코딩하는 해맑은 거북이

해당 글은 백준 1766번 '문제집' 문제를 다룬다. 문제 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 설명 해당 문제는 위상 정렬 알고리즘으로 해결할 수 있다. 위상 정렬은 순서가 정해져있는 작업을 차례로 수행할 때 사용한다. 위상정렬의 전체적인 과정은 아래와 같다. 0. 그래프와 진입차수 리스트를 생성한다. 1. 진입차수가 0인 정점을 큐에 삽입한다. 2. 큐에서 원소를 꺼내 해당 원소와 연결된 간선을 모두..

해당 글은 백준 1562번 '계단 수' 문제를 다룬다. 문제 https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 설명 해당 문제를 처음 봤을 때, 예전에 풀어본 문제와 비슷한거 같아 찾아보니 이전의 쉬운 계단 수 문제를 풀었었다. 쉬운 계단 수 문제와 다른 점은 0~9까지 숫자가 어떤 수가 포함되어 있는지를 확인해야 한다. 이때 비트마스킹을 이용한 DP로 이진수로 표현해서 연산하는 방법이 있다. 먼저 0~9까지를 다 포함하는 계단 수를 구하려면 dp 배열이 (n+1) x 10 x 1023 이 되어야 한다. 다음 한자리 수는 다 1로 초기화하고, 다음 자리수부터 3중 fo..

해당 글은 백준 1806번 '부분합' 문제를 다룬다. 문제 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 설명 처음엔 시간 제한이 0.5초여서 안될 것 같았지만, 배열의 start~end까지 슬라이스로 인덱스 접근을 이용하여 풀었는데 시간초과가 발생했었다. 시간을 단축할 수 있는 방법으로 투 포인터 알고리즘이 있다. start와 end의 투 포인터 변수를 생성하고, start과 end 위치에 따른 total이 s보다 작다면, e..

해당 글은 백준 18111번 '마인크래프트' 문제를 다룬다. 문제 https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 설명 해당 문제는 간단한 구현 문제인데, 시간초과를 해결하는데 애를 먹었다. 구현 알고리즘은 배열에 저장된 높이들 중 최소와 최대를 구하여, 해당 높이 범위로 for문을 돌려 각 높이일 때의 걸린 시간을 구하는 것이다. 이때 구한 시간들 중 가장 최소 시간을 정답으로 저장하면 된다. 이때, 처음으로 배열의 행과 열의 인덱스로 접근..

해당 글은 백준 1300번 'K번째 수' 문제를 다룬다. 문제 https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 설명 해당 문제는 2중 for문으로 행렬을 만들고, 인덱스로 접근했을땐 메모리 초과가 떠서 해당 방법으론 풀 수 없었다. 이진탐색으로 nxn 행렬에서 어떤 수보다 작거나 같은 값이 몇 개인지 찾아야 몇 번째 숫자인지 알 수 있다. 예를 들어, 3x3 행렬의 값들을 리스트로 정렬해보면 [1, 2, 2, 3,..

해당 글은 백준 2512번 '예산' 문제를 다룬다. 문제 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 설명 해당 문제는 이진탐색으로 해결할 수 있는 문제이다. 주의할 점은 total을 구할 때, mid와 arr[i] 중 최소값으로 구해야하는 점이다. 또한, total이 m보다 크다면, 예산을 초과한 것이므로 end를 mid-1로 줄여서 이진탐색을 다시 해야한다. 코드 n = int(input()) arr = list(map(int, i..