Problem Solving/BOJ 백준 (132) 썸네일형 리스트형 [ 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. 공유기 설치 가능 여부를 .. [ BOJ 백준 5052번 - 전화번호 목록 ] 해설 및 코드 https://www.acmicpc.net/problem/5052 목적 전화 번호 목록이 주어졌을 때, 일관성 있는 목록인지 아닌지 구한다. (문제에서 말하는 일관성 없는 목록이라 함은, 어떤 번호가 다른 번호의 앞부분에 매칭된다는 뜻이다.) 접근법 1. 트라이 자료구조를 연습할 수 있는 기본 문제로서, 트라이 구조체만 구현하면 쉽게 풀 수 있다. 이외에도 정렬하여 인접한 문자열만 비교하거나, 해싱을 통해서 해결 가능하다. 트라이를 사용하는 접근과 정렬을 사용하는 접근, 두 가지로 풀어보았다. 트라이 자료구조 사용 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.. [ BOJ 백준 4358번 - 생태학 ] 해설 및 코드 https://www.acmicpc.net/problem/4358 목적 중복된 값이 존재하는 종을 입력으로 받아, 각 종을 사전순으로 비율과 함께 출력한다. 접근법 1. key의 자료형이 string이고, value의 자료형이 int인 map으로 입력 데이터를 처리한다. 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 #include #include #define endl '\n' using namespace std; int main(){ ios_base::sync_with_stdio(false); cin.tie();cout.tie(); map m; string species; int tota.. [ BOJ 백준 2842번 - 집배원 한상덕 ] 해설 및 코드 https://www.acmicpc.net/problem/2842 목적 모든 집에 배달을 할 수 있는 피로도(=방문한 최고 고도와 최저 고도의 차이)의 최소값을 구하라. 접근법 1. 최저 고도와 최고 고도를 결정하기 위해 투 포인터 알고리즘을, 배달 가능한지 여부를 확인하기 위해 DFS로 접근하자. 우선, 투 포인터 방식을 적용하기 위해, 아래 그림과 같이 고도를 중복 없는 정렬된 형태의 배열로 가지고 있어야 한다. 구현을 쉽게 하기 위해서 set을 이용했다. 2. 최저 고도(이하 LEFT)와 최고 고도(이하 RIGHT)를 가리키는 두 개의 포인터(코드에선 set의 iterator를 사용)를 이용해서 다음 절차를 LEFT가 배열의 끝에 도달할 때까지 반복 수행한다. (투 포인터 알고리즘 핵심...) RI.. 이전 1 ··· 11 12 13 14 15 16 17 다음
