미소를뿌리는감자의 코딩

1. 개요DFS와 BFS에 대해서 공부해 보는 시간을 가지게 되었다. 2. DFS & BFS 위 sudo code는 공유 정점이 있더라도 적용할 수 있는 코드이다.이는 3가지 색을 이용해서 방문 전, 방문 중, 방문 후 노드를 나타내어 주었다.흰색 : not visited회색 : visiting검정 : visited를 나타낸다. 시작 정점을 제외한 모든 정점에 대해서 색을 흰색과, parent node는 NIL 그리고 거리는 무한으로 설정해 주었다.시작 노드 색을 grey로 설정하고, 시작 노드는 부모 노드가 없으므로 pi 또한 NIL로 설정해 주었다.시작 노드와의 거리도 0으로 설정해 주었따. BFS 는 queue로도 구현이 가능하기에, Q에 대하서 deque를 선언해 주었다. 또한 queue에서 po..

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 ..

1. .c 파일의 .o 파일 (executable object file)로의 변환 우선 hello.c파일 안에 printf("hello"); 가 들어가 있다고 하자.처음에 cpp 전처리기를 만나, #include 와 같은 라이브러리 코드를 hello.c 파일에 추가해 준다.해당 라이브러리 코드가 추가된 파일은 hello.i 가 된다. 이는 .c파일에서 modified 되었다고 한다.이후 hello.i는 compiler로 들어간다. compiler는 cpp file을 처리해 준다. compiler는 어셈블리어 프로그램을 저장해준다.어셈블리어 프로그램 저장을 통해,  동일한 내용을 다른 언어로 썼어도 assembly 언어로 표현된 후 실행할 수 있게 된다.이후 어셈블리 언어를 처리할 assembler(as)..