재원블로그 재원블로그

이 문제는 프로그래머스 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..

이 문제는 스택을 이용하여 풀었다. 이 문제의 핵심은 스택을 이용하여 괄호의 유효성을 체크하는 것과 문자열을 왼쪽으로 돌리는 방법을 구현하는 것이다. 괄호의 유효성을 체크하는 수도코드는 다음과 같다. 만약 비어있으면 push 안비어있으면 만약 여는 괄호 push 만약 닫는 괄호 top과 비교 같으면 pop 다르면 false 다 끝나고 비어있으면 true 안 비어있으면 false 전체 코드는 다음과 같다. #include #include #include #include using namespace std; bool correct(string& str) { stack st; for (char c : str) { if (st.empty()) { st.push(c); } else { if (c == '[' ||..

이 문제는 그리디로 풀었다. 문제에서 주어진 배열에서 k개의 귤을 고르는데, 종류가 다른 수를 최소화하는 문제였다. 처음에 배열을 순회하면서 해당 숫자의 cnt를 세고, cnt가 높은 순서로 배열을 정렬한다. 그 다음 k개를 선택하면서 종류가 달라졌을때 answer++을 하면 쉽게 풀 수 있다. #include #include #include #include using namespace std; map cnt; bool compare(int a, int b) { if (cnt[a] == cnt[b]) { return a > b; } return cnt[a] > cnt[b]; } int solution(int k, vector tangerine) { int answer = 0; // base case if..