목록코딩 테스트 (186)
미소를뿌리는감자의 코딩
1. 문제https://www.acmicpc.net/problem/2617 2. 접근 방법특정 구슬보다 작은지 큰지를 구분하여 저장해 주었다.예시를 defaultdict로 저장해 주었는데, 아래와 같이 저장하게 된다.heavier[1] = [2, 5]heavier[2] = [4]heavier[3] = [4]lighter[2] = [1]lighter[4] = [3, 2]lighter[5] = [1] heavier[1] 보다 작은 것은, 2, 5 그리고 2보다 작은 4이다.따라서, 이를 dfs로 순환하여 표현되지 않은 값들도 표현이 되도록 하였다. 구슬의 개수//2 보다 더 큰 값을 해당 노드가 저장하고 있다면, 그 노드는 중간에 있을 수 없다.해당 구슬보다 작은 구슬이 mid개 있는 것 or 해당 구슬보다..
1. 문제https://www.acmicpc.net/problem/2573빙산 정복 기념 그림 호호~ 2. 접근 방법 우선 얼음의 위치에 따른, 바닷물이 맞닿아 있는 개수를 base_sea라는 리스트에 저장해 주었다.따라서, 맞닿아 있는 바다의 개수를 계산하면서, 얼음이 있는 위치를 glacier_loc이라는 deque에 저장해 주었다.이를 통해 glacier_loc을 순환하면서, 값들을 수정할 수 있다.이를 이용하지 않는다면, 2중 for문을 사용하게 되어 시간초과가 날 가능성이 높다.또한 문제에서 제시하였듯, 리스트의 맨 위에 줄, 아래 줄, 그리고 왼쪽, 오른쪽 줄은 0으로 채워져 있으므로 범위를 이용할 경우가 있을 때, 1 glacier[0, 0, 0, 0, 0, 0, 0][0, 2, 4, ..
1. 문제https://www.acmicpc.net/problem/14888 2. 접근 방법어떻게 연산자들의 경우의 수를 표현할 수 있을까 고민해 보았다.처음에 잘 생각이 나지 않았지만, 섣불리 접근하다간 오히려 시간을 많이 쓸 것 같아서 더 고민해 보았다. - 요런 태도가 코테에서는 중요한 것 같다. (메모메모~)예를 들어 + : 2개- : 1개* : 1개/ : 1개라면, +가 중복 되기에, 중복 case를 제외시켜 주어야 한다. 따라서, dfs를 이용해서dfs(현재 연산 경우의 리스트, 사용하고 남은 연산자 리스트) 로 문제 풀이를 시작한다.만약, 현재 연산자 경우의 리스트의 len이 연산자 개수라면, 해당 리스트를 total 에 append하고 return 한다. 그 외는 for i in range..
1. 문제https://www.acmicpc.net/problem/21606 2. 접근 방법이번 문제는 고생을 너무 많이 했다.........................................진짜처음에 접근 방법을 제대로 잡고 들어갔어야 했는데, 경우에 따라서 코드를 작성하다보니 너무 시간이 오래 걸렸다. 처음에는 각 vertex 별 검정 vertex 까지의 경우를 생각하면서 풀었다. 하지만, 5번 test case 에서 fail 하고 말았다.즉, 다른 접근 방법이 필요로 했다. 몇 시간을 고민하다가 다른 동료 분의 도움을 받아서 풀 수 있었다. (압도적 감사) 이런 다양한 case 들이 있었다. 이제 본격적으로 문제 접근을 해보도록 하자우선 for 문으로 각 vertex를 접근하였다. 검정 v..