지속 가능한 꾸준함

www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 �� www.acmicpc.net 해당 문제는 위상 정렬 알고리즘을 이용하여 풀 수 있습니다. 풀이는 다음과 같습니다. 1. 수행 가능한 순대로 작업을 수행한다. 이때, 동시에 수행가능한 작업은 동시에 수행한다. 2. 각 작업을 수행하였을때 걸린 최대 시간을 기록한다. 3. 각 작업을 수행하였을때 걸린 최대 시간 중 최대 시간을 출력한다. 모든 작업을 완수하는데 걸린 최소 시간을 구해야 하는데 풀이에선 최대 시간을 구하는 느낌이 ..

Zig-zag Scanning은 2D Array의 Traversal 방법 중 하나로, 원소를 접근함에 있어 아래와 같이 지그재그 순으로 접근하는 기법입니다. 해당 Traversal 방법은 영상 압축 과정에서 주로 쓰입니다. 관련 내용으로 [H.264] Quantization(양자화)과 Zig-zag scanning 을 참고해보시면 도움이 될 것 같습니다. 위 그림을 보며 원소 접근 방식을 분석해보면 중간중간 방향을 전환하는 분기점이 존재합니다. 그리고, 분기점의 y, x 위치(행렬로 치면 행, 열)에 따라 하향 혹은 우향 방향에 존재하는 원소를 한 번 접근한다음 좌하향 대각선 방향 혹은 우상향 대각선 방향으로 원소를 쭈욱 접근 하는 규칙을 가지고 있음을 확인할 수 있습니다. C++을 이용하여 이를 구현해..

www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 본 문제는 정렬에 관한 문제입니다. 무분별한 C++ STL 사용으로 몇몇 정렬 알고리즘의 구현 방법을 잊은터라 정렬 알고리즘을 복습할겸 알고리즘 문제도 풀겸 일석이조의 효과를 누리고자 해당 문제를 풀었습니다. 코드를 제출하기전에 직감적으로 \(O(N^{2})\)의 복잡도를 갖는 정렬 알고리즘(Selection Sort, Insertion Sort, Bubble Sort)으로는 문제를 통과할 수 없음..

www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 본 문제의 제목은 LCS(Longest Common Subsequence)입니다. 이름만 봐도 유명한 문제라는 느낌이 들어 서칭을 바로 해보았습니다. 역시나 유명한 문제였습니다. LCS는 Longest Common Substring과 Longest Common Subsequence이 존재합니다. 2개는 다른 의미를 가지므로 구분해야합니다. 차이점은 공통되는 부분의 연..

www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주�� www.acmicpc.net 본 문제는 동전들이 주어지고, 각각의 동전에 대한 가치(원으로 생각)가 주어집니다. 그리고, 이 동전으로 k 원을 만들어낼 수 있는지, 만들어낼 수 있다면 주어진 동전을 최소 몇개를 써야 k원을 만들어낼 수 있는지를 묻는 문제입니다. k원을 주어진 동전을 최소로 사용하여 만들기 위해서는 k원보다 작은 금액들을 먼저 최소로 사용하여 만들 수 있어야 합니다. 어떤 문제를 작은 문제..

본 포스트는 알고리즘 문제를 해결해가며 공부한 알고리즘 중, 개인적인 판단하에 실용적이라 생각되는 알고리즘을 간략하게 정리한 글입니다. 게시글의 성격상 지속적으로 내용이 업데이트 됩니다. KMP(Knuth–Morris–Pratt) Algorithm: 문자열 검색 알고리즘

www.acmicpc.net/problem/1015 1015번: 수열 정렬 P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다. 배열 A가 주 www.acmicpc.net 본 문제는 차례로 입력받은 원소를 저장하는 배열 A를 오름차순(=비내림차순)으로 정렬하기 위하여, 배열 A의 각 원소를 몇 번째 인덱스에 배치해야하는지를 찾는 문제입니다. 예제로 A = {2, 3, 1}이라는 배열이 주어졌을때, A의 원소 "2", "3", "1"을 오름차순이 되도록 배치시켜 재배치(A) = {1, 2, 3}이 되도록 배열의 원소를 재배치해야..

www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 본문에 앞서 해당 문제는 다른 분들의 솔루션을 참고하고 풀었음을 밝힙니다. 본 문제는 시뮬레이션 문제입니다. 알고리즘은 문제의 규칙에 맞게 아래의 순으로 진행됩니다. 1. 미세먼지 확산 *미세먼지는 확산시, 미세먼지가 존재하는 칸에도 누적되는 방식으로 확산이 됩니다. 2. 미세먼지 이동 3. 위 과정(1. ~ 2.) T번 반복 문제를 풀다가 미세먼지를 시계/반시계 방향으로 이동시키는 부분을 깔끔하게 구현하는 ..

www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 본 문제는 브루트포스 알고리즘을 사용하여 풀었습니다. 그런데 모든 경우를 일일히 탐색하는 것은 불가능합니다. NxN 체스판에 퀸 N 개를 놓을 수 있는 경우의 수는 \({{}_{N^2}\mathrm{C}_{N}}\) 이며 N = 15 일때, 91,005,567,811,177,478,095,440 가지의 경우를 고려해야합니다. 그렇기 때문에 우리는 퀸을 놓으며 걸러낼 수 있는 경우의 수는 최대한 걸러내야 합니다. 먼저, 문제 및..

www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하� www.acmicpc.net 본 문제는 구현 및 시뮬레이션 문제입니다. 푸는데 2일 가량 걸렸을 정도로 저에게는 너무 어려운 문제였습니다. 제가 어려웠던점은 말을 쌓아야할때, 연결 관계를 코드로 구현해야하는 점이 어려웠습니다. 처음에는, 말이 쌓이며, 경우에따라 순서도 바뀌어야하니 데이터의 삽입과 Reverse 가 쉽게 가능한 자료구조를 생각해보았습니다. 좀 더 생각해보니 말이 얼마나 혹은 어떻게 쌓이든 바닥에 놓인 말과 가장 높이 놓인..