Leta Learns

지난 주 초반에 풀다가 못 풀어서 포기한 문제인데 드디어 풀었다. 친구랑 같이 상의해 본 문제긴 한데 그래도 내 코드로 풀고 싶어서 계속 붙잡고 있다가.. ㅋㅋ 며칠 동안 계속 안 풀려서 그냥 친구 코드 참고했다. 내 기존 코드에서는 원산지 여부를 if문에 all() 함수를 사용해서 처리했다. 유향 그래프이므로 인접리스트에 해당 값이 요소로 들어가있지 않으면 원산지이기 때문. 근데 이 방식으로 했더니 원산지가 검거되어도 dfs는 계속 돌아가는 문제가 생겼다. 원산지가 검거되면 해당 원산지로부터 공급받는 곳을 dfs로 확인할 필요가 없다. 따라서 root 리스트를 만들어서 원산지 여부를 확인하고 원산지이고, 해당 노드를 방문하지 않은 경우에만 dfs를 돌려주었다. 이렇게 하면 두 원산지로부터 공급받는 노드..

골드1... 함부로 건드리면 안된다... 진짜... 문제부터 잘 이해가 안 돼서 계속 읽었다. 겨우겨우 이해한 바는 각 노드에서 나아갈 수 있는 방향은 '우수마을' or 'not 우수마을' 이렇게 두 가지 경우. 루트 노드가 우수 마을이면 하위 노드는 우수 마을 일 수 없다. 루트 노드가 우수 마을이 아니면, 하위 노드는 우수 마을이거나 아니거나. (둘 중 최댓값....아마도) 이걸 dp에 저장하는 게 역시나 난관이었는데 dp[i][0] : 현재(i) 마을이 우수 마을이 아닌 경우 dp[i][1] : 현재(i) 마을이 우수 마을인 경우 로 저장했다. 제출했는데 recursion error 떠서 절망적이었다.. 근데 recursionlimit 풀어주니까 바로 됐다. 사실.. 어떻게 이렇게 빨리 풀 수 있었..

이거 지난 주 토요일 모각코 때 시도했던 문제인데 다른 거 하느라 계속 미뤄서 드디어 오늘 다시 시도했다. 모각코 당일인 17일에는 아예 알고리즘을 잘못 생각하고 있었고, 다음날인 18일에 다시 풀어서 모각코 글을 작성했다. 18일에 푼 코드는 예제만 맞고 제출 돌리면 틀렸었다. 2021.07.17 - [HUFS/HUFS 모각코 캠프] - [모각코] 210717 Today I Learned #기존(에 틀린) 코드 import sys def dfs(v): visited[v] = 1 for i in range(len(adjList[v])): w = adjList[v][i][0] if not visited[w]: dist[w] = max(max(dist), adjList[v][i][1] + dist[v]) d..

https://www.acmicpc.net/problem/7576 요새 dfs, bfs를 공부 중이었는데 익숙치 않아서 한 문제 푸는데 2-3일 걸리고 그랬다. 이 문제도 일요일에 처음 풀었는데 못 풀어서 모각코 때 다시 풀어야지. 하고 다른 공부했다. bfs는 그냥도 어려운데 이번 문제는 다른 문제들과 달리 n, m 으로 입력받는 게 아니라 m, n으로 입력 받아서 헷갈렸다. 그거 뭐 얼마나 바뀌었다고 헷갈리냐고 하면.. 할 말이 없다. 저는 코딩 바보예요. 종이에 계속 쓰면서 n이 row고, m이 col이다 라는 걸 계속 상기시켜주었다. 1. 기본 틀은 다른 bfs 문제들이랑 거의 비슷했는데 이 문제에서 좀 특별한? 점은 q.popleft()하기 전에 range(len(q))로 for문을 돌려준 것이..

내가 지금 .. 무언가 잘못된 길을 걷고 있다... 어려운 문제가 아닌 것 같은데 내가 지금 어렵게 풀고 있는 거다... 알고리즘 구상을 다시 해야 될 것 같다. visited를 2차원으로 만들어서 각각의 1번 인덱스에 거리를 저장하고 그 값을 갱신한 후 가장 마지막 값을 출력하려고 했는데 지금 이거 쓰면서 생각해보니 이게 아니라.. 거리의 최댓값을 찾아야 되네...? 아 문제 좀 제대로 읽을 걸 완전 다르게 이해하고 문제 풀고 있었다. 지금까지 푼 코드라도 올릴까 했는데 아예 다른 알고리즘이라 ㅋㅋ 다 풀고 나면 그때 올려야겠다..... 😭 #210718 사실 어제 모각코 할 때는 귀찮아서 종이 없이 머리로만 구상했다. ㅋㅋ 오늘 다시 풀어보려고 종이에 쓰면서 풀었는데 예제는 맞았다. 제출하니까 틀렸지..

분명 과제에서 했던 문제인데, 진짜 조금만 바꿔주면 되는데 왜 이것도 어려운지.. ㅋㅋ 그래도 다 풀었다....! 이건 좀 이따 문제풀이 카테고리에 따로 쓸 거라서 나중에 링크 올려놔야겠다. 2021.07.14 - [Coding/백준] - [Python] 백준 2178번 - 미로 탐색 원래 한 문제 풀려고 했는데 생각보다 금방 풀어서 며칠 전에 풀다가 잠시 미뤄둔 1240번을 시도했다. ... 시도만 했다. w에 넣는 값을 확인한 후 그거에 맞춰서 코드를 수정했는데 이상한 에러가 났다. Fatal Python error: _Py_CheckRecursiveCall: Cannot recover from stack overflow 라는 에러인데 구글링해보니 영어 밖에 안 나와서 아직 제대로 확인 안 해봤다. ..

짜증나서 돌아버릴 것 같다. DP는 익숙하지 않아서 어렵다.. 테이블에 들어갈 요소 생각하고 점화식만 잘 세우면 되는데 그 두 개가 왜 이리 어려울까.. 다 풀고 나서 제출 돌려보니 런타임 에러가 났는데 최대로 끌 수 있는 객차의 수가 달라질 때를 고려하지 않아서 그런 것 같다. 단순합(dp[0]) 부분을 수정해줘야 하는데 어떤 방식으로 해야할 지 생각이 나지 않는다. #런타임 에러 코드 import sys n = int(sys.stdin.readline()) #기관차가 끌고 가던 객차의 수 people = [0] + list(map(int, sys.stdin.readline().split())) m = int(sys.stdin.readline()) #소형기관차가 최대로 끌 수 있는 객차의 수 dp = ..

그리디 알고리즘 공부 2021.06.29 - [HUFS/Algorithm] - Greedy Algorithm (그리디, 욕심쟁이 알고리즘) Greedy Algorithm (그리디, 욕심쟁이 알고리즘) 1. Greedy Algorithm : 당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘 Greedy 알고리즘은 최적해를 구하는 상황에서 사용하는 방법이다. 여러 경우 중 하나를 선택할 때 그 상황에서 가장 좋다고 letalearns.tistory.com 예제는 맞는데 시간 초과가 난다. 이중 for문을 사용해서 그런 것으로 추정되는데 이중 for문 안 쓰고 푸는 방법이 도무지 생각나지 않는다. 코드 길이라도 줄여보려고 다른 방식으로 코드를 하나 더 작성했으나 이것도 이중 for문을 사용해서인지 시간 초과..