백준
1786_찾기
https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net KMP알고리즘을 사용해서 풀면된다. 백준 문제 글에 설명이 자세히 되어있으니 알고리즘 자체는 설명을 읽으면 될 것 같다. 최대의 k를 미리 계산해 놓으면 편리할 것이다 라는 구절이 있는데 이를 먼저 구해두면 된다. p를 처음부터 순환하면서 k를 저장해둘 공간을 넣어두면 된다. 해당 부분은 코드로 보는것이 좀 더 편할 것 같다. t = input() p = input() k=[0 for _ i..
2482_색상환
https://www.acmicpc.net/problem/2482 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net dp를 2차원배열로 설정해서 풀 수 있다. dp[i][j]라면 i개의 색중에서 j개의 색을 선택하는 것이다. dp를 채워나간다고 생각해보자. 만약 dp[i][j]를 채운다고 생각해보자. i번째 색이 새로 추가되었다면 그 색을 칠하는 경우와 안 칠하는 경우 2가지가 나올 것이다. 만약 색이 추가되었다면 i-1번째색은 칠할 수 없고, 이때 색을 칠한다면 j-1개를 구해야 하므로 i-2 개의 색으로 j-1개의 색을 칠하는 경..
11478_서로다른부분문자열의 개수
https://www.acmicpc.net/problem/11478 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net set을 통해서 중복이 들어갈 수 없게 한 후, 이어지는 문자열들을 집어넣으면 된다. s = input() result = set() for i in range(len(s)): for j in range(i,len(s)): result.add(s[i:j+1]) print(len(result))
17404_RGB거리2
https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net RGB거리 문제와 동일하지만 첫번째 집과 마지막집이 연결된 형태이다. 첫집과 마지막집의 색이 같아야 하지 않으므로 세 경우를 집어서 생각할 수 있다. 첫집을 R로 칠하고 dp를 채워나가 cost를 만든 것중 마지막집을 G,B로 칠한것중 최소비용 첫집을 G로 칠하고 dp를 채워나가 cost를 만든 것중 마지막집을 R,B로 칠한것중 최소비용 첫집을 B로 칠하고 dp를 채워..
2098_외판원순회 1
https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 해당문제를 풀기 위해선 비트마스크, dp , dfs 총 3가지의 알고리즘을 활용해서 풀 수 있다. 처음에 비트마스크와 dp만 가지고 풀어보려다가 많이 헤맸던 문제이다.. 먼저 dp는 2차원 dp로 선언을 한 후 dp[i][j]라면 i는 현재 도시의 위치, j는 현재까지 방문한 도시들을 기록한다. 이때 j를 비트마스크를 이용해서 기록한다. 즉, 현재 도시가 3이..
1311_할일정하기1
https://www.acmicpc.net/problem/1311 1311번: 할 일 정하기 1 N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다. 사람은 1번부터 N번까지 번호가 매 www.acmicpc.net 상당히 어려운 문제였다... 처음에 2차원 배열을 dp로 두고 한줄씩 채우면 뭔가 될꺼 같은데 이전에 방문하지 않았던 점에서 가져오는게 너무 어려워서 머리를 헤매다가 인터넷에서 약간의 힌트를 발견했다. 만약 문제의 예제케이스처럼 3명이 있다면 결국 우리는 [ 1 1 1 ] 와같이 채우는게 목표이다. 그리고 이 과정에는 [ 0 0 1 ] [ 0 1 0 ] [ 0 1 1 ] [ 1 0 ..