코딩하는 해맑은 거북이

해당 글은 백준 1018번 문제 '체스판 다시 칠하기'를 다룬다. 문제 https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 설명 입력된 보드판에서 8x8 크기의 체스판으로 행과 열을 하나씩 이동해가며 두가지 케이스를 비교하면 된다. 한 행의 8개의 값은 ['W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'] 또는 ['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W']를 가지게 된다. 이러한 두가지 케이스를..

해당 글은 백준 10845번 문제 '큐'를 다룬다. 문제 https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 설명 해당 문제는 이전의 백준의 스택문제와 같이 입력 시간을 줄이기 위해 sys.stdin.readline()으로 입력을 받는다. 나머지는 큐의 조건에 맞게 기능을 구현해주면 된다. 코드 import sys from collections import deque n = int(sys.stdin.readline()) queue ..

해당 글은 백준 1920번 문제 '수 찾기'를 다룬다. 문제 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 설명 해당 문제는 리스트의 모든 원소값을 전부다 비교하면 시간초과가 발생한다. 리스트에 특정값이 있는지 확인하는 방법 중 시간을 줄일 수 있는 알고리즘으로 이진탐색이 있다. 이를 이용해서 시간복잡도를 O(MlogN)으로 줄일 수 있다. 이진탐색을 하기 위해서는 비교할 리스트는 정렬이 되어있..

해당 글은 백준 11047번 문제 '동전 0'을 다룬다. 문제 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 설명 해당 문제는 그리디 알고리즘으로 풀 수 있는 문제이다. 입력 조건에서 오름차순으로 입력된 동전은 이전 동전의 배수이기 때문이다. 그래서 동전의 크기가 가장 큰 순서부터 나눠주면서 count 해주면 된다. 코드 n, k = map(int, input().split())..

해당 글은 백준 10828번 문제 '스택'을 다룬다. 문제 https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 설명 해당 문제는 각 명령어마다 쉽게 구현할 수 있는 문제이지만 시간 초과 문제가 떴었다. 이유를 알아보니 반복문을 통해 input을 받을 때는 import sys 모듈을 불러 sys.stdin.readline()을 통해 입력을 받으면 입력시간을 줄일 수 있다. 코드 import sys n = int(sys.stdin.r..

해당 글은 백준 2839번 문제 '설탕 배달'을 다룬다. 문제 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 설명 DP 문제로 거스름돈 최소갯수를 구하는 방법대로 구하였다. dp[j] = min(dp[j], dp[j-3]+1, dp[j-5]+1) 식으로 구하면 된다. 출력할 때 dp[n] 값이 5001이상이라면 -1을 출력해준다. 코드 n = int(input()) dp = [5001]*5001 dp[0]=0 arr = [3, 5] for i in ar..