[파이썬]코딩테스트 정리 블로그 [파이썬]코딩테스트 정리 블로그

14449 주사위 굴리기, 2642 전개도와 본질적으로 같은 문제다. 14449 문제는 골드4인 반면에 이 1917번 문제는 골드1이다. 이 문제는 분명 overrated되어있다고 장담한다. 왜냐하면, 인터넷에 11가지 전개도를 알아야하는 풀이법이 널리 알려져있기 때문일 것이다. 하지만, 나올지 안 나올지도 모르는 문제를 위해 11가지 전개도를 외우고 다닌다는 것은 너무 비효율적이고, 외우지 않으면 풀 수 없는 문제를 코딩테스트에 출제하지 않을 것이라 생각한다. 그보다 더 효율적인 풀이법은 전개도로 주사위를 굴리며 6가지의 면이 전부 바닥에 닿은 적이 있으면 전개도가 만들어지는 것이고, 1가지의 면이라도 바닥에 닿은 적이 없다면 전개도가 만들어질 수 없는 것이다. 일단은 기본적으로 주사위를 동,서,남,북..

이전에 풀었던 문제인데, 그 때 당시, 해결하지 못하여 풀이를 봤었다. 이번에도 헤매다가 해결했다. 한 번 헤맨 문제는 확실하게 해결하지 못하면 다음에 와서도 헤매는게 맞는 것 같다. 예전에 봤던 풀이를 보니 굉장히 심플하고 센스있는 풀이였다. 하지만, 내 것이 아니었고 또 다른 비슷한 문제에도 그런 해결책을 떠올릴 수 있을까? 답은 아니었다. 조금 투박해보이지만 여러 문제에 공통적으로 적용되는, 내가 시험장에서 떠올릴 수 있는 풀이대로 풀었다. 3차원 배열+alpha가 들어간 문제로 alpha가 낯설고 헷갈리는 문제다. 일단 거울의 갯수가 1개 늘어나는 8가지 상황을 정리해보았다. 위 그림의 8가지 상황을 2가지 조건으로 압축할수 있다. 행 1칸 이동 후 열 1칸 이동, 열 1칸 이동 후 행 1칸 이동..

22946 원 이동하기 1이랑 똑같이 하면 될 줄 알았다. 트리를 만든 후 특정 경로의 길이와 추적.. 트리 만드는 코드는 그대로하고 바로 경로 길이와 추적하는 코드를 작성하였지만 실행 시간 초과.. 멘붕이었다. 원 이동하기 2, n의 갯수는 최대 20만개 원 이동하기 1, n의 갯수는 5천개 시간복잡도의 엄청난 차이가 있을 것이다. 원 이동하기2는 모든 원의 y 좌표를 0으로 고정해놨다. 일일이 두 원의 거리 공식을 계산하는 것이 아니라 괄호쌍 판별의 개념을 이용하여 트리를 만들어야한다. 여기서 최소힙의 개념을 이용해야한다. 이유는? 좌표평면의 가장 왼 쪽에 있는 x좌표부터 오른쪽 좌표까지 순서대로! 왼쪽부터 오른쪽까지 촤르르 비교하게끔 문제의 예시로 과정을 설명하자면 스택에 좌표평면인 0을 넣는다. ..

문제 풀이 과정을 2가지로 나눌 수 있다. (1) 트리 만들기 (2) 트리의 지름 찾기(두 점을 선택했을 때 길이가 가장 긴 경로 찾기) 예제 3의 그래프를 트리로 나타내보면 0은 좌표 평면이다. 필자는 트리 만들기를 DFS로 구현했다. 반지름이 가장 큰 좌표평면에서 시작하여 그 다음 반지름이 가장 큰 원인 1로 시작하여 그 다음 3,그리고 포함 관계가 없으니 다시 1로 되돌아와서 4, 다시 1로 돌아와서 없으니 다시 좌표평면... 사고의 과정은 이렇다. 그래서 원의 정보를 내림 차순 정렬해주고 첫 번째에 좌표평면의 정보를 입력해주었다. 그리고 길이가 가장 긴 경로를 찾을 때, 트리의 지름 공식을 이용하면 코드의 실행 시간이 상당히 단축 되고, 제곱근 계산도 math.sqrt()를 이용해주었더니 코드 수..

사전 순으로 출력해라하면 바로 떠올려야된다. for i in range(n): graph[i].sort() 위 과정을 빼먹으면 90%에서 오답처리 된다. 처음엔 dfs로 했었다. dfs는 경로 파악이 쉽고 직관적이니까 하지만 시간초과가 났다. 잠시 까먹었다. 최단 거리 문제는 bfs로 해결해야 된다는 것을 문제 풀이 과정은 bfs를 2번 한다. (1)s에서 e로 가는 최단 경로 찾기 (2)e에서 s로가는 최단 경로 찾기 e에서 s로 갈 때 (1)과정에서 방문한 노드는 방문하면 안되니 x,path=q.popleft() q.append((y,path+[y]) 각각 큐마다 자신이 걸어온 경로를 저장시키는 방식으로 해결했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ..

너 사이클 알아? 사이클 찾을 수 있어?라고 묻는 문제다. 어려운 문제는 아니지만 사이클을 구별하는 코드를 짜본 숙련도가 부족하여 애를 먹었다. 숫자 고르기와 거의 똑같은 문제이다. 사이클의 정의: 처음 노드(루트 노드)에서 시작하여 다시 처음 노드로 되돌아온다. 모든 정점에서 완전 탐색을 하는데 이미 방문한 노드는 방문 처리를 해준다. 이 과정에서 사이클이 아닌 노드가 방문처리가 되어 사이클로 잘 못 판별이 될 수 있는데 이 때 res(cycle) 배열에 그 값이 있나 없나로 해결할수 있다. 그리고 만약 진짜 사이클이 맞다면 사이클의 정의인 처음 노드에서 시작하여 처음 노드로 되돌아온다를 그대로 수행해주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12..

가장 근본적인 방식은 모든 정점에서 시작해보는 완전 탐색일 것이다. 한 정점과 한 정점 사이의 최대 거리니까 하지만, dfs로 시도해보니 시간초과가 나고 bfs로 시도해보니 간당간당하게 통과한다. 결국 목적은 코딩테스트 통과고 문제 풀이니 미리 푸는 개념을 알면 장땡이다. 1)임의의 한 노드에서 시작해서 가장 거리가 먼 노드를 찾고 2)그 노드에서 가장 먼 노드를 찾아주면 된다. 3) 1,2 과정에서 구한 거리를 더해주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 import sys from collections..

BOJ 16946 벽 부수고 이동하기 4와 같은 문제이다. 지역탐색을 하면서 각 원소에 그룹의 번호를 매기고 그 그룹을 이루는 원소 수를 저장하는 방식 여기서 주의해야할 점은 그룹을 넣을 때 set() 자료구조를 사용해야한다는 점이다. 그렇지 않으면 시간초과가 난다. 아무래도 배열을 이용하면 거기서 시간이 많이 잡아 먹나보다. set()를 쓸 때는 써야한다는 교훈을 준 문제다. 시간 초과 코드와 맞춘 코드 2가지를 남긴다. [시간 초과 코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 5..