정리충의 정리노트

0. 문제 주소 https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 H이다. 가장 왼쪽 위칸은 H가 아니다. H는 구멍이다. www.acmicpc.net 1. 풀이 약간 내리막길 문제랑 비슷한 느낌이 들었다. 맨 처음엔 칸 별로 연결관계를 만들어 BFS를 돌리려고 했으나... 멍청한 생각이었다. DFS + DP의 풀이를 사용한다. top-down은 어렵다 ㅠ 주의해야 할 점은 cycle의 유무이다. [PS/BFS & DFS] - [BOJ] 9466: 텀 프로젝트에서 DFS를 ..

0. 문제 주소 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문자로만 이루어져 있고, 길이가 8보다 크거나 같고, 15보다 작거나 같다. 모든 단어는 중복되지 않는다. www.acmicpc.net 1. 풀이 백트래킹이라고 하긴 했지만 가지치기는 안 해서 사실상 완전 탐색 문제 처음에 시간 초과가 났는데, 1. 모든 단어에 포함되어 있는 'a', 'n', 't', 'i', 'c'의 5글자를 빼주지 않아서 2. 조합 경우의 수를 재귀적으로 구할 때 vector를 인자로..

0. 문제 주소 https://www.acmicpc.net/problem/3055 3055번: 탈출 문제 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제일 친한 친구인 비버의 굴로 가능한 빨리 도망가 홍수를 피하려고 한다. 티떱숲의 지도는 R행 C열로 이루어져 있다. 비어있는 곳은 '.'로 표시되어 있고, 물이 차있는 지역은 '*', 돌은 'X'로 표시되어 있다. 비버의 굴은 'D'로, 고슴도치의 위치는 'S'로 나 www.acmicpc.net 1. 풀이 BFS 두 번 돌리는 문제. 잠깐 " 물 한 번 / 고슴도치 한 번 " 으로 해 볼까? 하다가 그럴 필요가 없는 ..

0. 문제 주소 https://www.acmicpc.net/problem/3425 3425번: 고스택 문제 고창영은 스택을 조금 변형해서 고스택을 만들었다. 고스택은 숫자만을 저장할 수 있고, 다음과 같은 10가지 연산을 수행할 수 있다. 편의상 스택의 가장 위에 저장된 수를 첫 번째 수라고 하고, 그 다음은 차례대로 두 번째 수, 세 번째 수라고 한다. NUM X: X를 스택의 가장 위에 저장한다. (0 ≤ X ≤ 109) POP: 스택 가장 위의 숫자를 제거한다. INV: 첫 번째 수의 부호를 바꾼다. (42 -> -42) DUP: 첫 번째 숫자를 하 www.acmicpc.net 1. 풀이 진짜 극혐 DIV와 MOD 연산에서 부호 처리에 관해 주저리주저리 써놓았는데, c++에서 / 과 % 연산자가 알..

0. 문제 주소 https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 1. 풀이 나쁜 수열을 어떻게 판별할까 고민했던 문제. 확실히 c++로 문자열을 처리하는 부분이 약한 걸 느꼈다. 마지막에 새로 추가하는 숫자를 포함하는 부분 수열만 체크할 것이고, 이 경우 체크해야 할 인접한 부분 수열의 길이는 1부터 (현재 문자열의 길이) / 2 까지 일 것이다. 그렇기에 부분 문자열의 길이를 i라 하고, 현재 문자열의 길이를 N이라고 한다면 비교해야 할 두 부분 수열은 ..

0. 문제 주소 https://www.acmicpc.net/problem/2624 2624번: 동전 바꿔주기 명보네 동네 가게의 현금 출납기에는 k 가지 동전이 각각 n1, n2, … , nk개 씩 들어있다. 가게 주인은 명보에게 T원의 지폐를 동전으로 바꿔 주려고 한다. 이때, 동전 교환 방법은 여러 가지가 있을 수 있다. 예를 들어, 10원 짜리, 5원 짜리, 1원 짜리 동전이 각각 2개, 3개, 5개씩 있을 때, 20원 짜리 지폐를 다음과 같은 4가지 방법으로 교환할 수 있다. 20 = 10×2 20 = 10×1 + 5×2 20 = 10×1 + 5×1 www.acmicpc.net 1. 풀이 [PS/DP] - [BOJ] 9084: 동전 참고 개수의 제한에 주의할 필요가 있다. [PS/DP] - [BO..

0. 문제 주소 https://www.acmicpc.net/problem/1256 1256번: 사전 첫째 줄에 N, M, K가 순서대로 주어진다. N과 M은 100보다 작거나 같은 자연수이고, K는 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. 풀이 소문자를 대문자로 써놔서 근데 또 돌아가서 시간만 날린 문제...지만 좋은 문제 가장 먼저 필요한 건 i 개의 a와 j 개의 z로 만들 수 있는 단어의 개수를 저장할 2차원 dp 테이블이다. 단순하게 (i+j) ! / ( i ! ) ( j ! ) 으로 계산할 수 있지만 당연히 오버플로우가 나기 때문에, dp를 이용한다. K의 값이 10억 이하이므로, 그 이상은 오버플로우 처리를 위해 값이 10억을 초과하면 10억 + ..

0. 문제 주소 https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자. www.acmicpc.net 1. 풀이 교점이 생기면 안 된단다. 그냥 LIS 문제다. LIS 풀이는 여러가지가 있지만, 이 문제에선 N 제한이 40000이므로 dp, 즉 O(N^2)로는 풀 수 없다. lower_bound를 사용하면 O(n log n)으로 쉽게 풀 수 있다. 먼저 빈 배열 d를 설정해두고, 기존 배열..

0. 문제 주소 https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망에서 사람들의 친구 관계는 그래프로 표현할 수 있는데, 이 그래프에서 사람은 정점으로 표현되고, 두 정점을 잇는 에지는 두 정점으로 표현되는 두 사람이 서로 친구 관계임을 표현한다. 예를 들어, 철수와 영희, 철수와 만수, 영희와 순희가 서로 친구 관계라면 이를 표현하 www.acmicpc.net 1. 풀이 대표적인 tree DP 문제. 먼저 연결 관계로 vector 배열 child를 이용해 트리를 만들고..

0. 문제 주소 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 www.acmicpc.net 1. 풀이 [PS/DP] - [BOJ] 11049: 행렬 곱셈 순서와 똑같은 기법을 사용하는 dp 문제. 마찬가지..