본문 바로가기

알고리즘 문제147

[알고리즘문제] 프로그래머스 - 베스트 앨범 문제가 수학적인 지식을 필요로 하는 문제는 아니지만 기본적인 문제 분석, 얼마나 자료구조를 잘 사용하는지를 물어보는 문제인 것 같습니다. 전체적인 아이디어는 [장르 : 장르별 총 재생횟수], [장르 : 장르별 음악들의 정보(고유번호, 재생횟수)] 두개의 자료구조를 사용하였습니다. 2개의 자료구조로 2중 포문을 사용하였고, 장르가 같으면 해당 장르별 음악들의 정보에서 값을 answer에 넣어주는 방법을 사용하였습니다. 전체적인 위의 방식으로 문제를 풀었고 이 문제를 풀 때 고민했던 부분이 몇가지 있는데, 1. 각 장르별로 총 재생횟수를 체크하고 어떻게 총 재생횟수가 큰 값부터 정렬할까 ? 첫번째는 먼저 [ 장르 : 총 재생횟수] 를 map으로 체크하였습니다. map을 기본적으로 key를 기준으로 오름차순 .. 2020. 2. 3.
[알고리즘문제] 프로그래머스 - 입국심사 문제 분류는 이진탐색 문제이다. 쉽게 설명하면, 술게임 중에 소주병 뚜껑에 적힌 숫자를 맞추는 게임이 있다. 우리는 그 숫자에 대한 범위(0~100)만 안 상태에서 반씩 줄여가면서 숫자를 찾는다. 50을 말했을 때 up이면 다시 50~100에서 숫자를 찾고 75를 외쳤을 때 down인 경우 50~75....이런 식으로 숫자를 찾아가는 과정이다. 이와 비슷한 논리로 문제를 풀어 나갈 수 있다. 생각해보면 문제는 "모든 사람이 심사를 받는데 걸리는 최소 시간"을 구하는 문제이다. 이말은 즉, "모든 사람이 심사를 받을 수 있는 시간"의 값이 여러개 존재하고 그 중에서 최소 시간을 구하라는 것이다. 여기서 우리는 "모든 사람이 심사를 받을 수 있는 여러개의 값" 중에서 최소 시간의 값을 구하는 방법으로 이진탐.. 2020. 1. 27.
[알고리즘문제] 프로그래머스 - 정수 삼각형 전형적인 dp문제이다. 예전에 계산했던 결과를 사용하여 현재 계산하려는 값을 구할 수 있다. 만약 내가 dp를 배우지 않았다면 아마 완전탐색이나 dfs로 구현했을 것 같다. 7 5층 3 8 4층 8 1 0 3층 2 7 4 4 2층 4 5 2 6 5 1층 문제는 5층부터 1층까지 내려올 때 최대의 값이 얼마인지 구하는 문제이다. 제한 사항은 아래로 내려올 때 좌/우 1칸씩으로만 이동할 수 있다. 아이디어는 각 층(꼭대기층 제외)의 원소들에 현재 최선의 값을 저장하는 것이다. 여기서 "최선의 값"을 설명하면 n층의 k번째 원소에 도착할 수 있는 많~은 동선 중에서 그 값이 최대값이 경우이다. 예를 들어 3층의 1이라는 값에 도착할 수 있는 동선을 보자 7 - 3 - 1 = 11 7 - 8 - 1 = 16 여.. 2020. 1. 16.
[알고리즘문제] 프로그래머스 - 피보나치 수 그냥 일반적인 재귀방법을 사용하면 시간초과가 뜬다. fibo(5)값을 구하기 위해서는 fibo(4) + fibo(3). fibo(4)는 fibo(3) + fibo(2).fibo(3)은 fibo(2) + fibo(1). 여기서 fibo(3)은 fibo(5)와 fibo(4)를 구할 때 3번 사용하게 된다. 다시 계산을 해야 한다는 말이다. 근데 fibo(3)을 매번 계산해야 할까? 처음 1번은 계산을 해야 하지만, 그 뒤 부터는 fibo(3)계산 결과값을 기억하고 있으면 안될까 ? 그러면 바로 fibo(3)값을 재귀호출 없이 바로 구할 수 있을 것이다 -> 메모제이션 #include #include #include using namespace std; int store[100001] = {0}; int re.. 2020. 1. 6.

티스토리툴바