ComDoc ComDoc

몬테카를로 방법(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

공부가 짧아서이런 랜덤과 확률을 이용한 시뮬레이션도족보 있는 알고리듬인 줄 몰랐습니다. 이런 식으로 푸는 걸 몬테 카를로 방법이라고 하더군요. 몬테 카를로 방법(Monte Carlo method)무작위 수와 확률과 모의실험(시뮬레이션)을 통해 문제를 해석하고 해결함.  몬티홀 문제는사고 실험으로만 이해하기는 다소 혼란스럽지만...간단히 코딩할 수 있고...코딩을 하면 좀 더 이해가 쉬워지는 것 같습니다...https://namu.wiki/w/%EB%AA%AC%ED%8B%B0%20%ED%99%80%20%EB%AC%B8%EC%A0%9C 몬티 홀 문제 - 나무위키Suppose you’re on a game show, and you’re given the choice of three door..

가장 긴 팰린드롬연습문제 2100명 완료https://programmers.co.kr/learn/courses/30/lessons/12904 코딩테스트 연습 - 가장 긴 팰린드롬앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들programmers.co.kr파이썬의 효율성 테스트가 제대로 설정되지 않은 것 같다. 단순한 코드로 바로 Pass.Manacher's Algorithm을 사용하는 것이 더 좋다.  (반칙 같지만 https://docs.python.org/ko/3/library/difflib.html 를 이용하는 방법도 ..