오답노트

문제 https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 풀이 0층부터 256층까지 모두 둘러보면서 만들 수 있는 최소시간에 만들 수 있는 최고층을 찾으면 된다. 이때 블럭을 제거하면 다시 그 블럭을 사용할 수 있는데, 이 조건을 충족시키는 층끼리만 비교하면 된다. import sys N, M, B = map(int,sys.stdin.readline().split()) map_list = [] ans = 1e9 idx = 0 for _ in ra..

문제 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 풀이 틀린 풀이 어렵게 풀려고 했다. 채널에 가까운 작은 수와 큰 수를 찾았는데 너무 처리해야할 예외가 많았다. 그래서 멘탈이 터져서 포기.. import sys N = sys.stdin.readline().rstrip() M = int(sys.stdin.readline()) if M > 0: btn_list = list(map(int,sys.stdin.readline().s..

문제 https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 풀이 DP 테이블 정의까지는 생각했으나 점화식을 찾지 못했다. 0부터 찾아가는게 아닌 N부터 점차 찾아오는 식으로 풀이해야한다. 우선 팰린드롬의 특징부터 살펴보자 1. 팰린드롬은 거꾸로 해도 원본과 같은 수열을 이룬다 (테넷) 2. 팰린드룸은 양끝의 값이 같다. 3. 팰린드룸은 양끝을 제외한 나머지 수열도 대칭을 이룬다. (1번과 같다) 4. 수열의 길이가 2일 때는 2번만 고려한다. DP로 풀 수 있는 힌트는 3번에 있다. 아래..

문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 실버까지의 DP는 값을 직접적으로 이용했지만 골드부터는 수치적인 제한이 생기면서 유형이 바뀐듯하다. 처음엔 물건들로 2차원 배열을 생각했으나 물건을 선택하는 것과 하지 않는 것을 분리하지 못했다. 1. row는 주어지는 물건의 개수 N col은 0부터 가방의 제한 무제 K의 2차원 리스트를 만든다. 2. 현재 물건을 넣을..

문제 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 1. 인덱스를 수월하게 사용하기 위해 더미 문자열을 입력 문자열 앞에 추가한다. 2. 이중 for를 돌면서 각 문자를 서로 비교한다. DP 테이블에는 현재까지 만들 수 있는 공통 부분 수열의 개수를 넣는다. 2-1. 만약 i위치와 j위치에서 두 문자가 같다면 [i-1][j-1]에 값에 1을 더한다. (두 문자열의 각각 이전 문자까지의 공통 문자열 길이에 현재 문자를 더한 것이다. ) 2-2. 만약 i위치와 ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42627?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 1. 주어지는 작업은 정렬되어 있다는 가정이 존재하지 않는다. 그러므로 시작시간을 기준으로 정렬한다. (난 그냥 heapq를 사용해서 오름차순 정렬을 했음) 2. 정렬된 작업들에서 마지막에 수행된 작업시간 이전에 요청된 작업을 뽑는다. 3. 뽑은 작업들을 다시 heapq에 담는다 대신 작업의 소요시간 순으로 오름차순 정렬될 수 있도록 한다. 4. 그 중 가..

문제 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 풀이 우선 최소 힙과 최대 힙을 각각 만든다. 기본적인 아이디어는 두 힙을 서로 동기화 시키는데에 있다. 하지만 무조건 동기화만 시킨다면 시간 초과로 문제를 풀 수 없다. 지금부터는 자명한 정답들에 대한 내 생각이다. 시간 초과를 극복하기 위해서는 문제에서 요구하는 조건만 충족시키는 한에서 두 힙을 동기화 시키는 것이 가장 적절해 보인다. 즉, 두 힙을 무조건 동기화 시킬 필요가 없다는 것이다. 아래 사진은 예제 입력1에 두번째 케이스에서 정답을 출력하..

문제 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이 1. 회의실 배정이 끝나는 시간을 오름차순 정렬한다. 끝나는 시간이 같다면 시작하는 시간을 오름차순 정렬한다. 2. 정렬된 상태에서 가장 먼저 시작하는 회의를 선택한다. 3. 문제의 조건에 맞춰 선택된 회의의 끝나는 시간보다 같거나 큰 시간의 시작 시간을 가진 회의를 선택한다. 4. 3번을 계속 반복하며 회의를 선택한다. 위 과정을 통해 예제 입력1을 풀이한 결과는 다음과 같다. 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14 (8,11),(8,12) 같은 경우 2번을 통해 (8,11) 선택해야한다. 코드 import sys ..

문제 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀이 예제입력과 내가 자체적으로 만든 Test Case를 통해 풀이할 것이다. 예제입력 예제입력은 위 사진의 표와 같이 입력된다. 1. dp 테이블을 만든다. 이때 기존에 주어진 n x m 보다 큰 (n+1) x (m+1) 크기의 테이블을 만든다. 테이블의 원소는 모두 0으로 초기화 한다. 아래 사진에는 설명을 위해 입력 테이블에 행과 열을 하나씩 추가했다. 2. dp 테이블 기준으로 (1,1)부터 2x2 사각형의 오른쪽 아래 지점으로 가정한다. 그리고 한 칸씩 방문하여 입력 테이블에 1인 지점에서 점화식을 계산한다. 점화식은..

문제 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 풀이 1. 이번 예시에서는 동전의 종류는 2원, 4원, 7원이고 이를 사용해서 11을 만드는 경우의 수를 찾아야한다. 우선 dp 테이블을 2차원 배열로 row는 가지고 있는 동전의 종류 col은 0부터 M까지로 만든다. 2. 동전의 종류 중 가장 작은 값인 2를 초항으로 선택한다. 2로 0원부터 11원까지 만들 수 있는 경우의 수를 모두 입력한다. 여기서 0원을 만들 수 있는 경우의 수는 무조건 1이다. (각 동전을 사용하지 않는 경우에 0..