ComDoc ComDoc

거스름돈 연습문제 925명 완료 동적계획법, 테이블 작성하는 게 쉽지 않다. https://programmers.co.kr/learn/courses/30/lessons/12907 코딩테스트 연습 - 거스름돈 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5�� programmers.co.kr 만들 금액 -> 0원 1원 2원 3원 4원 5원 1원 동전 경우의 수 -> 1 가지 1 1 1 1 1 2원 동전 추가시 경우의 수 -> 1 1 2 2 3 3 5원 동전 추가시 경우의 수 -> 1 1 2 2 3 4 0원이 가능한 조합은 동전 0개를 사용할 수 밖에 없음 그..

순위 그래프 986명 완료 플로이드 와샬 알고리듬을 이용하면 되지만.. 족보 없는 방법(야매)으로도 풀 수 있다.. n번 선수, n번 선수에게 이긴 선수들, n번 선수에게 진 선수들, 이 셋의 합이 n이 되면 ~! n번은 순서를 알 수 있는 선수. 그림을 그려보면 직관적이다. 다만 어떻게 빠짐없이 이긴 선수와 진 선수를 정리할 수 있을지가 관건.. ..... 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): winner_loser, loser_winner = {i + 1:..

하노이의 탑 연습문제 1186명 완료 워낙 유명한 문제라... https://programmers.co.kr/learn/courses/30/lessons/12946 코딩테스트 연습 - 하노이의 탑 하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대�� programmers.co.kr 일단 종이로 어떤 식으로 움직이는지 확인해도 좋겠지만.. 종이보다 컴이 편해서.. n = 2인 경우... def solution(n): tower = [[i for i in range(n, 0, -1)], [], []] print(tower) def move(f, t): #..

줄 서는 방법 연습문제 1218명 완료 https://programmers.co.kr/learn/courses/30/lessons/12936 코딩테스트 연습 - 줄 서는 방법 n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람 programmers.co.kr 전수조사(brute force). 당연히 시간 초과.정답 비교용. def solution(n, k): from itertools import permutations lines = permutations([each for each in range(1, n + 1)]) for each in range(k - 1)..

섬 연결하기 탐욕법(Greedy) 1687명 완료 최소 신장 트리(Kruskal Algorithm)로 풀 수 있는 문제입니다. 이 알고리듬을 공부하신 적 있으시다면 어렵지 않게 풀 수 있을 겁니다. https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 문제를 읽어보면.. 주어진 배열을 비용을 적게 드는 순서대로 연결합니다. (정렬이 필요, 탐욕 알고리듬이죠.) 이때 이미 연결된 조합은 제외해야 합니다. (Union-Find 알고리듬, 아래 코드에서는 path리스트와 find 함수로 구현) 사이클이 생기는 조합은 ..

https://programmers.co.kr/learn/courses/30/lessons/43238 입국심사 이분탐색 1833명 완료 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 � programmers.co.kr 이분(이진)탐색은 최대값, 최소값, 중간값을 두고.. 찾는 값이 중간값보다 낮으면 최대값을 '중간값-1'으로 낮추고 찾는 값이 중간값보다 높으면 최소값을 '중간값+1'으로 올려주면서 숫자를 찾아가는 방식이다. 예전에 블로그에 정리한 적 있다. https://comdoc.tistory.com/entry/32-%EC%9D%B4%E..

단속카메라 탐욕법(Greedy) 1720명 완료 https://programmers.co.kr/learn/courses/30/lessons/42884 코딩테스트 연습 - 단속카메라 [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2 programmers.co.kr 시간제한이 없다면.. def solution(routes): cameras = set() while routes: all_case = {} for route in routes: for i in range(min(route), max(route) + 1): all_case[i] = all_case.get(i, 0) + 1 max_ = max(all_case.values()) for k, v in all_case.items..

방문 길이 Summer/Winter Coding(~2018) 1364명 완료 어렵지 않은데 유독 완료 수가 작다... 아래 풀이를 보지 말고 자신 있게 풀어보시길 ... https://programmers.co.kr/learn/courses/30/lessons/49994 코딩테스트 연습 - 방문 길이 programmers.co.kr def solution(dirs): paths, x, y = set(), 0, 0 for i in dirs: prev_x, prev_y = x, y if i == "U" and y + 1 x or prev_y > y else (x, y, prev_x, prev_y)) elif..