ComDoc ComDoc

하노이의 탑 연습문제 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)..

몬테카를로 방법(Monte Carlo Method): 무작위수와 모의 실험을 통해 문제를 해석, 해결. ---------- 위 그림에서 원의 반지름을 r 이라고 하면, 원의 면적은 pi * r ** 2 (파이 * r의 제곱)입니다. 정사각형(한 변이 2 * r)의 넓이는 (2 * r) ** 2입니다. 위 '정사각형'에 랜덤으로 점을 찍을 때 '원의 중심과의 거리가 r 이하인 점'의 확률은 '(원의 면적) / (정사각형의 면적)' 입니다. 이것을 이용해서 원주율(pi)를 구할 수 있습니다. 정사각형에 랜덤으로 점을 찍을 때, 내접하는 원의 중심과의 거리가 r 이하인 점의 확률 = (원의 면적) / (정사각형의 면적) = (pi * (r ** 2)) / ((2 * r) ** 2) = (pi * (r ** 2..

섬 연결하기 탐욕법(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]] 2programmers.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_ = m..

방문 길이 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..

최고의 집합연습문제 1855명 완료https://programmers.co.kr/learn/courses/30/lessons/12938 코딩테스트 연습 - 최고의 집합자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 집합으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다. 각 원소의 합이 S가 되는 수의 집합 위 조건을 만족programmers.co.krdef solution(n, s): if n > s: return [-1] answer = [int(s/n)] * n for i in range(s % n): answer[n - 1 - i] += 1 return answer