오늘의 문제: 25195. Yes or yes오늘 문제는 보자마자 큰일 났다는 생각이 제일 먼저 들었다. 그래프 관련된 문제 중 골드4면 꽤나 어려울 거라 생각해서 약간 시간을 잡아먹겠다는 생각이 들었다. 그래봤자 크게 어렵지 않겠지라는 생각으로 우선 풀어봤다.아이디어: 곰곰이를 만나지 않고 종료되면 틀리지 않을까.그래프 탐색을 종료하는 방법에 대해서 생각을 해봤을 때, (1) 곰곰이를 만나게 되면 그 경로는 앞으로 검사하지 않는다. (2) 곰곰이를 만나지 않고 경로 탐색이 종료될 경우 답은 yes가 된다.라는 대원칙을 가지고 시작해보려 한다.from collections import dequeimport sysinput=sys.stdin.readlinen,m=map(int,input().split())..

오늘의 문제: 18352. 특정 거리의 도시 찾기오늘 문제는 언뜻 보기에 다익스트라 문제이다. 하지만 이 문제가 실버2인 이유가 있지 않을까 하고 바라보니 단순 BFS로 풀어도 문제가 없지 않을까 하는 생각이 먼저 들어서 BFS로 접근해보기로 했다.아이디어: BFS로 풀 수 있지 않을까from collections import dequen,m,k,x=map(int,input().split())graph=[[] for i in range(n+1)]visit=[-1 for i in range(n+1)]for i in range(m): a,b=map(int,input().split()) graph[a].append(b)def bfs(graph, start): deq=deque() idx=..

오늘의 문제 | 7562. 나이트의 이동오늘 문제는 짧지만, 난이도는 확실히 있어보인다. 머리로 생각하기 보단 코드를 짜기가 어렵지 않을까하는 생각이 든다. 우선 생각없이 코드 구조부터 구성해봤다.오늘은 확실히 아이디어가 쉽게 떠오르지 않는다. 단순히 BFS로 하자니 경우의 수가 너무 많아지고, 줄이자니 예외가 너무 많을 것처럼 느껴졌다. 확실히 실버1로 올라가니 체감 난이도가 오르긴 했다. 무지성으로 BFS를 짜보면 뭐라도 나오지 않을까.아이디어: 미리 갈 수 있는 모든 곳까지의 거리를 계산해놓자.사실 숫자가 그리 크지 않고, 체스판이 그리 크지 않기에 이론상 가능할 것이라 생각했다. 나이트가 움직일 수 있는 방법을 미리 리스트로 만들고, zip을 통해 새로운 위치에 대해 계속해서 체크하는 방식으로 했..

오늘의 문제 | 2644. 촌수계산문제를 보자마자 그래프 문제라는건 바로 알 수 있다. 그래서 입력 부분부터 코드짜고 생각해보니, 로직이 떠오르게 되었다.아이디어: DP로 해결할 수 있지 않을까물론 이걸 DP라 해야할지 전처리 과정이라 해야할지 모르겠지만, 우선 n이 크지 않기 때문에 이론상 시작하기 전 루트를 기준으로 촌수를 구하고 해당 촌수들만 빼면 어떨까 했었다.사실 이게 가능한게 부모가 최대 한 명이라는 점에서 크게 문제가 없지 않을까 생각했었다. 하지만 촌수를 계산 하는건 꽤나 복잡한 과정이기이 전처리로 문제를 해결 할 수 없었다.아이디어: 문제를 복잡하게 생각하지 말자생각보다 문제가 단순하지 않을까 생각했다. 어차피 결혼 관계가 없기 때문에 부모자식 간 1촌, 즉 거리만 계산하면 되는 것이다...

오늘의 문제 | 프로그래머스: 모음사전처음 접근한 방식은 단순한 브루트포스로 하기로 했다. 모음 개수도 적고 경우의 수도 그리 많지 않을거 같아서 생각보다 할만해 보였다.아이디어: 어떻게 모든 경우의 수를 알아내야 할까생각해보니 이걸 어떻게 경우의 수를 다 찾아내야 할지가 고민된다. 처음에 생각했던건 길이가 5개라는 보장이 없기 때문에 공백 문자를 붙이는 방식을 할려 했는데 생각보다 중복이 많아질거 같아서 안되겠다.그 다음으로 생각나는건 DP 방식으로 하나씩 원소를 추가하는 것이다. 생각보다 배열의 길이가 많이 길어지지는 않을테니까 라는 생각이 드니 모든 경우의 수만 두고 나중에 정렬하는 방식을 차용하는 것이다.이 모든 경우의 수를 계속해서 불러내기 위해서 재귀함수를 활용하기로 했다. 다만 걱정되는건 문..

오늘의 문제: 2805. 나무 자르기오늘 문제는 예전에 풀었던 문제이다. 예전에 C++로 풀었던 문제이기에 이번에는 파이썬으로 다시 풀어보려고 한다. 기본적인 이분탐색 문제이기에 크게 어려울 것은 없어보이지만, 숫자가 매우 크다는 점만 고려하면 될듯하다.예전에 풀었던 문제라 이번에도 문제없이 금방 풀릴 줄 알았는데, 계속해서 틀리는 부분이 존재한다.n,m=map(int,input().split())l=[*map(int,input().split())]left=1right=max(l)mid=0while left=m: left=mid+1 else: right=mid-1print(right)오늘도 출력을 어떤 걸 해야하나에서 문제가 발생한 듯하다. 이제 대부분의 코드는 짤 수 있지..

오늘의 문제 | 24444. 알고리즘 수업 - 너비 우선 탐색 1이번에는 어제와 달리 BFS문제이다. 똑같은 형식이기에 비슷한 문제가 있을 것이라는건 파악하고 시작했다. 이번에도 수도코드를 보고 코드를 똑같이 구현하면 큰 문제없이 되지 않을까 생각중이다. 작성하면서 느낀건, BFS는 재귀함수로 작성하지 않아도 되기에 굳이 recursionlimit을 늘릴 필요가 없다. 단지 입력 횟수만 많다는것만 고려하면 오늘은 어렵지 않게 풀 수 있었다.import sysfrom collections import dequeinput=sys.stdin.readlinesys.setrecursionlimit(100_000)n,m,r=map(int,input().split())graph=[[] for i in range(n+..

오늘의 문제 | 24479. 알고리즘 수업 - 깊이 우선 탐색 1아주 기초적인 DFS에 대한 내용이겠거니 했다. 물론 내가 그래프 관련 코드를 매우 오랜만에 짜는 것이기 때문에 수도코드를 보고 따라치는 수준이었지만, 그래도 예전에 짠 기억이 있었기 때문에 크게 무리 있지는 않았다.# 오답 코드 (Recursion Error)n,m,r=map(int,input().split())node=[i for i in range(n+1)]graph=[[] for i in range(n+1)]visit=[0 for i in range(n+1)]idx=1def dfs(node, graph, start): global idx visit[start]=idx idx+=1 graph[start].sort(..