https://leetcode.com/problems/combination-sum/ ✅ 체크 포인트 1. ArrayList를 깊은 복사 : ArrayList(comb); 2. Backtracking할 때 다음 시작 인덱스를 i 를 해야할까 i + 1 을 해야할까? 제출 코드 class Solution { public List combinationSum(int[] candidates, int target) { List answer = new ArrayList(); Arrays.sort(candidates); dfs(answer, new ArrayList(), candidates, target, 0); return answer; } private static void dfs(List answer, Array..
Algorithm
https://www.acmicpc.net/problem/7662 접근 방법 하나의 Priority Queue를 두 가지 기준으로 만들 수는 없으니, 결국 2개의 Priority Queue를 선언해야한다. Priority Queue의 종류 중 heapq를 사용하여 구현하였다. heapq는 기본적으로 min-heap으로 구성된다. 따라서, max-heap을 구성하기 위해서는 value에 음수를 취하여 넣고 pop할 때도 음수를 취하여 사용하면 된다. 이 문제의 핵심은 2개의 우선순위 큐를 동기화하는 것이다. 나는 해시 테이블 popHistory를 이용해 동기화를 처리하였다. 에서 key는 n를 나타내고, value는 해당 n이 몇 개 존재하는지를 나타낸다. pop할 때 value를 하나씩 감소한다면, 동기..
머리말 최근 구름LEVEL에서 알고리즘 먼데이 챌린지에 참가하고 있다. 해당 챌린지는 매주 월요일에 4문제를 2시간 안에 푸는 코딩 테스트를 진행하고, 그 다음 주에 해설 강의를 제공하는 챌린지이다. 코린이를 위한 프로그램 같지만,, 생각보다 어렵다는 점 😇 스탬프를 얻으면 소소한 간식도 얻을 수 있으니 추천ㅋㅋ 이번 주차의 1번 문제로 개미와 진딧물 문제로 그래프 문제가 나왔다. 접근법 처음에는 BFS 문제인 줄 알고, 개미집 위치를 queue에 모두 넣고 bfs 순회하며 거리를 계산했다. 제출하니 시간초과로 통과하지 못했다. 문제를 단순하게 생각해보자. 입력 값의 범위가 작다! ➡️ 완전 탐색 개미집과 수액의 거리를 완전탐색하며 Manhattan distance 거리를 계산하고, 그 거리가 m 보다 ..
https://www.acmicpc.net/problem/3190 머리말 아, 뱀 게임 로직 짜는 거구나,, 재밌겠다,, 처음에는 뱀의 위치 정보를 어떻게 구현해야 할지 고민을 하다가 큐가 문득 떠올랐다. 자료구조 때 배운 것을 바로 적용할 수 있는 능력을 키우자! 접근 방법 차근차근 해결하면 된다. 맵 정보를 저장하는 graph 리스트에 사과 위치를 2로 저장하였다. dx, dy 방향 전환을 동, 북, 서, 남 형식으로 저장하여 방향에 맞게 circle로 돌 수 있도록 하였다. cnt는 게임의 시간 정보를 나타내는 변수로, 이것을 logs 배열에 존재하는지 확인 후 방향 전환을 고려하였다. 뱀의 위치 정보를 저장하는 snake 리스트를 큐(deque)를 사용하여 이동할 때 머리는 push, 꼬리는 po..
https://www.acmicpc.net/problem/1865 머리말 문제를 보고, 아 negative cycle 찾는 문제이구나 싶었다. 그래프에서 최단 경로를 탐색하는 방법 중 다익스트라와 벨만 포드가 있는데, 다익스트라는 Greedy 알고리즘이기 때문에 반드시 간선들이 non-negative weights을 만족해야 한다. 한편, 벨만 포드는 Dynamic Programming 알고리즘으로 negative weights를 가져도 정상적으로 동작한다! 접근 방법 edge relaxation을 N-1번 수행한다. 그때 만들어진 distance 배열은 최단 경로이다. edge relaxation을 N번째 수행했을 때, 더 짧은 경로를 발견한다면 negative weight cycle이 존재한다는 결론..
https://www.acmicpc.net/problem/16500 머리말 완전 탐색인 줄 알고 왜 시간 초과가 나지 쩔쩔 맺던.. (테스트케이스 완전 불친절하다 😇) 이 문제는 dp 문제이다. 가만 생각해보면 중복 연산이 많으니 메모이제이션을 당연히 해야 한다. 처음 참고한 블로그도 좋은 풀이법이지만, 다른 분(cozyyg)의 풀이가 더 직관적이어서 그 풀이로 다시 공부하였다. 접근 방법 dp 배열에는 해당 인덱스까지 A에 포함된 문자열로 표현할 수 있는지 여부를 0, 1로 저장한다. 초기값 dp[0]은 1(True)로 두고, 우리의 목표는 dp[len(s)]값이 무엇인지 찾는 것이다. 계산 편의를 위해 +1 위치에 결괏값을 저장한다. 추가 테스트 케이스 1 [input] aaaaaaaaaa 2 aaa..
https://acmicpc.net/problem/12865 머리말 0/1 Knapsack 문제 DP로 유명한 문제이자 NP-hard 문제로 유명한 문제.. 작년 알고리즘 수업시간 때 배웠던 부분이 기억이 잘 나지 않아 첨부하였다. 수업 노트 코드 n, k = map(int, input().split()) weights = [-1] values = [-1] for i in range(n): w, v = map(int, input().split()) weights.append(w) values.append(v) dp = [[0] * (k + 1) for _ in range(n + 1)] for i in range(1, n + 1): for w in range(1, k + 1): if weights[i]
2020 KAKAO BLIND RECRUITMENT https://school.programmers.co.kr/learn/courses/30/lessons/17677 머리말 풀이 시간 40분 다중집합의 교집합과 차집합을 어떻게 구할지 몰라 검색해서 알아보았다. 그런데 문제를 다시 보니 해당 부분 어떻게 처리할지 알려줬더라 ㅎㅎ;; 다른 풀이 방법을 보니 엄청 깔끔하니 이것도 참고해보자. 접근 방법 문제의 요구사항을 차근차근 적용하여 풀었다. 다중집합의 합집합과 교집합을 구하는 방법은 [더 알아보기]를 참조하길 바란다. 🐥 이건 얻어가자 str.upper(): 문자열을 모두 대문자로 변경 str.isalpha(): 문자열이 알파벳인지 확인 코드 def solution(str1, str2): answer =..
