목록코딩 테스트 (186)
미소를뿌리는감자의 코딩
1. 문제https://www.acmicpc.net/problem/1707 2. 접근 방법처음에 이분 그래프 (Bipartite Graph)를 잘 이해하지 못하여 헤맸었다.이에, 이분 그래프에 대한 설명을 찾아보게 되고 문제 풀이의 가닥을 잡게 되었다. 특정 노드에서 인접 노드로 접근하게 되면, color_num을 증가시켜서 넣어주는 방식으로 접근하였다.빨간색, 검정색으로 표현하고 싶었지만, 짝수와 홀수로 표현하는 것이 더 코드 작성이 편리할 것이라고 생각이 들었다. 만약 색이 칠해진 노드에 다시 접근하게 된다면, 저장된 color가 짝수인지 홀수인지 확인하였고, 새로이 저장하고자 하는 값과 일치하는 . 지확인하였다.일치하지 않는다면, 다른 색을 저장하려고 하게 되는 것이며, 이는 이분 그래프의 정의에 ..
1. 문제https://www.acmicpc.net/problem/5639 2. 접근 방법pre order 결과를 가지고, post order의 결과를 도출해야 하는 문제였다. pre order이기에, 순으로 출력될 것이었다.따라서, 처음 주어진 노드의 키는 전체 binary tree의 root node를 나타낼 것이다.따라서, 이를 기준으로 다음으로 주어진 노드를 왼쪽에 배치할 것인지, 오른쪽에 배치할 것인지 결정해 주었다. def get_nodes(): root_num = int(input()) root_node = Node(root_num) while True: try: new_node = Node(int(input())) c..
1. 문제https://www.acmicpc.net/problem/2178 2. 접근 방법처음엔 dfs로 코드를 작성하여 재귀로 문제를 해결하고자 하였다.하지만 지속적인 '시간 초과'가 발생하였고 dfs 를 stack으로 접근해야 하나 라고 생각하게 되었다. def get_maze(y): maze = [] for _ in range(y): m = list(input()) maze.append(m) return mazedef get_shortest_path(i, j, path_count): global shortest_path if i == y-1 and j == x-1 and shortest_path > path_count: shortest..
1. 문제https://www.acmicpc.net/problem/1991 2. 접근 방법오랜만에 전위 순회, 중위 순회, 후위 순회에 대해서 다시 개념을 잡고 가는 문제였다.첫 번째 예제를 바탕으로 더 자세히 알아보았다.근데 A가 root이며 left node, right node가 순차적으로 나온다.이를 정의 한 Class Node에 저장을 통해, 노드의 left node와 right node를 .left와 .right로 접근할 수 있도록 하였다. 전위 순회를 구현하기 위해 Class Node를 작성하였다.class Node: def __init__(self, root, left, right): self.root = root self.left = left ..