https://www.acmicpc.net/problem/25418난이도 :  S3Tag : ?풀이 일자 : 2025-03-19문제 탐색하기1 A와 K가 주어졌을때, 두 가지 연산만을 사용하여 A를 K로 변경해야합니다.연산A+1A*2위 두 연산을 적절히 사용하여 A를 K로 만드는 최소 횟수를 구하면 됩니다.가능한 시간복잡도백트래킹(DFS)모든 경우를 탐색하여 K가 되는 경로를 찾을 수 있습니다.하지만, 최악의 경우 O(2^N)로 시간이 오래 걸려 시간 초과가 발생합니다.BFS (너비 우선 탐색)BFS는 최소 경로 탐색에 최적화되어 있습니다.한 번 방문한 숫자는 다시 방문하지 않기에 O(N)의 시간이 걸립니다.따라서, BFS를 사용하는게 효율적인 풀이 입니다.  알고리즘 선택초기에는 백트래킹(DFS) 방식..

https://www.acmicpc.net/problem/2467 난이도 : G5Tag : Binary Search풀이 일자 : 2025-03-18문제 탐색하기N : 전체 용액 수( 2 용액은 산성(양수) 또는 알칼리성(음수)이며, 혼합하면 각 특성값의 합이 특성값이 됨 조건:N(2 ≤ N ≤ 100,000)특성값은 -1,000,000,000 ≤ X ≤ 1,000,000,000모든 용액의 특성값은 오름차순 정렬됨산성 용액만, 알칼리성 용액만 존재할 수도 있음N개의 용액 중 두 용액의 특성 값이 0에 가장 가까운 경우를 찾으면 됩니다. 가능한 시간복잡도브루트포스가장 간단하게 생각하면 브루투포스 방식(완전탐색)을 생각할 수 있습니다.가장 직관적인 방법은 이중 for문을 사용하여 모든 조합을 확인하는 것..

https://www.acmicpc.net/problem/2805 난이도 :  S2Tag : Binary Search풀이 일자 : 2025-03-17문제 탐색하기N: 나무의 수 (1 M: 상근이가 집으로 가져가려고 하는 나무의 길이 (1 나무 높이: (0 나무의 높이는 항상 M보다 크거나 같다.절단기에 설정할 높이 H 를 찾아야 합니다.나무 N개를 절단기에 넣고, 높이가 H보다 큰 나무는 잘리고, 작은 나무는 그대로 남습니다.잘린 나무의 총 길이가 최소한 M 이상이 되도록 해야 하며. 가능한 절단기의 높이 중 최댓값을 구하는 문제 입니다.   가능한 시간복잡도 나무 개수 N이 최대 1,000,000개이므로,모든 높이에 대해 직접 탐색하면 O(NH) 으로 불가능합니다. 그러므로 이분 탐색을 활용하면 O(l..

https://www.acmicpc.net/problem/11663 난이도 :  S3Tag : Binary Search풀이 일자 : 2025-03-16문제 탐색하기N: 점의 개수 (1 M: 선분의 개수 (1 M개의 시작점과 끝점 (1 점의 좌표는 중복되지 않음. N개의 점과 M개의 선분이 주어졌을 때 각 선분의 시작점과 끝점이 주어지면 해당 선분위에 존재하는 점의 개수를 출력하면 됩니다.가능한 시간복잡도먼저 최대 N개의 점이 주어지므로 O(N)이후 M개의 선분이 주어지므로 O(M)각 선분의 길이는 최소 1부터  10억까지 이므로 각 선분의 점의 주어졌을때 매번 몇개의 점이 있는지 순서대로 탐색을 하는건 불가능합니다. 이때는 이분탐색을 사용 가능합니다.이분탐색은 정렬이 되어야만 사용 가능하며 이분탐색의 시..

https://www.acmicpc.net/problem/17266 난이도 :  S3Tag : Binary Search풀이 일자 : 2025-03-15문제 탐색하기N: 굴다리의 길이 (1 M: 가로등의 개수 (1 x: M개의 설치를 할 수 있는 가로등의 위치 (0 주어진 조건가로등의 높이의 두배만큼 주위를 비춘다.모든 가로등의 높이는 같다.설치할 가로등의 개수(M)과 설치할 위치(x)는 이미 정해졌다.가로등의 위치(x)는 오름차순으로 입력받으며, 중복되지 않고 정수이다.즉, 이 문제의 핵심은 최소한의 비용을 사용해 가로등이 굴다리를 전부 비출 수 있는 높이를 찾으면 됩니다.가능한 시간복잡도여기서는 완전탐색과 이분탐색을 둘 다 진행해 볼 수 있습니다.완전탐색의 경우완전탐색을 사용하면, 모든 가로등 간의 간..

https://www.acmicpc.net/problem/13335 난이도 :  S1Tag : Simulation풀이 일자 : 2025-03-14문제 탐색하기n : 다리를 건너는 트럭의 수 (1 w : 다리의 길이 (1 L : 다리의 최대 하중 (10 a(i) : i번째 트럭의 무게주어진 조건트럭의 순서는 바꿀 수 없음다리 위에는 최대 w대의 트럭만 동시에 올라갈 수 있음트럭들은 매초마다 1만큼 이동하며, 다리 길이를 지나야 완전히 건넘다리 위 트럭들의 무게 합이 L을 초과할 수 없음완전히 올라가지 못한 트럭의 무게는 다리의 하중에 포함되지 않음모든 트럭이 다리를 건너는 최단 시간을 구하는 프로그램을 작성해야 합니다.가능한 시간복잡도이 문제는 완전탐색을 이용한 시뮬레이션 문제로 해결할 수 있습니다.최대 ..

https://www.acmicpc.net/problem/2615 난이도 : S1Tag : Simulation풀이 일자 : 2025-03-13문제 탐색하기이기는 경우: 같은 색의 바둑알이 정확히 5개 연속으로 놓인 경우 (가로, 세로, 대각선)6개 이상 연속될 경우 승리로 인정되지 않음바둑알 정보검은 바둑알: 1흰 바둑알: 2빈자리: 0출력 조건검은색이 이긴 경우 1 출력흰색이 이긴 경우 2 출력승부가 결정되지 않은 경우 0 출력이겼을 경우 → 연속된 다섯 개의 바둑알 중 가장 왼쪽에 위치한 바둑알의 좌표 출력세로로 배치된 경우 → 가장 위쪽의 바둑알 좌표 출력입력값19×19 크기의 바둑판 상태즉 이 문제는 바둑판을 탐색하며 오목(정확히 5개 연속)을 찾고, 가장 왼쪽 또는 위쪽에 있는 바둑알의 위치를 ..

https://www.acmicpc.net/problem/2503 난이도 : S3Tag : Simulation풀이 일자 : 2025-03-12문제 탐색하기영수가 생각한 수: 111 ~ 999 (0 제외, 중복 숫자 없음)민혁이가 질문한 수: 111 ~ 999 (0 제외, 중복 숫자 없음)N: 질문의 수 (1 스트라이크 (Strike): 같은 숫자가 같은 위치에 존재할 경우볼 (Ball): 같은 숫자가 존재하지만, 위치가 다를 경우민혁이가 질문을 하고 영수가 대답한 정보를 파악해서 답이 될 수 있는 숫자의 개수를 출력해야 합니다.이때, 각 숫자는 서로 달라야 합니다.가능한 시간복잡도문제에 요구하는대로 구현하는 시뮬레이션 문제입니다.먼저 숫자는 1부터 9까지로 이루어진 서로다른 3자리의 수 입니다.그럼 모든..