Problem Solving (135) 썸네일형 리스트형 [ BOJ 백준 3090번 - 차이를 최소로 ] 해설 및 코드 https://www.acmicpc.net/problem/3090 목적 자연수 N개로 이루어진 배열 A에서, 감소시키는 연산을 최대 T번 할때, 인접한 수의 차이의 최댓값을 최소로 만들자. 접근법 1. 0부터 10^9까지의 범위에서 이분탐색으로 인접한 수의 차이 값의 상한을 구해나간다. 2. 상한값을 정했다면, 인접한 두 수의 차이를 상한값 이하로 만들어줘야한다. 여기서 중요한 점은 행렬을 정방향, 역방향으로 한번씩 순회하면서, 진행 방향으로 나보다 큰 앞 놈만 쳐내야 한다. (정방향으로 진행하던 도중에 나보다 큰 뒷 놈이 신경쓰여 역방향으로 쳐내며 진행하다보면 시간초과를 경험할 것이다.) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2.. [ BOJ 백준 15732번 - 도토리 숨기기 ] 해설 및 코드 https://www.acmicpc.net/problem/15732 목적 규칙에 맞게 앞에서 부터 도토리를 집어넣었을 경우, 가장 마지막 도토리가 들어가게 될 상지가 어떤건지 구하자. 접근법 1. 규칙에 맞게 다 집어 넣고 답을 구하기에는 일단 집어 넣다가 시간초과에 걸리고 만다. (입력이 상자 100만개, 규칙 만개, 각 규칙 당 C가 1일 경우 10^10의 시간복잡도가 나오므로...) 2. 하나의 방법은 백만개의 상자를 만져서 시간 복잡도를 줄여야 한다. 바로 이분탐색이다. 1부터 백만까지를 범위로 적정 값을 이분탐색해야 한다. (이렇게 하면 20*10^4 정도 되려나..) 3. i번 상자까지 총 몇개의 도토리를 집어 넣었는지는 ... 간단한 수학이다. 1 2 3 4 5 6 7 8 9 10 11 12.. [ BOJ 백준 2585번 - 경비행기 ] 해설 및 코드 https://www.acmicpc.net/problem/2585 목적 다음 그림과 같이 S(=출발지: {0,0}), T(=도착지: {10000,10000}), 그리고 N개의 경유지가 있는데, M번을 경유하여 S에서 T로 가기위해 필요한 연료통의 최소 용량을 구하자. 접근법 1. 연료통의 용량을 1에서 S에서 T까지 가는데 필요한 양까지를 범위로 하는 이분탐색 알고리즘을 적용한다. 2. 제곱근을 구하는 오버헤드가 어느정도 존재하므로, 이 연산은 생략하고 진행한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 #include #include #define DIST(a,b,c,d) ((a.. [ BOJ 백준 2613번 - 숫자구슬 ] 해설 및 코드 https://www.acmicpc.net/problem/2613 목적 과 같은 숫자구슬을 나 과 같이 M개의 그룹으로 나누었을 때, 그룹의 최대 합이 최소가 되도록 하는 값을 구하자. 접근법 1. 이분 탐색 알고리즘으로 1부터 전체 구슬의 합까지를 범위로 하여, 최적 값을 찾아나간다. 2. 문제에서 분명하게 명시하진 않았지만, 직관적으로 그룹에 구슬이 하나도 없는 경우는 없어야 함을 인지한다. (M개의 그룹으로 나누라는 조건이 있으므로) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 #include using namespace std; int n, m, i, j,.. [ BOJ 백준 1981번 - 배열에서 이동 ] 해설 및 코드 https://www.acmicpc.net/problem/1981 목적 아래와 같은 nxn 배열의 (0,0) 부터 (n-1,n-1)까지 이동하기 위해 거쳐간 수들의 최대값과 최소값의 차이를 가장 작게 만드는 경우를 찾자. 접근법 1. 투 포인터 알고리즘으로 최소 최대 값을 정한 후, BFS 알고리즘을 이용해 최소,최대의 범위 안에서 이동 가능한지 검사한다. (투 포인터 알고리즘 설명 참고 : 백준 2842 - 집배원 한상덕) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 #include #include #include #define REP(i,.. [ BOJ 백준 6073번 - Secret Message ] 해설 및 코드 https://www.acmicpc.net/problem/6073 목적 코드단어(codeword)가 m개의 가로챈 코드(intercepted code)중 몇 개와 앞부분(initial bits)이 일치하는지 구하라. 접근법 1. 트라이 자료구조를 이용하여 접근한다. 아래 그림은 예제로 주어진 4개의 가로챈 코드로 구성한 트라이 구조의 형태이다. 2. 각 노드는 몇 개의 가로챈 코드에 사용되었는지, 가로챈 코드의 끝부분인지에 대한 정보를 담고 있어야 한다. 나타내자면 다음과 같다. 3. 이와 같은 정보를 가지고 코드단어와 앞부분(initial bits)이 일치하는 것이 몇 개나 되는지 계산한다. 가로챈 코드는 중복되는 데이터가 존재한다. 때문에 소스코드를 보면 알 수 있듯이 end의 자료형을 bool이 아.. [ BOJ 백준 2343번 - 기타 레슨 ] 해설 및 코드 https://www.acmicpc.net/problem/2343 목적 M개의 블루레이에, N개의 레슨 동영상을 블루레이 크기를 초과하지 않는 만큼 순서대로 채워 넣을 때, 가능한 블루레이의 최소 크기를 구하자. 접근법 1. 부분합과 이분탐색 알고리즘을 이용하여 접근한다. (이분 탐색 과정 참고 : 백준 2110 - 공유기 설치) 2. 블루레이의 크기를 정했다면, N 개의 레슨 동영상을 M개의 블루레이에 담을 수 있는지 여부를 확인해야한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include using namespace std; int n,m,a[(int)1e5+1.. [ BOJ 백준 2110번 - 공유기 설치 ] 해설 및 코드 https://www.acmicpc.net/problem/2110 목적 N개의 집 중에서, C개의 집에만 와이파이를 설치했을 때, 인접한 두 공유기의 거리를 최소로 만들자. 접근법 1. 이분 탐색 알고리즘을 이용하여 인접한 공유기의 최소 거리를 결정해 나간다. 가장 처음에 left는 1(가능한 최소 거리), right는 9(가능한 최대 거리)로 하여, 이분 탐색할 범위를 정한다. left와 right의 중간 값인 5를 최소 거리로 정한 후, 5이상의 간격으로 공유기 3개를 설치할 수 있는지 확인한다. 확인 후에는 범위를 좁혀야 하는데, 설치 가능 여부에 따라 중간 값을 기준으로 왼쪽, 오른쪽으로 범위를 갱신한다. 이런 과정을 left가 right보다 커질 때까지 반복하자. 2. 공유기 설치 가능 여부를 .. 이전 1 ··· 11 12 13 14 15 16 17 다음
