코딩기록

https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net import sys from collections import Counter n = int(sys.stdin.readline()) # 수의 개수 nums = [] # 숫자 리스트 # 숫자 입력 받기 for _ in range(n): nums.append(int(sys.stdin.readline())) # 산술 평균 print(round(sum(nums) / n)) # 중앙값 nums.sort() print(nu..

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://programmers.co.kr/learn/courses/30/lessons/49190 코딩테스트 연습 - 방의 개수 [6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0] 3 programmers.co.kr 이 문제는 Level5 답게 굉장히 어려웠다.. 그래서 어떻게 방의 개수를 셀 수 있는지 전혀 생각나지 않았다... 그래서 문제를 풀지는 못하고 다른 사람의 풀이를 보고 정리를 했다. 방의 개수를 어떻게 구할 수 있는지에 대한 것은 이 링크를 참고하면 좋을 것 같다. 굉장히 상세하게 정리해주셔서 도움이 많이 되었다. 결론만 말하자면, 방이 생성되려면 "방문한 노드가 이미 방문한 적 있으며 해당 노드로 들어온 경로는 처음인 경우" 이다. ..

https://programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 이 문제는 처음봤을 때 이기고 지는 관계이므로 선후관계가 있다고 생각해서 위상정렬을 사용해서 풀어야겠다고 생각했었다. 위상정렬로 풀려고보니 위상정렬을 사용하기 위한 조건을 만족하지 못했다. 다른 사람의 풀이를 보고 사용한 알고리즘만 확인했다. 플로이드 워셜 알고리즘을 사용하면 풀 수 있었다. 예전에 공부한 것을 바탕으로 문제를 풀었다. def solution(n, results): answer = 0 graph = [[0] * (n+1) for _ in range(n+..

https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 이 문제는 최단거리를 찾는 문제로 BFS 로 풀 수 있었다. 전형적인 BFS 문제여서 기본적인 BFS 구조만 알고 있다면 쉽게 풀 수 있을 것이다. 최근에 BFS를 공부했어서 쉽게 풀 수 있었던 것 같다. from collections import deque def solution(n, edge): answer = 0 graph = [[] for _ in range(n+1)] # 연결된 노드 정보 그래프 distance = [-1]..

https://programmers.co.kr/learn/courses/30/lessons/43236 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 이 문제는 이분 탐색 문제였다. 이분 탐색 문제는 어느 문제든 코드 구조는 정말 비슷한데 이분 탐색할 대상? 기준? 을 찾는 것이 어려운 것 같다. 여러 문제를 풀어보면서 보는 시각을 키워야 할 것 같다. 이 문제에서는 최소 거리를 이분 탐색 대상으로 삼았다. 최소 거리를 특정한 다음 바위를 제거해가면서 n과 맞는지 확인한다. n과 최소 거리가 모두..