https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 1. Logic 이전 가장 긴 증가하는 부분 수열 문제에서는 DP를 사용해서 풀었다. DP를 사용하는 풀이에서는 전체를 돌면서 확인 하며 메모이제이션 했기때문에 시간복잡도가 O(N^2)이었다. 하지만 이 문제에서는 입력값이 엄청 많기 때문에 N^2으로 풀지 못하기 때문에 시간복잡도가 O(nlogn)을 가지는 이분탐색 기반으로 풀어야 한다. binary search를 구현해서 푸는 방법과 C++의 ..
코딩테스트
코딩테스트를 처음 준비한다면 언어 기초 → 배열·문자열과 자료구조 → 완전탐색 → BFS·DFS → 이분탐색·그리디 → 동적계획법 순서로 공부해 보자. 아래는 직접 문제를 풀며 정리한 학습 방법과 단계별 연습 경로다. 기업별 출제 빈도를 집계한 순위는 아니며, 지원하는 시험의 안내와 자신의 약점에 맞춰 순서를 조절하면 된다.처음 시작할 때의 공부 순서언어와 복잡도: 입출력, 반복문, 함수, 정렬을 익히고 입력 크기로 가능한 시간복잡도를 판단한다.배열·문자열·자료구조: 인덱스와 경계값, 스택·큐·해시를 연습한다. 백준 1475 방 번호로 개수 세기를, 2346 풍선 터뜨리기로 덱 활용을 연습할 수 있다.완전탐색과 그래프: 모든 경우를 빠짐없이 만드는 방법부터 익히고 방문 배열을 사용하는 BFS·DFS로 넘..
https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 1. Logic - 입력수가 10억을 넘기 때문에 입력만으로 시간복잡도가 터진다. 그래서 시간복잡도가 O(logN)인 자료구조인 priority_queue를 썼다. 그렇기 때문에 시간복잡도 log10억은 9이다. 작은 값부터 탐색해야 하기 때문에 priority queue에 greater인자를 넣어 오름차순으로 정리해주었다. 앞의 원소들 부터 차례대로 탐색하면서 1. 입력받은 수의 전체 합이..
https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 1. Logic 비슷한 문제인 벽 부수고 이동하기 1(boj - 2206) 과 비슷하게 풀어보았다. 2206번 문제에서와 마찬가지로 vis배열 설정이 중요하다. 이번 문제에서는 부실 수 있는 블록의 갯수를 유동적으로 입력받기 때문에 BFS에서 처음 시작구간을 queue에 넣을 때 부실수 있는 block의 갯수를 입력받은 k만큼 넣어준 상태로 0이 될때까지 부셔나..
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 1. Logic - 방문처리를 하는 vis배열을 2차원으로 좌표로만 구성하는 것이 아닌 3차원으로 형성하여 벽을 뚫을 수 있는지 아니면 이전에 뚫은 적이 있는지 확인한다. 부분문제를 나눠보자면 1. 벽을 뚫을 기회가 있을 때 벽을 만난경우 2. 갈 수 있는 길이면서 방문한적 없는 경우 이렇게 2가지로 나눌 수 있다. 2. Code #include using namespac..
https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 1. Logic - 인덱스를 가르키는 두개의 포인터 변수(start, end)를 선언 한 뒤 원하는 수보다 sum이 작으면 다음 배열로 end를 옮기고 vec[end] 더해주고 크면 vec[start]를 빼주고 start 포인터를 하나 더해준다. 해당 문제는 투포인터를 설명하면서 똑같이 풀이해놨으니 투포인터를 잘 모른다면 다음 글을 참고하면 좋을 것 같다!..
https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 1. Logic - 인덱스를 가르키는 두개의 포인터 변수(start, end)를 선언 한 뒤 원하는 수보다 sum이 작으면 다음 배열로 end를 옮기고 vec[end] 더해주고 크면 vec[start]를 빼주고 start 포인터를 하나 더해준다. Testcase 하나를 예시로 들어보면 Testcase 10 4 5 1 3 5 10 7 4 9 2 2 여기서 더해서 4가 되는 연속되는 인..
https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 1. Logic - 스티커를 뜯으면 상하좌우 한개씩은 무조건 못사용하기 때문에 함수를 작성할때 이전에 어떤 스티커를 골랐는지, 어디 위치에 있는 스티커를 골랐는지 넘겨준다 DP table[어떤 스티커를 골랐는지][스티커의 index] 0 : 스티커를 안고르고 지나침 1 : 스티커의 y값이 0인 스티커를 선택 2 : 스티커의 y값이 1인 스티커를 선택 2. Code #include usi..
https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 1. Logic - 입력을 받으면서 가장 큰 값과 해당 값의 인덱스 번호를 저장해놓는다. - 저장해 놓은 가장 큰 값의 인덱스를 기준으로 앞에서부터 인덱스까지 돌며 빗물이 찼을 때 가장 최댓값을 구하고 똑같이 뒤에서부터 인덱스 까지 돌며 최대값을 구한다. 이후 각 블록의 높이를 다 더한값을 최댓값에서 빼주면 빗물의 총량을 구할 수 있다. 14719번 문제가 어렵다면 2304 창고..
https://www.acmicpc.net/problem/1461 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 1. Logic - 0에서부터 왔다가 돌아와서 책을 다시 가져가야 하기 때문에 모든 (경로값 * 2)를 하게된다. 그렇기 때문에 입력을 모든 값중 절댓값이 가장 큰 경로에 있는 책을 제일 마지막에 가져다 놓아서 * 2를 하지 않아야겠다는 생각을 했다. 1, 양수를 저장하는 positive배열과 음수를 저장하는 negative 배열을 받아서 각각 저장하며 절댓값을 통해 절댓값이 가장 큰 값을 저장해놓는다..
