CS/알고리즘 (6) 썸네일형 리스트형 [DFS&BFS] 개념 정리 및 구현 01. 그래프 탐색 알고리즘그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘으로, 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있습니다. 02. 그래프의 구현 방법인접 리스트 표현각 정점과 인점한 정점들을 저장해서 그래프를 표현하는 방법으로,예를 들어 그래프의 저장 공간을 이차원 벡터로 표현한다면, 다음과 같게 됩니다.vector> adjacent;adjacent[i 03. 깊이 우선 탐색(DFS)깊이 우선 탐색은 한 정점으로부터 가장 깊은 노드까지 탐색하고, 더 이상 갈 곳이 없어지면 원점으로 돌아와 다른 노드를 탐색하는 방법으로, 다음 그림과 같이 탐색을 진행합니다. 탐색 순서: 0 -> 1 -> 3 -> (4 -> 1 -> 0) -> 2 -> 5 -> (6 -> 2 .. [백준] 10818번 : 최소, 최대 문제 풀이 방법 [백준] 1110번 : 더하기 사이클 문제 풀이 방법 문제를 보고 생각난 방법은 다음과 같다.1) input이라는 변수에 입력값을 저장한다. 2) b라는 변수에 일의 자리를 저장한다. (이때, 일의 자리는 십과 나머지 연산하여 구한다.) 3) a라는 변수에 십의 자리를 저장한다. (이때, 십의 자리는 일의 자리를 빼고 십으로 나누어 구한다.) 4) c라는 변수에 a+b값을 저장한다.5) result라는 변수에 b*10+c%10을 저장한다. 6) length(사이클의 길이)를 하나씩 늘려준다.7) result가 input과 같아질 때까지 위의 2~6 과정을 실시한다. 이와 같은 방법으로 짠 코드는 다음과 같다. 결과는! [백준] 10828번 : 스택 문제 풀이 방법 [백준] 10773번 : 제로 문제 풀이 방법 문제를 보고 생각난 방법은 다음과 같다.1) 입력받은 숫자를 배열에 저장한다.2) 입력받은 숫자가 0이라면, 최근의 수를 0으로 바꿔준다. (지우는 것과 같다.) 2-1) 이때, 이미 0으로 바뀌어졌을 수도 있다는 것을 고려해 배열에 들어있는 값이 0이 아닐 때까지 while문을 돌려 배열의 인덱스 값을 줄여준다. 2-2) 배열에 들어있는 값이 0이 아니라면, while문을 빠져나와 그곳에 0을 대입해준다.3) for문을 이용하여 배열에 들어있는 값들을 검색해 0이 아닌 값들끼리 더해준다. 위의 방법을 토대로 짠 코드는 다음과 같다. 초기에는 count라는 변수를 선언해주지 않았는데, 그랬을 경우에 input [i-1]이 0일 때마다 i값이 줄어들어 줄어든 i 인.. [백준] 2941번 : 크로아티아 알파벳 문제 풀이 방법 문제를 보고 생각난 방법은 먼저 변경된 크로아티아 알파벳들과 입력값을 각각 배열에 저장한 뒤,strstr 함수와 for문을 이용하여, 입력값에 크로아티아 알파벳이 있다면 dz=를 제외한 나머지의 문자 개수는 2이므로 입력한 값의 문자 개수에서 1씩 빼는 것이었다. 그래서 다음 순서로 코딩을 하였다.1) 크로아티아 알파벳 배열에 저장 2) 입력값 저장3) 입력한 값의 개수 구하기4) for문 이용하여 입력값에서 크로아티아 알파벳 검색5) 있다면 개수 하나 줄이기 이때, dz=는 z=을 포함하므로 나머지 알파벳들처럼 1씩 빼주어도 상관이 없어 다음과 같이 코드를 짰다. 하지만 위의 코드는 예제 2와 4같이 입력한 값에 같은 크로아티아 알파벳이 2번 이상 존재하는 경우를 생각하지 못했고, .. 이전 1 다음
