조금씩 꾸준히 완성을 향해

문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 출력 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. 예제 입력 1 10 4200 1 5 10 50 100 500 1000 5000 10000 50000 예제 출력 1 6 내가 짠 코드 num, price = map(i..

우선선위 큐 (Priority Queue) 우선순위가 가장 높은 데이터를 먼저 삭제하는 자료구조 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용 예) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야 하는 경우 ▶ 우선순위 큐를 구현하는 방법은 다양하다. 1) 단순히 리스트를 이용하여 구현 가능 2) 힙(heap)을 이용하여 구현 가능 ▶ 데이터의 개수가 N개일 때, 구현 방식에 따라서 시간 복잡도 비교 힙(Heap)의 특징 완전 이진 이트 자료구조의 일종 힙에서는 항상 루트 노트(rooot node)를 제거 최소힙(min heap) : 루트 노트가 가장 작은 값을 가지는 힙 최대힙(max heap) : 루트 노트가 가장 큰 값을 가지는 힙 ▶ 완전 이진 트리 (Com..

그리디 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 그리디 해법은 그 정당성 분석이 중요 => 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토한다. 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다. 하지만 코딩테스트에서 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제된다. 각 부분에서의 선택이 다른 부분에게 영향을 주지 않는다 => 각 부분에서의 최적해결이 최종 해결방법이다. 예시 문제 분석 ▶ 문제 설명 당신은 음식점의 계산을 도와주는 점원..

복잡도(Complexity) 시간복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석 공간복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석 => 동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을 수록 좋은 알고리즘 빅오 표기법(Big-O Notation) 가장 빠르게 증가하는 항만을 고려하는 표기법 (함수의 상한만을 나타냄) ▶ 표현 방법 n이 증가할 때 가장 빨리 증가하는 항(최고차 항)만 남기고 다른 항은 모두 생략 가장 빨리 증가하는 항에 곱해진 상수 역시 생략 남은 항을 O() 안에 넣어 표기 알고리즘 설계 Tip ▶ 일반적으로 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서 연산 횟수가 5억을 넘어가는 경우 C언어를 기준으로 통상 1~3초 가량 시..

사실 테스트인지 뭔지도 모르고 시작했는데 얼떨결에 합격했다ㅎㅎ..... 프로그래머스 사이트에 들어가서 처음 보이는 화면에 레벨1 문제 뭐시기를 클릭하니까 갑자기 테스트가 떴다. 이게 뭐지 ㅇ__ㅇ 하다가 문제가 보이니까 그냥 풀었는데 제한시간이 40분이어서 일차 멘붕, 그리고 문제가 두 개나 있어서 2차 멘붕!! 백준문제를 풀 때는 에디터를 사용해서 코드를 짰는데 이렇게 진짜 시험환경을 만나니 좀 당황스러웠다. 그리고 원래 어려운 문제를 만나면 몇 일씩 고민하곤 했는데 이건 제한시간이 있으니 긴장돼서 사고가 멈출 뻔 했다. 그럼에도 불구하고 요근래 꾸준히 푼 덕택인지 무사히 합격을 하게 됐다. (사실 20초 남기고 풀어서 진짜 아슬아슬했다ㅠ) 테스트 결과 분석도 이렇게 나오는데, 내심 뿌듯- 체감 난이도..

문제 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다. N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로..

문제 정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 여섯 가지이다. push X: 정수 X를 큐에 넣는 연산이다. pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 큐에 들어있는 정수의 개수를 출력한다. empty: 큐가 비어있으면 1, 아니면 0을 출력한다. front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다. 입력 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. ..

문제 나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다. 재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다. 재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다. 재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자! 입력 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다. 정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할..

문제 설명 게임개발자인 "죠르디"는 크레인 인형뽑기 기계를 모바일 게임으로 만들려고 합니다. "죠르디"는 게임의 재미를 높이기 위해 화면 구성과 규칙을 다음과 같이 게임 로직에 반영하려고 합니다. 게임 화면은 "1 x 1" 크기의 칸들로 이루어진 "N x N" 크기의 정사각 격자이며 위쪽에는 크레인이 있고 오른쪽에는 바구니가 있습니다. (위 그림은 "5 x 5" 크기의 예시입니다). 각 격자 칸에는 다양한 인형이 들어 있으며 인형이 없는 칸은 빈칸입니다. 모든 인형은 "1 x 1" 크기의 격자 한 칸을 차지하며 격자의 가장 아래 칸부터 차곡차곡 쌓여 있습니다. 게임 사용자는 크레인을 좌우로 움직여서 멈춘 위치에서 가장 위에 있는 인형을 집어 올릴 수 있습니다. 집어 올린 인형은 바구니에 쌓이게 되는 데,..