본문 바로가기

알고리즘/백준

 (109)
9252번 : LCS 2 https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이 문제는 다이나믹 프로그래밍 문제이다. DP 정의를 잘하면 쉽게 풀 수 있는 문제이다. 두 문자열의 가장 긴 공통된 부분 수열을 찾아야 하는 문제이다. str1 : ACAYKP str2 : CAPCAK 이 두 수열에서 가장 긴 공통된 부분 수열을 어떻게 찾을 수 있을까? 만약 가장 긴 공통된 부분 수열이 있다고 가정하면, CAPCAK에서 각 문자는..
11066번 : 파일 합치기 https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 문제 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 www.acmicpc.net 이번 문제는, DP 점화식을 생각하지 못해서 구글링 통해서 코드를 참고했다. 뭔가, 사칙 연산에 관련된 것은 항상 같은 방식으로 ..
2225번 : 합분해(점화식의 중요성) https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 규칙을 찾아보려고 했을 때 쉽지 않았다. DP에서 가장 중요한 것은 점화식이 아닐까... 우선 점화식이 찾는 습관부터 들이도록 하자. 하향식 접근으로 간단하게 문제를 풀어보았다. 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 #include #include #include using namespace std; int N, K; long long dp[201][201]; long long solve(int N, int K) { if (K == ..
1890번 : 점프 https://www.acmicpc.net/problem/1890 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 www.acmicpc.net 이 문제는 기분좋게 풀었다. DP를 이용한 하향식 접근으로 문제를 해결했다. 해설코드(C++). 1 2 3 4 5 6 7 8 9 10 11 1..
11054번 : 가장 긴 바이토닉 부분 수열 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 못 풀어서 해설을 본 문제. 증가하는 부분 수열을 두 번 이용하면 풀 수 있는 문제. DP 정의가 복잡해지고 있다면, 문제의 해결 접근 방법이 맞는지 다시 생각해봐야 한다. 해설코드(C++). 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 ..
1520번 : 내리막 길(C++, 시간 초과, Bottom-up, Top-down) https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다. www.acmicpc.net 이번 문제는, 다이나믹 프로그래밍 문제이다. 대학생 때, Bottom-up 접근 방법, Top-down 접근 방법들을 배웠던 기억이 난다. 그러면서 호출되는 순서를 그래프로 표현해봐라는 과제가 있었는데, 하면서도 이걸 왜하나 싶었는데... 이제 그 중요성을 알 수 있었다. 또한, 지금까지 접근했던 문제들이 B..
1904번 : 01타일 https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다. 그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수 www.acmicpc.net 오랜만에 깔끔하게 풀은 문제! DP문제로 분류되어 있어서, DP로 접근하긴 했다. 이 문제는 비교적 쉬운 DP문제라 노골적으로 DP문제임..
15927번 : 회문은 회문아니야!! https://www.acmicpc.net/problem/15927 15927번: 회문은 회문아니야!! 팰린드롬이란 앞으로 읽으나 뒤로 읽으나 같은 문자열을 말한다. 팰린드롬의 예시로 POP, ABBA 등이 있고, 팰린드롬이 아닌 것의 예시로 ABCA, PALINDROME 등이 있다. 같은 의미를 가지는 여러 단어들을 보자. 회문 (한국어) palindrome (영어, 프랑스어, 노르웨이어, 그리스어, 라틴어) 回文 (일본어, 중국어) palindrom (독일어, 덴마크어) palindromi (핀란드어) palíndromo (스페인어, 포르투갈어) pal www.acmicpc.net 이 문제는, 과거에 풀다가 실패한 문제이다ㅠㅠ... 어느정도 알고리즘을 풀어봤다면, 회문의 정의는 알 것이다. 이 문제는..

티스토리툴바