https://www.acmicpc.net/problem/1932 5인 정수 삼각형의 한 모습이다. 맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있...
이진탐색과 파라메트릭서치 차이점
파라메트릭서치(Parametric Search)는 파라미터(매개변수)에서 파상된 단어입니다. 그리고 이진탐색(바이너리서치)와 파라메트릭 서치는 어떻게 다른지 한번 살펴봅시다. 이진탐색(Binary Search) 이진탐색의 경우 정렬된 시퀸스에서 중간인 지점을 서치하면서 답을 찾아나가는 것으로 O(logN)의 복잡도를 보이는 것으로 알려져 있습니다....
금광 다이나믹프로그래밍
nxm크기의 금광이 있습니다. 금광은 1x1 크기의 칸으로 나누어져있으며, 각 칸은 특정한 크기의 금이 들어있습니다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫번째 열의 어느 행에서든 출발할 수 있습니다. 이후에 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다. 결과적으...
정렬된 배열에서 특정 수의 개수 구하기 이진탐색
리스트나 배열이 정렬되어 있다는 가정하에 가장 빠르게 원소를 찾는 방법은 이진탐색을 이용하는 것입니다. 그리고 이런 이진탐색은 코딩테스트에서 출제자가 의도하지 않았더라도 제일 효과적으로 문제를 해결할 수도 있으니 이진 탐색 라이브러리인 bisect 모듈의 사용 방법은 꼭 기억을 합시다. 예를 들어 수열 [1,1,2,2,2,2,3]이 있을 때 x = ...
정렬된 시퀸스를 탐색할때 이진탐색 bisect 사용방법
일반적으로 정렬되었다는 가정하에 어떤 원소를 가장 빠르게 찾는 방법은 이진탐색을 수행하는 것이고 이 이진 탐색을 위해서 파이썬 내장함수로 준비된게 bisect입니다. 프로그램이 구체적으로 어떤 것을 처리해야하는지 유형에 관계없이 리스트에서 index함수를 사용해 특정값을 찾아내려면 리스트 길이에 선형적으로 비례를 합니다. 운이 좋아서 첫번째에 있다...
카드 정렬하기 백준 1715번 정렬
https://www.acmicpc.net/problem/1715 문제 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많...
가사 검색 프로그래머스 이진탐색
https://school.programmers.co.kr/learn/courses/30/lessons/60060 친구들로부터 천재 프로그래머로 불리는 “프로도”는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.그 제안 사항 중,...
실패율 프로그래머스 정렬
https://school.programmers.co.kr/learn/courses/30/lessons/42889 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다. 이 문제...