![]()
* 이 글은 "한국항공대학교 - 알고리즘해석 및 설계" 정렬에 나온 내용을 바탕으로 작성하였습니다. 1. 분할 정복 기법 (Divide - and - Conquer) - 착안점 : 문제의 크기가 커지면 더 풀기가 어렵다. - 주어진 문제를 작은 사례로 나누고(Divide) 각각의 작은 문제들을 해결하여 정복(Conquer)하는 방법 - 순환적(recursive)으로 문제를 푸는 하향식(Top - Down) 접근 방법 - 분할 정복의 설계 전략 (1) 문제 사례를 하나 이상의 작은 사례로 분할(Divide)한다. (2) 작은 사례들을 각각 정복(Conquer)한다. 작은 사례가 충분히 작지 않은 이상 재귀를 사용한다. (3) 필요하다면, 작은 사례에 대한 해답을 통합(Combine)하여 원래 사례의 해답을..
![]()
문제 링크 : https://www.acmicpc.net/problem/4375 4375번: 1 문제 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. 입력 입력을 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다. 출력 1로 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다. 예제 입력 1 복사 3 7 9901 예제 출력 1 복사 3 6 12... www.acmicpc.net 문제 2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오. 입력 입력을 여러 개의 테스트 케이..
![]()
문제 링크 : https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다. X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다. 예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()( www.acmicpc.net 문제 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된..
![]()
www.acmicpc.net/problem/2477 2477번: 참외밭 첫 번째 줄에 1m^2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1≤K≤20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지나� www.acmicpc.net 실버 5의 구현 문제여서 쉬울 것이라고 생각하고 접근했다가 엄청 애먹었다... 문제를 보면 다들 큰 사각형에서 작은 사각형 빼면 되겠다!라고 생각할 것이다. 근데 어떻게 작은 사각형을 구하지...? 이 고민만 30분 넘게 했다. 다양한 방법이 생각났지만 아무리 봐도 실버5에 쓸만한 구현들이 아니었다. 분명 더 쉬운 풀이법이 있을 것 같은데... 결국 내가 마지막으로 생각해 낸 방법은 4가지 도형으로 나누어서 각..
1. LCS 알고리즘이란? LCS(Longest Common Subsequence) 알고리즘은 단어 그대로 해석하자면 가장 긴 공통 부분 문자열이다. 부분 문자열(Subsequence)이란 어떤 단어에서 연속되지 않는 부분 문자열을 뜻하는데 연속된 부분 문자열을 나타내는 부분 문자열(Substring) 도 있다. (따라서 string 헤더파일의 substr()은 substring을 의미한다) 두 부분 문자열의 차이는 예를 들자면 pringles sangeles 이렇게 두 문자열이 있을 때 가장 긴 Subsequence는 pringles sangeles "ngles" 가 되고 가장 긴 Substring은 pringles sangeles "les" 가 된다. 위에서 알 수 있듯 가장 긴 Substring은 ..
![]()
* 이 글은 "알고리즘 문제 해결 전략(종만북)" 中 20장 문자열에 나온 내용을 바탕으로 작성하였습니다. 개요 '문자열'은 간단한 문제여도 쉽지 않은 문제들이 많다. C++의 STL을 사용하며 많은 부분에서 편리함이 생겼지만, 그럼에도 문자열 문제들은 많은 시간이 소요된다. 하지만 문자열 문제는 카카오 코딩테스트 문제 유형에도 자주 나오며 그 외 많은 문제에서 찾아볼 수 있다. 항상 나를 괴롭혀 왔던 '문자열'에 대해 자세히 공부해 보고자 한다. 1. 문자열 검색 문자열을 검색하는 알고리즘에 대해 공부해보자 주어진 긴 '짚더미(Haystack)' 문자열 H가 '바늘(Needle)' 문자열 N을 부분 문자열로 포함하는지를 확인하고, 포함한다면 N과 일치하는 부분 문자열의 시작 위치를 찾는 문제를 문자열 ..
![]()
백준 14499번 - 주사위 굴리기 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 이 문제는 시뮬레이션 문제이다. 주사위를 지도 안에서 굴리면서 윗면(바닥 면과 반대되는 면)을 출력하는 문제이다. 조건은 다음과 같다. 주사위를 굴렸을 때, 이동한 칸에 쓰여있는 수가 0이면, 주사위의 바닥면에 쓰여 있는 수가 칸에 복사된다. 0 이 아닌 경우에는 칸에 쓰여 있는 수가 주사위의 바..
ACM-ICPC 2020 Korea Regional을 대비하여 작성해 보았습니다. 2015~2019년도 까지 각 년도별 문제 중 난이도 별로 선별해서 작성했습니다. 선별된 문제 난이도는 골드 1 ~ 플래티넘, 다이아입니다. (Solved AC 기준) (실버나 골드3, 4 문제는 알고리즘 유형을 모른 채로 풀어보는게 좋을 것 같아서..) 2015 Korea Regional 난이도 문제 이름 및 번호 연관 알고리즘 플래티넘 2 동전 교환 - 11493번 최대 유량, 최소 비용 최대 유량 플래티넘 2 격자 0 만들기 - 11495번 최대 유량 플래티넘 2 홀수 싸이클 - 11498번 (미공개) 플래티넘 2 Path - 11499번 기하학 플래티넘 4 Polynomial - 11500번 수학, 다이나믹 프로그래..
![]()
알고리즘이란?? 문제를 해결하기 위한 절차나 방법을 말한다 알고리즘이란 단어의 정의는 대수학의 아버지 알-콰리즈마의 이름에서 유래되었다고 전해지는데, 오늘 날 어떤 문제를 푸는 알고리즘이란 어떤 입력에서 정확한 출력을 유한한 시간에 내는 프로그램을 일컫는다. 여기서 어떤 입력이란? 주어진 입력의 크기와 관계없이 문제를 풀 수 있음을 뜻하는데 문제에 따라서는 음수도 될 수 있고 매우 크거나 작은 수(double 자료형의 범위 밖)가 될 수도 있다. 정확한 출력은 말 그대로 코드를 짠 프로그래머가 원하는 결과값을 나오게함을 의미한다. 유한한 시간은 여러 알고리즘 문제 사이트에서 볼 수 있는 시간 제한 내에 풀 수 있는지를 뜻한다. 예를 들어 내가 짠 코드가 무한루프에 빠지게 되거나 정말 터무니없는 반복을 할..
![]()
* 이 글은 "알고리즘 문제 해결 전략(종만북)" 中 11장 조합 탐색에 나온 내용을 바탕으로 작성하였습니다. 우리가 문제 해결 시 흔히 사용하는 동적 계획법(DP) 또는 분할 정복과 같은 완전 탐색에 기초한 디자인 패러다임은 사실 실생활에서 쓰기엔 매우 한정적이다. 예를 들어, 인공지능 체스 프로그램을 알고리즘으로 짠다고 할 때 우리가 가장 먼저 떠올릴 수 있는 것은 브루트 포스(brute force) 방식이다. 즉, 가능한 모든 말의 움직임을 다 해보는 것이다. 하지만 이 방식은 어림도 없는게 움직일 수 있는 말과 이동 가능한 칸이 너무 많기 때문에 만약 이 방식으로 프로그램을 개발했다고 하면, 죽을 때까지 게임이 끝나지 않을 것이다. (경우의 수가 10^120 가지라고 합니다.) 그렇다고 해서 분할..
![]()
www.acmicpc.net/problem/17134 17134번: 르모앙의 추측 첫째 줄에 테스트 케이스의 개수 T (1 ≤ T ≤ 100,000)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 N은 홀수이고, 5 < N ≤ 1,000,000을 만족한다. www.acmicpc.net 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 67 68 69 70 71 72 73 74 75 76 77 78 79 8..
![]()
www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net 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 6..
