전체 글
-
[Python] 백준 7662 : 이중 우선순위 큐Algorithm 2022. 11. 2. 00:06
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 : 개미와 진딧물Algorithm 2022. 11. 1. 02:03
머리말 최근 구름LEVEL에서 알고리즘 먼데이 챌린지에 참가하고 있다. 해당 챌린지는 매주 월요일에 4문제를 2시간 안에 푸는 코딩 테스트를 진행하고, 그 다음 주에 해설 강의를 제공하는 챌린지이다. 코린이를 위한 프로그램 같지만,, 생각보다 어렵다는 점 😇 스탬프를 얻으면 소소한 간식도 얻을 수 있으니 추천ㅋㅋ 이번 주차의 1번 문제로 개미와 진딧물 문제로 그래프 문제가 나왔다. 접근법 처음에는 BFS 문제인 줄 알고, 개미집 위치를 queue에 모두 넣고 bfs 순회하며 거리를 계산했다. 제출하니 시간초과로 통과하지 못했다. 문제를 단순하게 생각해보자. 입력 값의 범위가 작다! ➡️ 완전 탐색 개미집과 수액의 거리를 완전탐색하며 Manhattan distance 거리를 계산하고, 그 거리가 m 보다 ..
-
[Python] 백준 3190 : 뱀 (implementation)Algorithm 2022. 10. 7. 16:40
https://www.acmicpc.net/problem/3190 머리말 아, 뱀 게임 로직 짜는 거구나,, 재밌겠다,, 처음에는 뱀의 위치 정보를 어떻게 구현해야 할지 고민을 하다가 큐가 문득 떠올랐다. 자료구조 때 배운 것을 바로 적용할 수 있는 능력을 키우자! 접근 방법 차근차근 해결하면 된다. 맵 정보를 저장하는 graph 리스트에 사과 위치를 2로 저장하였다. dx, dy 방향 전환을 동, 북, 서, 남 형식으로 저장하여 방향에 맞게 circle로 돌 수 있도록 하였다. cnt는 게임의 시간 정보를 나타내는 변수로, 이것을 logs 배열에 존재하는지 확인 후 방향 전환을 고려하였다. 뱀의 위치 정보를 저장하는 snake 리스트를 큐(deque)를 사용하여 이동할 때 머리는 push, 꼬리는 po..
-
[Python] 백준 1865 : 웜홀 (Bellman Ford)Algorithm 2022. 10. 4. 18:23
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이 존재한다는 결론..
-
2022년 7월 ~ 8월 월간 일지Study log 2022. 9. 1. 23:00
키워드 일기 7월 # 토익: 다음 달에 있을 토익 공부를 위해 단어, ets 기출 1권을 풀었다. 꾸준히 하자고 다짐했지만 건너뛴 날도 있다 😇 7월 말까지만 해도 LC 귀가 뚫렸다고 생각했었다. (과거형) # 정보처리기사: 대학 동기들이 다 따길래 나도 따라 쳐봤다. 외우는 게 너무 귀찮았지만 필기 합격! 실기 시험은 언제더라 # 제주도 여행(8日-15日): 교회 친구들과 다녀왔는데 스쿠버 다이빙도 처음 해보고,, 이것저것 별거 다해서 행복했다ㅋㅋ 다음에도 모일 수 있겠지? 8월 # 토익: 시험 결과가 나왔는데,, 저번보다 RC는 75점 올랐는데 LC는 35점 떨어졌다 ㅋㅋ. 졸업을 위해서 땄지만 공부한 게 아쉬워서 한 번 더 시험 칠까 고민 중이다. LC 진짜 자신 있었는데 점수 폭망 # 스미싱: 여..
-
[오브젝트] 역할, 책임, 협력Books 2022. 8. 18. 22:17
"오브젝트: 코드로 이해하는 객체지향 설계" 책의 기록입니다. 협력 협력이란, 어떤 객체가 다른 객체에게 무엇인가를 요청하는 것 메시지 전송: 객체 사이의 협력을 위해 사용할 수 있는 유일한 커뮤니케이션 수단 메시지를 수신한 객체는 메서드를 실행해 요청에 응답 객체가 메시지를 처리할 방법을 스스로 선택! → 자신의 일을 스스로 처리하는 자율적인 존재 객체를 자율적으로 만드는 기본적인 방법은 내부 구현을 캡슐화하는 것 협력이 설계를 위한 문맥을 결정 객체의 행동을 결정하는 것은 객체가 참여하고 있는 협력 객체의 상태를 결정하는 것은 행동 결론적으로, 협력이 객체를 구성하는 행동과 상태를 모두 결정 → 객체 설계에 필요한 문맥을 제공 책임 협력에 참여하기 위해 객체가 수행하는 행동 무엇을 알고 있는가(kno..
-
[Python] 백준 16500 : 문자열 판별 (dp)Algorithm 2022. 7. 19. 01:23
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..
-
[Python] 백준 12865 : 평범한 배낭 (0/1 knapsack problem)Algorithm 2022. 7. 9. 00:18
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]