코딩기록

https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 처음 생각했던 풀이는 영화제목이 1666, 2666, 3666, ... 으로 증가하니까 그냥 666 앞에 입력받은 숫자만 붙이면 되겠다! 라고 생각해서 코드를 제출했더니 틀렸다고 나왔다. 코드를 짤 때부터 너무 간단하다고 생각하긴 했다...^^ 틀리고 나니 문제를 잘못 이해한 것 같아서 블로그를 찾아봤다. n = int(input()) movie = str(n-1) + '666' print(mo..

https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 이 문제는 브루트포스 문제로 모든 경우의 수를 탐색해보면 되는 문제였다. 정말 하나씩 다 확인해보는 방법을 선택했다. 시작하는 글자가 'W' 일 때 0번째줄부터 시작한다고 할 때 짝수줄은 'WBWBWB...' 이고, 홀수줄은 'BWBWBW...' 으로 되니까 인덱스로 하나씩 확인해서 제대로 체스판이 칠해져있는지 확인하려고 했다. 행(i)과 열(j) 인덱스를 살펴보면 규칙을 찾을 수 있었다...

https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 이 문제는 브루트포스 문제였다. 그래서 그냥 무차별로 대입해서 찾으면 되는 문제였다. n = int(input()) persons = [] # 사람들의 키와 몸무게 정보를 담는 리스트 # 키와 몸무게 입력받기 for _ in range(n): person = list(map(int, input().split())) persons.append(person) # 전체 탐색 수행 for m..

https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net # 하노이 탑 알고리즘 1. 1번 기둥의 n-1 개의 원반을 2번 기둥으로 옮긴다. 2. 1번 기둥에 남아 있는 가장 큰 원반을 3번 기둥으로 옮긴다. 3. 2번 기둥의 n-1개의 원반을 3번 기둥으로 옮긴다. num = int(input()) def hanoi(n, p_from, p_to, p_mid): if n == 1: # 원반이 1개이면 무조건 원반을 1번에서 3번으로 옮긴다...

https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 이 문제는 이해하는게 어려웠던 문제였다. 이해하는데 시간이 좀 걸렸다. 이 문제를 푸는데는 여러 가지 방법이 있는데 나는 상중하로 구간을 나눠서 별을 찍는 방식을 선택했다. 구간을 상중하로 나누어 재귀함수를 통해 구해진 별을 붙여 나간다. 코드가 직관적이어서 이해하기 좀 더 쉬웠던 것 같다. print(L) 을 해보면 어떻게 재귀함수가 돌아가는지 이해하는데 도움이 될 것..

https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 처음에 제출했을 때 시간 초과가 났다! 이유를 알아보니 파이썬은 input().split() 으로 입력하는 경우 입력량이 많기 때문에 시간 초과가 나는 것이었다... 시간 초과가 나지 않으려면 sys.stdin.readline() 을 사용해야 한다! 이 문제는 최단 거리를 찾는 문제로 너비 우선 탐색(BFS)을 이용하면 풀 ..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 이 문제는 전형적인 최단 경로 문제이며 플로이드 워셜 알고리즘을 이용하면 수월하게 풀 수 있었다. 플로이드 워셜 알고리즘을 알아야 풀 수 있어서 이 알고리즘을 모른다면 아래의 링크를 참고하면 좋을 것 같다. https://it-garden.tistory.com/247 플로이드-워셜(Floyd-Warshall) 알고리즘 이론과 파이썬 구현 플로이드-워셜(Floyd-Warshall) 알고리즘 플로이드..

https://www.acmicpc.net/problem/18406 18406번: 럭키 스트레이트 첫째 줄에 점수 N이 정수로 주어진다. (10 ≤ N ≤ 99,999,999) 단, 점수 N의 자릿수는 항상 짝수 형태로만 주어진다. www.acmicpc.net # 입력받는 부분 n = str(input()) # 왼쪽과 오른쪽 나누기 left = n[:len(n)//2] right = n[len(n)//2:] l_sum = 0 # 왼쪽의 각 자릿수 합 r_sum = 0 # 오른쪽의 각 자릿수 합 # 왼쪽과 오른쪽의 합 구하기 for i in range(len(left)): l_sum += int(left[i]) r_sum += int(right[i]) # 결과 출력 if l_sum == r_sum: pri..

www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net import heapq # 입력받는 부분 n = int(input()) cards = [] for i in range(n): heapq.heappush(cards, int(input())) answer = 0 # 최소 비교 횟수 # 최소 비교 횟수 계산 while len(cards) != 1: first = heapq.heappop(cards) second = heapq.heappop(cards)..

www.acmicpc.net/problem/18310 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net # 입력받는 부분 n = int(input()) house = list(map(int, input().split())) # 정렬 house.sort() # 안테나를 설치할 집 출력 print(house[int((n-1)/2)]) # print(house[(n-1)//2]) 처음에는 for문을 사용하여 배열을 돌면서 각 집에서 다른 집들 간의 거리를 구하고 그 거리들 중에서 최소값을 구해야한다고 생각했습니다. 이 방법으로 코드를 짜다보..