Overman

유니온 파인드 마지막 예제이다. 이런 유니온 파인드 같은 알고리즘 한해서 나오는 예제 같은 경우는 문제가 다양한 느낌은 아니다. 뭔가 구조를 활용해서 문제와 싸운다기 보다는 그저 유니온 파인드를 구현해놓고 살짝씩 바꿔가며 해결해가는 느낌이다. 일단 문제를 읽어보면 사이클에 대한 문제해결을 요구한다.지금까지는 같은 집합임을 물어봤다면, 이번에는 간선을 긋는다는 점에서는 같은 집합임을 물어봤으나 사이클이라는 조건을 추가하여 첫 사이클이 언제 발생하는 지를 출력해야한다. 그렇다면 사이클이 어떤 경우일 지를 생각해보면1. 같은 집합에 있어야 한다.2. 이미 같은 집합에 있어야 한다. 이렇게 순서대로 생각하는 것이 옳다. 즉, 컴퓨터 속에 내가 있다는 가정으로 상황을 계속 판단해본다고 할 때 입력이 들어올 때마다..

알고리즘, 백엔드/알고리즘, 자료구조 2025. 2. 8. 14:23

유니온 파인드 3번째 예시 문제로 두 사람의 친구 네트워크에 몇 명이 있는 지 구하는 것이다.입력으로는 친구 관계가 입력으로 들어오고 친구 관계가 생길 때마다 친구 네트워크가 몇 명이 있는 지 구하는 프로그램을 작성하는 것이다.즉, 유니온 파인드의 개념으로 생각을 해본다면 친구 관계라는 것은 결국 하나의 집합이다. 친구 관계가 들어올 때마다 기존의 집합에 새롭게 합집합으로 추가되는 개념이다.  이 문제의 난이도는 골드 2로 지난 문제가 보통 골드 4-5에 비하여 살짝 어려워졌다. 그렇다면 뭐가 다를까 하면 입력이 문자열이라는 것이다. 친구의 이름은 당연하게도 숫자가 아닌 문자열로 들어오게 된다. 그렇다면 이 문자열을 어떻게 관계 잡아 처리할 지가 관건이었다. 그리하여 생각한 방법은 문자열이 들어올 때마다..

알고리즘, 백엔드/알고리즘, 자료구조 2025. 2. 8. 14:09

이전 포스팅했던 토마토 문제와 맥락은 똑같다. 상자에 토마토가 없는 칸이 있을 수 있으며 인접한 곳에 영향을 준다. 살짝의 차이는 위 아래가 추가 되었다.  구현은 아래와 같다.from collections import dequenx = [-1,1,0,0,0,0]ny = [0,0,-1,1,0,0]nh = [0,0,0,0,1,-1] # nx와 ny가 움직임이 0일때 위아래로 움직일 수 있음.q = deque([])m,n,h = map(int, input().split())arr = [[] for _ in range(h)]for i in range (h): for j in range(n): tmp = list(map(int,input().split())) arr[i].appen..

알고리즘, 백엔드/알고리즘, 자료구조 2025. 2. 5. 15:23

간단히 정리하면, 익은 토마토와 익지 않은 토마토에 대한 정보가 주어지는데 익는 것이 퍼진다는 것이다. (질병처럼)그래서 얼마나 지나면 다 퍼지냐? 이것을 물어보았다. 해당 문제는 대표적인 BFS 문제 중 하나이다. 다 풀고 나서 생각해보면 문제가 굉장히 직관적이다. 다음으로 어디로 갈 것인지가 굉장히 명확히 정해져 있다(인접한 곳). 그냥 count로 며칠이 지났는 지를 세고, bfs의 큐를 통해서 다음 갈 곳을 정하고 다음 갈 곳들을 count 변수를 통해서 값을 update 시키면 마지막 토마토가 물드는 순간에 (전부 다 익는다는 가정 하에) 마지막 토마토에 count가 아름답게 딱 적혀있을 것이다. 그렇다면 BFS는 도대체 뭐길래 글쓰는 놈은 신나서 나불대고 있는 것일까BFS는 DFS와 비슷한 탐..

알고리즘, 백엔드/알고리즘, 자료구조 2025. 2. 5. 15:18

유니온 파인드를 연습하기 위한 두 번째 문제이다. 입력의 의미는 도시가 어느 도시와 연결되었는지에 대한 여부이다. 원하는 여행 경로에 따라 해당 여행 경로가 가능한 여행 경로면 YES아니면 NO가 출력되는 형식이다. 해당 문제를 보며 처음 든 생각은 이거를 만약 코딩 테스트나 문제 구분 없이 푼다면 당연히 BFS로 풀 거 같다는 생각을 하였다. (물론 지금도 마찬가지이다.) 하지만 분류를 유니온 파인드에서 발견하였으므로 해당 방법으로 풀겠다. 유니온 파인드에 대한 구현은 그 전(골드 5 [1717번] - 집합의 표현)과 같게 생각했다. 알고리즘 자체가 어려운 것도 아니고 굉장히 간단했기 때문에 기본으로 이 함수를 적어두고 어떻게 해결할 까 생각했다. 유니온 파인드의 구현 방식을 생각해보면 같은 집합에 속..

알고리즘, 백엔드/알고리즘, 자료구조 2025. 2. 5. 15:05

오늘 공부했던 것은 유니온 파인드에 관련한 문제이다.해당 문제에는 두 가지 종류의 연산이 들어온다.하나는 두 집합을 합치는 연산이며, 다른 하나는 두 원소가 같은 집합에 포함되어 있는지 확인하는 연산이다.즉, 집합을 합치고, 포함되어 있는지 확인하는 연산이 필요하다. 보통 집합이라는 자료 구조를 다룰 때는 파이썬에서는 set을 통해서 이리저리 굴린다. 하지만 이 문제를 풀기 전에 실제로 그 자료 형을 사용해서 움직이게 하는 것인가 생각을 해보았다.  굳이이다. 최근 백준을 풀며 느낀 것은 예상보다 실제 그렇게 움직이는 것을 구현하는 것보다 같은 맥락으로 해석 가능한 무언가를 만드는 느낌이 강했다. 심지어 해당 문제의 분류는 유니온 파인드라는 새로 푸는 문제 분류로 들어가있다. 따라서 문제를 풀기 전에 유..

알고리즘, 백엔드/알고리즘, 자료구조 2025. 2. 5. 14:49

https://www.acmicpc.net/problem/11401 이런 문제가 젤 무섭다. 문제가 한 줄로 끝나는 데 골드 1에 있고, 시간 제한 1초, 메모리 제한 256MB로 딱봐도 타이트하게 걸려있다.또한 1,000,000,007로 나눈 나머지라는 말이 있는 거로 봐선 입력에도 큰 값이 들어올 것이라는 것을 당당히 밝히고 있다.# 1,000,000,007인 이유 :  (int의 범위 : -2147483648 ~ 2147483647) int의 max에 가까운 수 중에서 절반에 해당하는 소수 값1. 모듈러 연산을 하기 위해서2. stackoverflow 방지 (최대값으로 나눌 경우, overflow일어날 수 있음) 이제 해당 문제에 대한 접근을 하게 되면, 보통의 이항 정리 공식이라고 하면nCr =>..

알고리즘, 백엔드/알고리즘, 자료구조 2025. 1. 28. 16:34

Discord를 이용해서 주식의 코드를 입력한 경우 주식의 정보를 전달해주는 간단한 기능을 만들어보자. 몇가지 단계가 필요하다. 1. KIS develop 가입 및 계좌 연동 TOKEN을 받아야 한다.2. Discord 봇에 해당하는 TOKEN을 받아야 한다.3. 이것을 파이썬을 통해 연결하여야 한다. TOKEN은 일종의 로그인을 해주는 무언가라고 생각하면 될 것 같다. 1번의 경우는 이미 진행되었다고 가정하고 진행하겠다. 일단 시작은 디스코드 개발자 포털에 들어간다.https://discord.com/developers/applications Discord Developer Portal — API Docs for Bots and DevelopersIntegrate your service with Dis..

알고리즘, 백엔드/Economic discord bot 만들기 2025. 1. 28. 16:09