본문 바로가기

알고리즘

 (74)
백준 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을 활용한 문자열을 출력해야 한다는 점이다. ..
백준 1963 - 소수경로 - bfs,몫 나머지 활용 - C++ https://www.acmicpc.net/problem/1963
백준 1697 숨바꼭질 - bfs - c++ https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 www.acmicpc.net 한 7번;; 만에 풀었다. 큐에다가 bfs를 진행하면서 넣고 빼고를 반복하면서 카운팅만 잘 해주면 풀 수 있는 문제지만 따져야 되는 조건들..

티스토리툴바