레벨업 일지

문제 11058번: 크리보드 (acmicpc.net) 11058번: 크리보드 N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl www.acmicpc.net 알아야 할 개념 점화식 dp 풀이 버튼 4가지의 역할은 다음과 같다. A를 출력 전체 선택 선택 영역 복사 붙여넣기 알수 있는 규칙은 단순히 A를 추가하면 현재 길이 + 1 가 되고 , 붙여넣기를 하면 현재 단계 i 에서 3번째 전 단계의 것을 가져와서 붙여넣기를 한다. 붙여넣..

문제 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 알아야 할 개념 dfs 백트래킹 코드 dfs 탐색시 주의점을 알려준 문제 예제에 사이클 그래프가 보여서 난이도가 높은줄 알고 당황했었다. 해당 문제는 모든 정점에서 dfs 를 돌리는것으로 간단히 풀이 가능하다. 풀이는 다음과 같다. 주어진 그래프를 무방향 인접 그래프로 구현한다. 모든 정점에대해 DFS 탐색을 한다. DFS 탐색 깊이가 4 ( 시작 = 0 ) 이상이면 탐색을 종료하고 1 리턴한다. 그렇지 않으면 0 리턴한다. 백트래킹을 연습하는 문제라고 생각한다. 플래그를 세워서 dfs 탐색 종료..

문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 알아야 할 개념 DFS 백트래킹 풀이 핵심은 치킨집을 (Math.min (M, 치킨집 개수 ) ) 만큼 뽑았을 때 도시 치킨 거리의 수를 모두 구하면 되는 문제. 나이브한 브루트포스 풀이 알고리즘은 다음과 같다. 일정 개수 (min(주어진 M, 치킨집 개수 )) 만큼 치킨집을 뽑는다. 모든 집의 치킨 거리를 계산한다. 도시 치킨 거리를 계산한다. 알고리즘 (1,2,3) ..

문제 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 알아야 할 개념 다이나믹 프로그래밍 풀이 풀이는 다음과 같다. dp 배열을 하나 만들고 최대 값 10001로 채운다. dp 배열에 (idx == 3의 배수)를 3으로 나눈 몫으로 채운다. dp 배열을 순회 하면서, dp[i-5] (이전에 최소값 봉지의 개수) + 1 , dp[i] (현재 개수 ) 두 값의 최솟값으로 업데이트한다. dp[ 주어진 숫자 ] 를 리턴한다. 참고 dp[i-5] + 1 을 한 이..

문제 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 풀이 수학 문제를 풀 때 1 부터 n 까지의 수를 for문을 돌리면서 누적합을 하고 싶은가? 아님 n까지의 수의 합 n*(n+1)/2 으로 한 번에 도출 하겠는가? 당연히 후자일 것이다. public int getSum(int n){ int sum = 0 ; for(int i = 1; i < n+1 ;i++) sum += i; return sum; } publi..

문제 11501번: 주식 (acmicpc.net) 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 풀이 우선순위 큐를 이용하여 풀이한 로직은 다음과 같다. O ( N^2) 1. 우선순위 큐에 배열값을 다 담는다. 2. 방문 해시맵을 만들어 아직 남아있는 개수이면, 해당 key 방문처리하고 꺼낸다. 3. 현재 값이 max Number 보다 작으면 합을 더한다. 4. 현재 인덱스가 maxIdx보다 크면, 최댓값을 for문으로 구한다. 5. 배열 끝까지 2..4 로직을 반복하고 답을 구한다. 그런데 이 ..

문제 https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 풀이 최대한 적게 멀티플러그를 빼는 문제. 게시판 반례 참고해서 코드 수정 하였다. 풀이는 다음과 같다. 1. 현재 멀티탭이 구멍보다 작을 때 플러그를 꽃는다. 2. 멀티탭 남는 구멍이 없어 플러그를 빼야 하면, 다음 등장하는 인덱스가 가장 큰 것을 플러그에서 제거한다. 3. 이미 멀티탭에 있는 번호가 나왔으면, 다음 등장 인덱스를 업데이트 해준다. 먼저 해시맵을 사용해서 현재 기준 cur ..

문제 https://www.acmicpc.net/problem/25947 25947번: 선물할인 입력은 표준입력을 사용한다. 첫 번째 줄에 선물의 개수를 나타내는 양의 정수 $n$ ($1 ≤ n ≤ 100\,000$), 예산을 나타내는 양의 정수 $b$ ($1 ≤ b ≤ 10^9$), 반값 할인을 받을 수 있는 최대 선물의 수를 www.acmicpc.net 조건을 만족하며 최대로 살 수 있는 선물의 수를 출력한다. 풀이 풀이는 다음과 같다. int left, right 를 선언해주어 left .. right 범위 내의 윈도우 슬라이드에 담긴 물건들을 "할인해서 구매한 물건들" 로 정의하였다. 1. 주어진 배열 오름차순 정렬 2. 먼저 할인 가능하면 가능한 만큼 일단 구매한다. 3. 더 이상 할인 할 수 ..