코딩테스트(89)
-
백준 특정 거리의 도시 찾기 코드 및 해설 (파이썬)
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 큐를 이용한 BFS 코드를 활용해 풀이했습니다. 처음엔 X에서 각 도시까지의 거리를 충분히 큰 값 INF로 초기화합니다. 여기선 문제에서 주어진 K의 최댓값인 300000보다 1만큼 큰 값을 INF로 설정했습니다. 문제에서 X에서 X까지의 거리는 0이라고 했으므로 X번째 요소는 0으로 값을 변경합니다. 한 번 방문한 곳을 계..
2021.09.07 -
백준 치킨 배달 코드 및 해설 (파이썬)
https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 국어 능력이 중요한 거 같은 복잡한 문제!!!! 우선 입력으로 들어온 걸 잘 정리해서 저장해둔다 N은 도시 크기, M은 최종 선택할 치킨 가게 개수, houses엔 집이 있는 좌표를 튜플로, stores엔 치킨 가게가 있는 좌표를 튜플로 저장한다. 이때 좌표는 0이 아니라 1부터 시작한다고 했으므로 그냥 +1씩 해줬다. 이후 각 집마다 각 치킨 가게까지의 거리를 구했다. 이를..
2021.09.02 -
백준 뱀 코드 및 해설 (파이썬)
https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제 설명이 좀 불친절하지 않나?? 그렇지 않나??!?! 뱀이 너무 이상하게 움직여서 짜증나는 문제였다. 뱀이 자기자신의 몸과 부딪히는게 어떤 상황인건지 한참 고민했다. 다음 이동할 곳으로 (무리하게!) 먼저 머리 먼저 옮기는데 그 곳에 지 몸이 있으면 부딪히는 거구만 으이구 먼저 보드 크기, 사과 개수, 사과 위치, 방향 전환 시점 및 방향 등 필요한 정보를 모두 받아 변수에 저장한다. 보드는 0~ (..
2021.08.24 -
백준 럭키 스트레이트 코드 및 해설 (파이썬)
https://www.acmicpc.net/problem/18406 18406번: 럭키 스트레이트 첫째 줄에 점수 N이 정수로 주어진다. (10 ≤ N ≤ 99,999,999) 단, 점수 N의 자릿수는 항상 짝수 형태로만 주어진다. www.acmicpc.net 주어진 숫자를 절반으로 갈라 오른쪽, 왼쪽으로 나누고, 오른쪽 자릿수의 합과 왼쪽 자릿수의 합이 같은지 다른지 확인한다. 정말 쉬운 문제였는데 이상하게 평소처럼 sys.stdin.readline()을 쓰니 UnicodeError였나? 무슨 에러가 나서 헤맸다. 이상하네??? x = input() half = len(x) // 2 right = sum([int(num) for num in x[:half]]) left = sum([int(num) fo..
2021.08.24 -
볼링공 고르기 코드 및 해설 (파이썬)
출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 5, p 315 먼저 무게에 상관없이 두 사람이 볼링공을 고르는 경우의 수를 구해 total에 저장합니다. 이는 nC2와 같으므로 n * (n-1) / 2로 구현합니다. 이후 같은 무게의 공이 2개 이상인 공들을 확인하며, 이 두개를 두 사람이 고를 경우의 수를 구해 duplicates에 저장합니다. total에서 duplicates를 뺀 값을 최종 정답으로 반환합니다. import sys # N: 공의 개수, M: 무게의 범위 N, M = map(int, sys.stdin.readline().split()) balls = list(map(int, sys.stdin.readline().split())) # nC2 total = N * (N-1..
2021.08.16 -
만들 수 없는 금액 코드 및 해설 (파이썬)
출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 4, p 314 먼저 주어진 동전으로 만들 수 있는 모든 금액을 구한 후, 이중 불연속인 구간을 찾아 만들 수 없는 금액의 최솟값을 구합니다. 만들 수 있는 모든 금액을 구할 때는 possible_amount라는 함수를 만들어 사용했습니다. 오름차순으로 정렬된 동전의 리스트가 입력으로 주어지면, 첫 번째 두 개의 동전과 그 두 개의 동전의 합으로 이루어진 집합을 만듭니다. 이후 세 번째 동전부터 모든 동전을 하나씩 살피면서 지금까지 만들어진 집합 amounts의 모든 값에 현재 동전의 값을 더한 값을 집합에 추가합니다. 이후 amounts 집합을 리스트로 변환해 반환합니다. 이렇게 얻은 만들 수 있는 모든 금액 중에서 1이 없으면 정답으로 1..
2021.08.16