본문 바로가기

알고리즘/백준

 (68)
백준 2252 줄 세우기- 위상정렬 개념공부, 큐를 이용한 위상정렬 (c++) 우선순위 큐 문제를 풀어보려고 했다가, 위상정렬 개념을 처음 들어봐서 공부도 하고, 문제도 풀어본 좋은 경험이 된 문제인 것 같다. 문제를 풀기 전에 위상정렬에 대한 개념을 위키피디아에서 공부했다. 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예로 대학의 선수과목(prerequisite) 구조를 예로 들 수 있다. 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이..
백준 18429 근손실 - dfs와 백트래킹 (c++) https://www.acmicpc.net/problem/18429 18429번: 근손실 웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 감소하게 된다. 따라서 운동을 하지 않고, 가만히 있다면 매일매일 중량이 감소할 뿐이다. 다행히도 이 대학원생은 N개의 서로 다른 운동 키트를 가지고 있다. 이 대학원생은 하루에 1개씩의 키트를 사용하며, 매일 어떤 키트를 사용할 지는 마음대로 결정할 www.acmicpc.net 백트래킹을 하면서, 근손실이 나지않는 조건 하에서 dfs를 끝까지 진행한 경우에 결과에 +1씩 해주면 되는 문제였다. 백트래킹의 대표적인..
백준 2580 - 스도쿠 ( 재밌는 dfs 문제) c++ https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다. 나머지 빈 칸을 채우는 방식은 다음과 같다. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다. 굵은 선으로 구분되어 있는 3 www.acmicpc.net 최소경로 문제가 아니므로 bfs가 아닌 dfs 문제이다. 오랜만에 dfs 백트래킹 문제를 만났는데, n queen에서 공부했던 백트래킹의 ..
백준 2251 물통 - 세 쌍 벡터를 이용한 bfs https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다. 이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. www.acmicpc.net 이 문제를 풀기 위해서는 물통 a,b,c를 각각 한 쌍으로 만든 다음에, 세쌍 동시에 bfs를 진행해야 한다. a b c 각각 물통에 담긴 물..
백준 10814 나이순 정렬 - c++ 벡터를 가지고 sorting만 할 줄 알면 푸는 문제이다. 필자는 'paired vector'일 경우에는, 어차피 first를 가지고 정렬하기 때문에 다른 것 필요없이 sort함수를 그냥 갖다 쓰면 될줄 알았는데 그렇게 하니까 결과값이 이상하게 나온걸 깨달았음.. 1. sort를 쓰면 안되고 stable sort를 사용해야 한다. std::sort는 두 원소가 같을 때 기존의 순서를 유지해준다는 보장이 없는 unstable sort이다. 이 때문에 "나이가 같으면 가입한 순으로 한 줄에 한 명씩 나이와 이름을 공백으로 구분해 출력한다."가 지켜지지 않는다. 2. cmp 함수를 따로 만들어야 하는 필요성 pair::operator 자체가 first가 같으면 그 다음 second를 비교하기 때문에 {21,j..
백준 2251 물통 : bfs와 브루트포스 - c++ https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다. 이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. www.acmicpc.net 총 6가지 경우의 수에 대해서 전부 bfs. 각각의 물 담긴 상태가 이미 저장되어 있으면 넘기고. 세가지 상태를 전부 저장하는 경우는 처음이었..
1525 퍼즐 - bfs와 브루트포스 - c++ 문제가 처음에 봤을땐 어떻게 풀지 감이 잘 안왔는데(bfs로 풀어야 한다는 사실 빼고) 꾸준함님 해설을 보면서 풀었다. 퍼즐을 아예 하나의 문자열로 받아버린 다음에 y,x 좌표를 3으로 나눈 몫과 나머지로 구한다는 사실이 꽤 신선했다. 특히 잘 익숙치 않은 메소드들을 처음 보고 아직 갈길이 멀었구나를 느꼈던 문제.. 내가 몰랐다고 느낀 메소드들은 다 주석을 달아 놓았다. 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 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 ..
백준 9019 DSLR : bfs 활용 브루트포스 탐색 c++ https://www.acmicpc.net/problem/9019 9019번: DSLR 문제 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자) D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경 www.acmicpc.net 이 블로그에서 이전에 몇번 다뤄봤던 bfs 문제이다. (최단경로!) 여기서 중요한건 DSLR을 활용한 문자열을 출력해야 한다는 점이다. ..

티스토리툴바