Problem Solving (135) 썸네일형 리스트형 [ 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.. [ BOJ 백준 1654번 - 랜선 자르기 ] 해설 및 코드 https://www.acmicpc.net/problem/1654 목적 K개의 랜선을 최대 길이로 잘라 N개의 랜선을 만들자. 접근법 1. 길이를 1늘리거나 1줄이는 방법으로는 시간초과에 걸릴 것이다. 이분 탐색 알고리즘을 이용하자. (이분 탐색 과정 참고 : 백준 2110 - 공유기 설치) 2. 주어진 조건에 의해 int 자료형의 범위를 벗어나는 경우가 존재하기 때문에, 더 큰 범위의 자료형을 사용한다. 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 using namespace std; int k,n,a[10001],ret; void bs(unsigned l,unsig.. [ BOJ 백준 2512번 - 예산 ] 해설 및 코드 https://www.acmicpc.net/problem/2512 목적 지방예산을 모두 더해서 국가예산에 최대한 가깝게 만들 수 있도록 상한액을 정하라. 접근법 1. 상한액을 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 #include #include using namespace std; int n,m,a[10001],ret; void bs(int l,int r){ if(l>r){ ret=r; return; } int h=(l+r)/2; long long k=0; for(int i=0;i.. [ BOJ 백준 2805번 - 나무 자르기 ] 해설 및 코드 https://www.acmicpc.net/problem/2805 목적 절단기에 설정한 높이 h 이상의 나무만 잘라 그 합이 m이상이 되도록 하는 h를 구하자. 접근법 1. 절단기의 높이를 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 #include #include using namespace std; int n,m,a[1000001],ret; void bs(int l,int r){ if(l>r){ ret=r; return; } int h=(l+r)/2; long long k=0; for(in.. [ BOJ 백준 1022번 - 소용돌이 예쁘게 출력하기 ] 해설 및 코드 https://www.acmicpc.net/problem/1022 목적 아래 그림과 같이, 소용돌이를 출력하려는 수들 중에 가장 길이가 긴 수에 서식을 맞추어 오른쪽 정렬로 출력한다. 접근법 1. 만약, i, j가 있고, 두 수중에 절대값의 최대값이 2이라면, i, j에 해당하는 수는 다음과 같은 테두리 형태의 수들 중 하나일 것이다. 2. 위 테두리는 i와 j의 값이 2인지 -2인지에 따라 각 꼭지점을 기준으로 아래와 같이 네 부분으로 나눌 수 있다. 3. 이미 위의 그림까지 보면 공식을 도출해 낼 수 있을 것이다. 우측하단 꼭지점인 (n, n)에 해당하는 값은 (2*n+1)^2로 나타낼 수 있다. 시계방향으로 다음의 꼭지점은 이전 꼭지점에서 2*n 만큼 감소한 값이다. 1 2 3 4 5 6 7 8 9.. [ BOJ 백준 3005번 - 크로스워드 퍼즐 쳐다보기 ] 해설 및 코드 https://www.acmicpc.net/problem/3005 목적 퍼즐에서 사전순으로 제일 앞서는 단어를 구한다. 접근법 1. 가로방향으로 놓인 단어를 찾아서 앞서는 단어 갱신 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 #include using namespace std; int r, c; char p[22][22]; string ret=""; void find(int a,int b,bool d) { for (int i = 0; i tmp) ret = tmp; tmp = ""; } else tmp.push_back(ref); } } .. 이전 1 ··· 12 13 14 15 16 17 다음
