정리충의 정리노트

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/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 문제. 마찬가지..

0. 문제 주소 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같다. www.acmicpc.net 1. 풀이 2차원 배열을 이용하여 모든 구간별 정보를 메모이제이션 하는 dp 문제. 다시 말해서, i번째 행렬부터 j번째 행렬까지 곱했을 때의 최소 곱셈 횟수를 저장할 것이기 때문에, 이 정보들을 이용하기 위해선 곱셈 형태를 큰 부분 두 개로 나누어야 한다. A, B, C, D 4개의 행렬이 있다고 가정해 보자. 메모이제이션을 통해 A ~ C , 그리고 B ~ D ..

0. 문제 주소 https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다. 동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오. www.acmicpc.net 1. 풀이 문제에 있는 예시는 M이 너무 크므로, 다음과 같은 예시를 들어보자. 동전 종류 : 2, 4, 5 만들어야 하는 금액 : 10 기본 개념은, 첫 번째 ~ i 번째 까지의 동전을 사용했을 때,..