오늘의 문제: 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(..

오늘의 문제 | 프로그래머스: 입국심사오늘은 처음으로 프로그래머스 문제가 출제되었다. 프로그래머스로 문제를 해결하는게 거의 처음이라 어색하고 문제 유형도 다르다고 느껴지긴 한다.프로그래머스는 solution 함수 기반으로 돌아간다.기본적으로 입력이 되어있는 함수에 입력값과 반환값이 적혀있다. 따라서 solution 함수의 출력값만 정상적으로 들어가게 하면 될 듯 하다.아이디어: 답은 times 배열의 원소의 배수이다.n의 범위가 매우 크고, 심사하는 시간도 매우 크기 때문에 이분탐색을 이용해야 하는건 맞다. 사실 프로그래머스는 타이틀에 알고리즘이 적혀있어서 보자마자 이분탐색임을 알 수 있었다.예시 설명에서 보았듯이 단순히 심사대가 비는 곳에 들어가는 형식이 아닌, 가장 빨리 마무리될 수 있는 시간을 구하..