분류 전체보기
-
🚚 블로그 이전 공지 🚚카테고리 없음 2022. 11. 21. 00:00
https://velog.io/@squareyun 공지 첫 게시물인 2020년 8월 5일로부터 약 2년 후 새로운 곳으로 블로그를 이전하게 되었습니다. 새로운 블로그 주소는 상단에 적어놓았고, velog를 선택하였습니다. 블로그 이전 이유 블로그를 시작하게 된 계기는 공부한 것을 기록하고 다시 보자는 것이었습니다. 그러다가 사용하던 소프트웨어에서 발생한 오류의 해결법을 포스팅하였을 때, 방문자 수가 급등하게 되었습니다. 많은 분들의 감사 인사를 받고, 기뻤습니다. 제가 아는 것을 공유하고자 하는 마음이 커졌습니다. 많은 개발자 분들이 티스토리를 사용하여 작성하길래 저도 이 플랫폼을 이용하였습니다. 마음의 드는 스킨을 찾고자 며칠을 썼고, black7375 님께서 수정하신 블로그 스킨을 지금까지 잘 써왔습..
-
[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..