황태건블로그

https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 동적 프로그래밍을 사용하여 푼다. 길이 i의 타일을 만들 수 있는 경우의 수를 tile[i]이라고 할 때, tile[i]은 다음과 같이 계산할 수 있다. tile[i] = (tile[i-1]에 1을 추가하는 경우의 수) + (tile[i-2]에 00을 추가하는 경우의 수) tile[i-2]에 11을 추가하는 경우는 중복되므로 제외한다. 결국 추가하는 경우의 수를 어떻게 계산하느냐가 문제의 핵심인데, 여..

https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 입력의 개수가 많아 map 컨테이너를 사용해 풀었으나 map은 키와 이에 대응하는 값이 있을때 쓰는 컨테이너고 키의 존재 유무만 알아보기 위해서는 set을 사용하면 된다. (사용법은 유사, set이 tree 구조) 이진탐색으로도 풀 수 있다고 하여 이진탐색도 적용해보았다. 시간 초과가 떴는데, 찾아보니 시간 초과의 원인이 함수를 호출할 때 마다 크기가 큰 배열을 그대..

https://www.acmicpc.net/problem/20920 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 알고리즘 보다는 C++의 STL 기능을 이해하고 있어야 풀 수 있는 문제 이 문제에서는 문자열이 등장한 횟수를 기록하고 확인해야 하는데 vector만으로는 시간 내에 해결할 수 없다. 따라서 map 컨테이너를 사용한다. 먼저 단어를 입력받아, 일정 길이 이상의 단어에 대해 해당 단어가 map에 존재하는 지 확인(count != 0..

https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 분할 정복 알고리즘을 이용하는 문제이다. n = 3인 기본 패턴을 출력하는 데 줄바꿈이 들어가므로, 재귀함수에서 직접 문자열 출력을 해서는 안 되며 배열에 값을 저장한 뒤 재귀가 끝나면 한번에 출력해야 한다. 크기가 nXn인 2차원 char 배열을 생성하고 n에 대해 재귀함수를 호출한다. 이 재귀함수는 크기가 nXn인 정사각형을 가로세로 3등분하여, 총 9개의 작은 정사..

https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 동적 프로그래밍을 통해 풀 수 있는 문제이다. 단순히 aCb를 계산하면 되지만, 조합의 계산은 O(n!)을 기반으로 하기 때문에 n이 20만 돼도 오버플로우가 발생할 수 있다. 따라서 조합의 기본 성질인 aCb = (a-1)Cb + (a-1)C(b-1)를 활용한다. ex) 5C2 = 4C2 + 4C1 배운 내용 : 동적 프로그래밍을 통한 큰 수 계산

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 그래프 탐색과 동적 프로그래밍 기법을 활용해 풀었다. 각 타워의 개별 건설 비용을 저장할 1차원 cost 배열, 타워 간의 건설 순서를 저장할 2차원 order 배열, DP의 optimal substructure 생성을 위한 1차원 sum 배열, 그래프 탐색을 위한 1차원 visited 배열 총 4가지 배열을 사용했다. optimal substructure는 다음과 같이 설계한다. i번째 건..

https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 이번 문제에서는 나이를 기준으로 입력값을 정렬하되 나이가 같다면 이름을 비교하지 않고 기존 입력 순서를 유지해야 한다. 즉, stable sort를 지원하는 정렬 방식을 사용해야한다. 내가 구현할 수 있는 평균 시간복잡도 O(n log n)의 정렬은 힙, 병합, 퀵 정렬이다. 이 중 stable sort를 지원하는 정렬은 병합 정렬이므로 문제 해결을 위해 병합 정렬을 구현했다. 병합 정렬의 수행 방식은..

https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제에서 제시한 대로 브루트 포스 방식으로 해결하였다. 2차원 캐릭터 배열을 입력받은 후, check8x8 함수를 이용해 현재 행과 열을 시작 위치로 하는 8x8 배열에 대해 다시 칠해야 하는 색깔의 수를 계산한다. 정상적인 체스판에서, 대각선으로 이동할 수 있는 모든 정사각형의 색깔은 서로 같다. 또한 시작 위치 0,0에서 대각선으로 이동할 수 있으면 중첩 loop문에서 i+j가 짝수이며..

https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 분할 정복을 연습하기 위한 첫 번째 문제 쿼드트리는 분할이 4개씩 되는 알고리즘을 의미하는 듯 싶다 알고리즘 slice_blue (int row_start, int row_end, int col_start, int col_end, int res) //해당 구간에서의 파란색 종이의 수를 구하는 함수 //base condition if(길이 = 1) return 해당 타일의..