재원블로그 재원블로그

이 문제는 다이나믹 프로그래밍을 이용해 풀었다. 사실 이 문제는 bfs로 풀어도 전혀 상관이 없어보이는게 2와 3을 곱해서 수가 빠른 속도로 커지기도 하고, x부터 시작해서 세 연산 모두 무조건 커지기 때문에 충분히 가능할 것 같다. 하지만 나는 이 문제를 처음 보자마자 dp가 떠올라서 그걸로 풀었다. 다이나믹 프로그래밍으로 풀 때 유의 사항은 처음으로 dp 배열에 값을 집어넣는다고 해서 그 값이 최적이 아닐 수 있다는 사실이다. 처음에 나는 dp 배열이 -1이면 dp[i] + 1을 저장하고 다음 수로 넘어갔는데, 이렇게 하면 테스트 케이스에서 일부 오답이 나온다. 그래서 dp가 -1이 아니더라도 dp[i] + 1과 저장되어 있는 값을 비교하여 최소를 저장하는 로직을 집어넣었더니 바로 정답이 나왔다. #..

이 문제는 스택을 이용해서 푸는 문제이다. 처음에는 덱을 이용해서 풀었는데 테스트 22번에서 시간 초과가 났다. 아무리 해도 정답이 나오지 않아 검색을 했고, 스택을 이용해서 훨씬 간단하게 풀 수 있었다. 일단 입력 배열의 최대 길이가 1,000,000 이므로 무조건 O(n) 이하의 알고리즘을 구상해야만 한다. 덱을 이용했을 때의 수도 코드는 다음과 같다. (시간 초과) answer[n] = -1 for (i : n - 1 -> 1) 만약 numbers[i + 1] > present dp.push_front(numbers[i + 1]); answer[i] = numbers[i + 1] 그렇지 않다면 dp 덱 순회하여 present보다 큰 값 있는지 확인 만약 없으면 answer[i] = -1 있으면 an..

이 문제는 프로그래머스 level 2에 있는 문제이다. 이 문제를 처음에는 그리디한 방식으로 풀었지만, 오답이 나왔다. 결국 해답을 찾지 못해 검색을 통해 풀이를 확인했고, 다이나믹 프로그래밍과 비슷한 방식으로 풀 수 있다는 사실을 발견했다. 내가 아쉬웠던 것은 다이나믹 프로그래밍과 같은 방식을 생각하긴 했지만, dp 배열에 무조건 답이 들어가야 한다는 생각에 빠져 해답을 찾지 못한 것이다. 코드를 보면 이전 행에서 최댓값을 더해주고, 같은 행일 때만 두번째로 큰 값을 더해주는데, 이 방식이 다이나믹 프로그래밍에서 메모이제이션과 비슷하다고 느꼈다. dp 배열에 무조건 정답이 들어가는 게 아니라 어떤 값이든 답을 찾을 수 있는 방식이라면 들어갈 수 있다는 생각을 꼭 해야겠다. #include #includ..

이 문제는 맵을 이용해서 풀었다. 상당히 복잡한데, 특히 교집합과 합집합을 계산해내는 것이 복잡했다. 일단 특수 케이스로 입력 스트링을 파싱한 두 배열이 모두 공집합이면 65536이 나와야 하고, 둘 중 하나라도 공집합이면 0이 리턴된다. 입력 스트링에 대한 집합을 만들 때, 그 안에 중복된 것도 들어가게 하는 대신 각 요소마다 카운트를 저장하고 집합 안에는 하나만 들어가도록 구현했다. 또한 교집합과 합집합을 구하는 수도코드를 다음과 같이 짜서 구현했다. - 교집합 찾는 수도코드 visited 맵 생성 inter = 0 A 집합 반복문 현재 원소 : temp B 집합 반복문 만약 같으면 inter += min(cntA, cntB) visited[temp] = true; break; 만약 break로 끝나..

이 문제는 문자열, 정렬, 맵을 이용해서 풀었다. 이 문제의 핵심은 문자열로 주어진 집합을 이차원 배열로 파싱하는 것과, 파싱된 정수 배열에서 원래 튜플을 찾아내는 것이다. 문자열 파싱같은 경우에는 다음과 같은 수도 코드를 작성하여 구현하였다. 여는 괄호 나오면 반복문 시작(닫는 괄호 나올 때까지) 숫자면 append 쉼표면 vector에 push, append 스트링 초기화 또한 원래 튜플을 찾아내는 것은 정수 배열들 중에 가장 작은, 즉 길이가 1인 배열부터 보면 해당 배열의 숫자가 반드시 원래 튜플의 첫번째 자리임을 알아내면 규칙성을 쉽게 찾을 수 있다. 첫번째 자리를 찾으면, 그 다음 길이가 2인 배열을 보고 기존에 있지 않은 숫자가 2번째 자리이고, 쭉 반복하면 원래 튜플을 찾을 수 있다. 전체..

이 문제는 자료구조를 이용한 구현 문제이다. cities의 최대 길이가 100,000 밖에 되지 않기 때문에 충분히 시간 안에 풀 수 있다. 일단 예외 케이스로 만약 캐시 사이즈가 0이라면 무조건 miss만 발생하기 때문에 5 * cities.size()를 리턴해주면 된다. 그 다음 캐싱에 대한 알고리즘이 필요한데, 간략한 수도코드를 다음과 같이 구현했다. 먼저 찾을땐 왼쪽에서 pop하면서 찾음 - 그 순서 그대로 집어넣음 만약 찾으면 빼고 일단 왼쪽으로 집어넣음 그 다음 찾은거 오른쪽으로 집어넣음 만약 없으면 일단 다 집어넣고 (왼쪽으로) 가장 왼쪽에 있는거 빼고 오른쪽으로 새로 집어넣음 물론 위와 같은 수도 코드를 그대로 구현하지는 않았지만, 생각을 정리하는데 큰 도움이 되었다. 덱에서 왼쪽에 있는 ..

이 문제는 구현 문제인 것 같다. discount의 최대 길이가 100,000이고, want의 길이가 최대 10이므로 단순 순차 검색으로도 시간 초과가 발생하지 않는다. 이 문제는 단순히 요구사항들을 구현만 하면 되지만, 문제를 잘 읽어야 한다. 문제에서 요구하는 것은 가능한 일 수의 개수인데, 나는 이걸 잘못 읽어서 처음 나오는 일 수를 리턴했다. 알고리즘은 문제를 잘 읽어보는게 정말 중요한 것 같다. #include #include #include using namespace std; int solution(vector want, vector number, vector discount) { int answer = 0; for (int i = 0; i < discount.size() - 9; i++) ..

이 문제는 슬라이딩 윈도우와 맵을 이용해서 풀었다. elements 의 최대 길이가 1,000 이므로, 최대 O(n^2) 시간을 소요할 수 있고 그 이상의 시간이 드는 알고리즘은 사용할 수 없다. 만약 부분 수열의 합을 구하는 알고리즘 내부를 단순 반복문으로 구성하면 1,000,000 * (l 값) 이 들어 시간이 초과될 것 같았고, 이를 보완하기 위해 고정된 범위를 이용한 슬라이딩 윈도우로 시간을 단축시켰다. 또한 값의 중복이 없어야 하므로 map에 해당 값을 저장함으로써 중복을 없앴다. set을 사용할 수도 있지만 아직 잘 몰라서 잘 알고 있는 map을 이용해 문제를 풀었다. #include #include #include using namespace std; map mp; int solution(v..