nxm크기의 금광이 있습니다. 금광은 1x1 크기의 칸으로 나누어져있으며, 각 칸은 특정한 크기의 금이 들어있습니다. 채굴자는 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫번째 열의 어느 행에서든 출발할 수 있습니다. 이후에 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다. 결과적으로 채...

리스트나 배열이 정렬되어 있다는 가정하에 가장 빠르게 원소를 찾는 방법은 이진탐색을 이용하는 것입니다. 그리고 이런 이진탐색은 코딩테스트에서 출제자가 의도하지 않았더라도 제일 효과적으로 문제를 해결할 수도 있으니 이진 탐색 라이브러리인 bisect 모듈의 사용 방법은 꼭 기억을 합시다. 예를 들어 수열 [1,1,2,2,2,2,3]이 있을 때 x = ...

일반적으로 정렬되었다는 가정하에 어떤 원소를 가장 빠르게 찾는 방법은 이진탐색을 수행하는 것이고 이 이진 탐색을 위해서 파이썬 내장함수로 준비된게 bisect입니다. 프로그램이 구체적으로 어떤 것을 처리해야하는지 유형에 관계없이 리스트에서 index함수를 사용해 특정값을 찾아내려면 리스트 길이에 선형적으로 비례를 합니다. 운이 좋아서 첫번째에 있다...

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 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다. 이 문제...

https://www.acmicpc.net/problem/18310 문제 일직선 상의 마을에 여러 채의 집이 위치해 있다. 이중에서 특정 위치의 집에 특별히 한 개의 안테나를 설치하기로 결정했다. 효율성을 위해 안테나로부터 모든 집까지의 거리의 총 합이 최소가 되도록 설치하려고 한다. 이 때 안테나는 집이 위치한 곳에만 설치할 수 있고, ...

https://www.acmicpc.net/problem/10825 문제 도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오. 국어 점수가 감소하는 순서로(내림차순) 국어 점수가 같으면 영어 점수가 증가하는 순서로(오름차순) 국어 점수와 ...

Deque를 이용한 스택, 큐 구현하기 지난번 파이썬 내장 함수인 deque를 이용해서 간단하게 스택과 큐처럼 사용하는 방법을 작성했습니다. 이어서 코딩테스트에서 유용하게 사용할 수 있는 우선순위큐에 대해서 살펴보겠습니다. 먼저 이를 위해서 힙이라는 개념도 알고 있으면 좋습니다. 힙 정렬이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하...

https://school.programmers.co.kr/learn/courses/30/lessons/60063 로봇개발자 “무지”는 한 달 앞으로 다가온 “카카오배 로봇경진대회”에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 2 x 1 크기의 로봇으로 “무지”는 “0”과 “1”로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 ...