search5 [프로그래머스] 징검다리 문제 링크: https://programmers.co.kr/learn/courses/30/lessons/43236 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 프로그래머스 기준 Level 4인, 약간 어려운 문제입니다. 문제 내에서 총 거리가 주어지고 (distance), 각 바위의 위치가 주어집니다. 이후 제거해야 하는 바위의 수 (n)이 주어집니다. n개의 바위를 제거한 후 시작점 - 각 바위 사이 - 도착점 사이의 거리를 구했을 때, 어떤 바위를 제거했느냐에 따라 각 바위 사이 거리가 달.. 2021. 10. 8. [백준 1300번] K번째 수 난이도: 골드 III 문제 링크: https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net N의 최대 크기가 10만이므로, 배열에 들어갈 모든 수를 계산하기에도 벅찹니다 (10만 x 10만 번의 연산). 따라서 이 문제는 모든 숫자를 계산하지 않고 풀 수 있어야 합니다. K번째 수를 구한다는 것은, 이보다 작은 수가 K-1개 존재한다는 뜻입니다. 이러한 상황에서 비교 연산을 훨씬 덜 하면서 원하는 수를 탐색하는 방법 중 하.. 2021. 9. 17. [백준 2110번] 공유기 설치 난이도: 실버 1 문제 링크: www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 이분 탐색을 이용하는 문제 중 꽤 애를 먹은 문제입니다. 어느 부분에서 이분 탐색을 이용해야 하는지 고민을 많이 했는데, 다른 블로그 (링크)의 글을 참고하여 알고리즘을 이해했습니다. 문제의 접근 순서는 다음과 같습니다. 주어진 집들의 좌표를 오름차순으로 정렬한다 (이분 탐색의 기본 조건). 집들 사이의 거리를 초기화한다. 최솟값.. 2021. 3. 8. 이진 탐색 탐색이라 함은, 데이터의 집합 중에서 원하는 값을 찾는 것을 의미합니다. 오늘 다루어 볼 내용은 이진 탐색 (binary serach)인데, 이에 앞서 가장 기본적인 탐색 방법인 순차 탐색을 다루고자 합니다. 순차 탐색 순차 탐색 (sequential search)는 배열 내의 특정 데이터를 찾기 위해 앞에서부터 순차적으로 확인하는 방법입니다. 정렬되지 않은 배열에서 데이터를 찾을 때, 시간만 충분하다면 순차 탐색이 좋은 방법이 될 수 있습니다. 'Carrot' 이라는 문자열을 찾는 과정입니다. 파란색은 현재 'Carrot'와 비교하는 문자열, 빨간색은 이미 비교하였으며 일치하지 않은 문자열, 초록색은 목표로 하는 문자열입니다. 첫 번째 문자열 'Apple', 두 번째 문자열 'Banana'는 일치하지 .. 2021. 2. 4. [백준 16236번] 아기 상어 이 문제는 삼성 SW 역량 테스트 기출문제 입니다. 난이도: 골드 5 문제 링크: www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net BFS를 이용한 탐색을 핵심으로 하는 문제입니다. BFS에 대한 이론적 배경은 여기를 참고하세요. BFS를 실제로 이용하여 문제를 푸는 접근법이 아직 생소하여, 인터넷 검색을 많이 활용했습니다. 문제가 내용이 긴데, 요약하면 아래와 같습니다. 상어는 본인보다 작은 물고기만 잡아먹을 수 있다. 상어는 빈 공간 혹은 자기보다 .. 2020. 11. 23. 이전 1 다음
