시드니랩

누가봐도 분명 그래프 문제인데, 'shortest' 관련한 이야기가 없어서 바로 DFS로 접근했다. Permutation/ Combination 의 DFS문제가 얼마나 기초가되는지 다시한번 실감한다

설계는 비슷하게 했는데 최소거리임을 간과하고 DFS로 시도했다가 아주 오래 걸려버렸다. 반드시 "최소값" 을 구해야 하는 문제에서는 BFS를 먼저 떠올려주자

문제를 정확히 파악하지 못해서 어마무시한 시간을 날린 문제이다. 한곡이 있을때를 제외하고, 무조건 2개씩 붙는다는 조건을 무시해서, 계속 숨겨진 테스트케이스에서 실패하였다. zip 사용법 복습과 lambda 를 이용한 딕셔너리 정렬방법을 다시 복습할 수 있었던 좋은 기회였다.

해시테이블을 만들고 간단한 조합연산을 하는 문제였다. 딕셔너리 사용법을 잘 복습할 수 있던 좋은 기회였다. defaultdict 을 사용하면 정해준 type으로 디폴트 값이 형성되므로, 복잡한 연산을 할 필요가 없어진다. 또한, 없는 키값에 추가하더라도 에러를 발생시키지 않기때문에 예외처리를 안해줘도 된다는 점에서 좋다. 딕셔너리에서 모든 조합을 다 나타내야하는 상황에 대해서 복습하자. [모범답안] [반성할 점] Counter 객체를 사용하자!! - len 사용이나 set으로 변환할 필요없이, Counter 객체를 사용한다면, 중복되는 값을 제외하고 동일한 값이 몇개 반복되는지 확인할 수 있다. 입력으로는 리스트/딕셔너리 모두 된다. 다만 리턴값은 Counter 객체이기때문에, 딕셔너리처럼 values(..

파이썬은 다 참조로 돌리기때문에 b=[[0]*n] 했다가 나중에 특정 요소에 append 하면, 모두 같은 값을 가리키기때문에 모든요소에 append 될수 있다. 따라서 그냥 리스트 컴프리헨션으로 [[0] for _ in range(n)] 으로 구현하는게 훨씬 안전하다. BFS에서 실수했다! distance += 이전 distance 배열값 인데... visited 랑 distance 를 한꺼번에 처리하려다가 시간 많이 잡아먹었다. 가능한 각 기능을 담당하는 요소들은 분리하자.

교훈은 굳이 배열의 모든 정렬이 필요없다고 생각되고, 지속적인 최소 혹은 최대값만 관심이 있을때 heap 을 떠올리자는 것이다

간만에 제대로 풀었다고 생각하는 문제였다. 이제 스택/큐는 비록 초보지만 감각 정도만 유지하고, DP와 그래프에 조금 더 신경을 써보자, [내 풀이] 내풀이의 핵심은, Timer 와 Bridge 라는 큐를 두개 만들어서, 트럭이 들어오고 빠지는 시뮬레이션을 큐의 pop으로 구현했다는 것이다.

간단한 정렬 문제라고 생각했는데, 꽤나 까다로운 문제이다. 일단 string 정렬 기준을 잘 알 수 있게된 좋은 문제였다고 생각한다. [반성할점] 반성할점 보다는 배워가는 점이 더 많은 문제다. - map 함수 의 사용, - 스트링연장해서 비교할수 도 있다는 사실을 염두에두기

순열 가짓수를 dfs 로 구하는 방법을 체화하려고 해서그런지, dfs를 빨리 구현하고나서 디테일을 수정하는 방식으로 구현했었다. 하지만 풀이를 보니까 다른 멋진 풀이들이 많다. [내풀이] [모범 답안] => 개인적으로 감탄한 풀이이다. 부분집합 구할때 이렇게 요소들을 하나하나씩 더해서 구할수도 있구나.

전형적인 크루스칼 알고리즘 문제로, 그래프가 주어졌을때, 간선의 가중치를 최소로 소비하면서 Minimum Spanning Tree를 만들어 내는 문제다. 크루스칼 알고리즘을 복습하고싶으면 이 문제를 바로 풀어보도록 하자. [내 풀이] [반성할 점] Parent Union 할때 좀 애를먹었다... find(v[0],v[1])!=True 일때, table[v[0]]=table[v[1]] 을 했었는데, 합칠때도 재귀로 타고 올라가야된다. 안그러면 서로다른 두 그래프를 합치게될때(서로 다른 시작점에서 출발할때) 에러난다.