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를 하나씩 감소한다면, 동기..
Python
머리말 최근 구름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..
2020 KAKAO BLIND RECRUITMENT https://school.programmers.co.kr/learn/courses/30/lessons/17677 머리말 풀이 시간 40분 다중집합의 교집합과 차집합을 어떻게 구할지 몰라 검색해서 알아보았다. 그런데 문제를 다시 보니 해당 부분 어떻게 처리할지 알려줬더라 ㅎㅎ;; 다른 풀이 방법을 보니 엄청 깔끔하니 이것도 참고해보자. 접근 방법 문제의 요구사항을 차근차근 적용하여 풀었다. 다중집합의 합집합과 교집합을 구하는 방법은 [더 알아보기]를 참조하길 바란다. 🐥 이건 얻어가자 str.upper(): 문자열을 모두 대문자로 변경 str.isalpha(): 문자열이 알파벳인지 확인 코드 def solution(str1, str2): answer =..
2020 KAKAO BLIND RECRUITMENT https://school.programmers.co.kr/learn/courses/30/lessons/60058 머리말 풀이 시간 50분 컴파일러 수업을 잘 들었다면 수월하게 풀었을 것 같다는 느낌.. 카카오에서 컴파일러 관련 문제도 내는구나 싶었다. 접근 방법 정말 다행인 것은 문제에서 접근 방법을 친절히 설명해준다;; 재귀 함수 쓰는 방법도 다 알려줘서 그거 따라서 하면 쭉 하면 문제없이 풀이할 수 있다. 균형 잡힌 괄호 문자열은 다음과 같이 판별했다. left와 right변수를 선언한다. 문자열을 앞에서부터 탐색하면서 (가 나오면 left를 증가시키고 )가 나오면 right를 증가시키는데 그 갯수가 같아지는 그 시점에서 문자열을 u와 v로 분리하..
2021 카카오 블라인드 채용https://school.programmers.co.kr/learn/courses/30/lessons/72411머리말풀이 시간 1시간 5분처음 생각한 로직을 쭉 풀어쓰다가 문제에서 이해하지 못한 부분 때문에 코드가 난잡해졌다.접근 방법2번 예제에서 왜 AB는 답에 포함되지 않을까 고민을 많이 했다.하지만 문제에서 가장 많이 함께 주문한 단품 메뉴들을 코스요리 메뉴로 구성 이라는 말을 잘 생각해야 한다.AB도 2번 이상 포함되기는 하지만, AD, CD가 3번씩 포함되므로 이것만 답에 포함시켜야 한다.나는 다음과 같은 로직으로 문제를 풀었다.단품 메뉴 가장 많이 주문한 사람의 개수를 maxLen에 저장한다.그 개수가 course 보다 작다면 확인할 필요가 없..
