코재의 블로그

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 알고리즘은 간단하게 dfs를 사용하여 풀었다. 하지만 위 아래 좌 우 모두 함수를 구현해주어야하므로 조금은 귀찮았다. 큰 알고리즘은 방향으로 민다 -> 방향으로 합친다 -> 다시 방향으로 밀어준다 이다. 먼저 빈칸이 없도록 밀고자하는 방향으로 다 몰아준다. 그리고 밀고자하는 방향의 제일 윗부분 부터 바로 뒤의 수가 자신이랑 같으면 합쳐준다. 합쳐진 수들은 0으로 되기 ..

KMP관련 문제를 풀다가 라빈 카프 알고리즘이란 것이 있다는 것을 알았다.KMP알고리즘과 동일하게 문자열 매칭 알고리즘이다. 보통 KMP를 자주 쓰지만 그 못지 않게 꽤 빠르게 작동한다. 라빈 카프 알고리즘은 특이하게 해시를 사용한다. 해시의 장점의 경우 단순한 해시 알고리즘의 시간 복잡도는 O(1)이란 것이다. 지금까지 해시를 잘 사용하지 않았기 때문에 SWEA에서 해시 관련 문제들을 푸는데 어려움을 겪고 있다. 라빈 카프 알고리즘은 그렇게 어렵지 않으니 간단하게 설명하고 코드로 넘어가겠다. 간단한 예제로 abc를 들겠다. 이진수 변환하듯이 뒤에서부터 각 자릿수 제곱승 * 각 자리의 수자를 다 더하여주면 abc = a*2^2 + b*2^1 + c*2^0이런 식으로 해시 값으로 나타낼 수 있다. 만약 a..

https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net A. 사용한 알고리즘 및 자료구조 heap을 사용한 priority queue를 사용하였다. i-l+1~i까지 최솟값을 구하면 되기 때문에 일단 들어오는 모든 원소들을 우선순위 큐에 넣어주었다. 구조체를 만들어서 원소 자체의 값과 원소가 언제 들어왔는지 알려주는 변수를 만들었다. 만약 i-l+1의 범위에서 벗어나는 원소가 우선순위 큐의 top에 존재할때 범위 안에 ..

한동안 SWEA와 연구실 인턴을 병행하다보니 백준을 풀 시간이 거의 없었다. SWEA는 되도록 유출이 되지 않도록 올리지 않기 때문에 백준 문제를 풀고 후기를 쓴다. https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net A. 사용한 알고리즘이나 자료구조 먼저 heap을 사용하였다. min heap과 max heap 둘다 사용해주었다. 여기서 가운데를 찾아야 하기때문에 첫번째 원소를 max heap에 저장을 해준다. 핵심 개념은 max..

링크드 리스트야 워낙 흔하게 쓰이는 것이라 그렇게 놀라웠던 건 없었다. 하지만 알고리즘 대회 용으로 배운 메모리풀 방식은 인상깊었다. 구조체를 미리 정적배열로 할당을 해준후 필요할때마다 하나씩 꺼내서 사용하는 식이다. 간단하게 struct Node { int data; Node* next; }; Node node[MAX_NODE]; 위와 같이 선언을 해준다면 새 노드를 추가 할때마다 동적할당을 통하여 할당해주는 것이 아닌 이미 할당이 되어있는 빈 노드들 중에서 하나를 가져와서 쓰는 것이다. 동적할당 한것 마냥 똑같이 data를 넣어주고 next값으로 다음 노드를 포인팅하게 초기화를 진행해주면 된다. 이렇게 진행하면 매번 동적할당을 할 필요없이 간단하고 빠르게 바로 새 노드를 가져올 수 있는 것이다. 하지..

어쩌다보니 삼성에서 진행하는 알고리즘 캠프를 접할 기회가 생겼다. 오늘 1일차로 오리엔테이션과 Bitmap을 관련하여서 배웠는데 그저 단순하게 생각하던 bitmap이 아닌 조금은 신기했다. 오늘 코딩하면서 제일 신기했던건 &인것 같다. 어떻게 보면 매우 간단해보이고 언제나 사용되었던 것인데 제대로 활용을 못하고 있었다. 예를 들어서 16명의 사람이 있고 몇명이 참석했는지 알고 싶을때 그냥 당연히 16개짜리 배열을 선언하고 거기에 값을 보아 있으면 참석했고 없으면 참석하지 않았다로 판별하고 그 수를 찾았을것 같다. 하지만 만약 bitmap을 사용해보면 너무나도 쉬워진다. 먼저 16개의 비트로 나타내면 0000 0000 0000 0000 으로 초기화를 해준다. 만약 참석하였을 때 1로 바꿔줄 경우 0100 ..

https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. 아이디어 및 사용한 알고리즘이나 자료구조 dp로 무작정 풀기엔 n이 너무 크기 때문에 분할정복을 사용하려고 했다. 그래서 아래의 그림과 같이 간단한 행렬로 접근을 해보았다. 하지만 시간초과가 떴고 뭔가 이상했다. 1000000으로 나눈단 것이 이상해서 혹시나 반복이 되나 싶어서 피보나치 반복에 대해 검색해봤는데 역시나였다. 1000000으로 나눈 나머지의 피보나치는 주기가 1500000이었다. 결국 처음부터 dp로 1500000까지 구해준후 출력때 n을 1500000을 나..

https://www.acmicpc.net/problem/13430 13430번: 합 구하기 첫째 줄에 k와 n이 주어진다. (1 ≤ k ≤ 50, 1 ≤ n ≤ 1,000,000,000) www.acmicpc.net 1. 아이디어 및 사용한 자료구조나 알고리즘 보자마자 당연하게 dp를 떠올렸다. 간단하게 A[n][k] = A[n][k-1] + A[n-1][k] 로 풀 수 있지 않을까라는 생각을 가지고 시작했다. 하지만 생각해보니 배열을 할당할 수 있는 범위를 훌쩍넘어가기 때문에 dp는 사용할 수 없었다. 그래서 수학적으로 접근을 해보았다. 하지만 이것 또한 배열의 한계를 넘어가기 때문에 마지막으로 생각한것은 행렬을 사용하는 것이었다. 거듭 제곱을 사용한다면 k의 배열은 [50][50]이기 때문에 배열의..

https://www.acmicpc.net/problem/23291 23291번: 어항 정리 마법사 상어는 그동안 배운 마법을 이용해 어항을 정리하려고 한다. 어항은 정육면체 모양이고, 한 변의 길이는 모두 1이다. 상어가 가지고 있는 어항은 N개이고, 가장 처음에 어항은 일렬로 바 www.acmicpc.net A. 아이디어 및 사용한 자료구조와 알고리즘 특별히 사용한 자료구조나 알고리즘은 없다. 이 문제의 경우 특별한 것이 아닌 말 그대로의 구현을 원하는 것 같았다. 얼마나 효율적으로, compact하게 구현을 하느냐에 달려있는 듯 했다. 첫번째 정리를 하는 함수 setup(), 두번째 정리를 하는 함수 half_setup() 그리고 마지막으로 setup작업이 끝날 때마다 물고기를 나누고 1자로 다시 ..

이제 슬슬 감을 찾기 위해서 저번보다 난이도를 조금 올려보았다. https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net A. 아이디어 및 사용한 자료구조 와 알고리즘 문제를 처음 딱 읽자마자 들었던 생각은 물고기들을 옮기는 함수와 DFS, 그리고 각 화살표를 나타내는 vector 배열을 생각했다. 주어지는 물고기들의 번호는 1부터 16까지 정해져 있기 때문에 구조체를 사용하여 각 물고기들의 위치와 방향을 저장하고 있으면 순서대로 물고..