분류 전체보기77 DFS(Depth First Search) 깊이 우선 탐색 IntroductionDFS: 한 우물만 깊게 파다가 막히면 돌아가서 다른 우물을 파는 성향 자세한 내용은 여기가 최고 입니다. 핵심은 방문하는 순서대로 정점을 스택에 쌓고, 방문이 끝나면 스택에서 pop하는 것 입니다.재귀 함수도 스택 메모리 공간에 쌓아올려지는 구조이기 때문에 이를 이용해서도 구현 할 수 있습니다. cf) 메모리 구조 아래 코드는 재귀 함수를 통해서 구현한 DFS입니다. adj: 인접 행렬(간선 리스트)addEdge: u와 v 사이의 간선을 설치하기 위한 함수sortList(): 번호가 작은 정점부터 방문하기 위해 정렬하는 함수 DFS1. dfs()라는 함수 내부에서 오버로딩된 dfs()를 이용하여 0번 노드부터 재귀함수로 실행2. 이미 방문한 정점은 다시 방문하지 않으므로 visit.. 2019. 1. 29. 백준 1012 유기농 배추 풀이 C++ Introductionhttps://www.acmicpc.net/problem/1012 그래프와 DFS 관련 문제입니다. 저는 가뜩이나 공간 지각 능력이 부족한데 이 문제는 제가 거의 처음 풀어본 그래프, DFS 문제이면서 평소에 익숙한 행렬(row, col) 방식이 아닌 좌표평면(x,y) 방식으로 배추밭의 길이가 주어져서 머리 속에서 그림으로 변환하여 이해하는데 굉장히 애를 먹었습니다. main함수 자체는 변수를 입력 받고, 배추가 심어져 있는 부분을 1로 변경해주는 비교적 간단한 작업인데 입력 받아온 값을 dfs 함수에 보내고 탐색하는 과정을 짤 때 가로, 세로와 row, column이 머리 속에서 뒤엉켜서 몇 번이나 혼자 짜는 것에 실패했습니다. 그래서 처음에는 둘 다 사용했던 단위를 제가 더 편한.. 2019. 1. 28. 백준 1918 후위 연산자 풀이 C++ Introductionhttps://www.acmicpc.net/problem/1918 스택의 대표적인 문제 중에 하나인 후위 연산자 문제입니다. 문제 설명에 연산자 순서대로 괄호를 쳐서 후위 연산자로 바꾸는 과정이 나와있었지만 저 방식으로 하면 손으로는 쉽지만 프로그래밍으로 접근 할 때는 괄호를 추가해야해서 더 복잡하다는 생각이 들었습니다. 그래서 다른 분들의 블로그 설명을 보고 해당 규칙대로 풀어보려고 했습니다. 하지만 처음에는 후위 연산자 자체를 제대로 이해를 못해서 코딩할 때 많이 헤매었습니다. 하다 하다 안되서 손으로 계속 중위 연산자를 후위 연산자로 바꾸는 연습을 하고 바꾸는 규칙을 완전히 이해 한 후에 다시 코딩 하니 좀 더 쉽게 코딩할 수 있었습니다.혹시 저 처럼 잘 안되시는 분들은 손으로.. 2019. 1. 20. scanf로 EOF까지 입력 받기 Introductionscanf는 성공적으로 받아온 포맷문자의 수를 return합니다. 만약 에러가 발생하거나 EOF(End of File)을 만나면 -1을 리턴합니다. EOF는 콘솔에서 ctrl + Z or ctrl + D로 입력이 가능합니다. 문자열을 끝날 때 까지 입력 받는 방법 1. while (scanf("%d", &n) != EOF) 2. while (scanf("%d", &n) != -1) 3. while (~scanf("%d", &n)) EOF는 -1을 나타내므로 1과 2는 같은 방법입니다. 3번의 ~는 NOT입니다. -1은 2진수로 표현하면 1111 1111 ... 1111 입니다. -1에 ~를 붙이면 0000 0000 ... 0000 즉 0이 됩니다. 그래서 scanf로 EOF(-1)을.. 2019. 1. 17. 이전 1 ··· 8 9 10 11 12 13 14 ··· 20 다음
