1. BFS란? - BFS 는 너비우선탐색을 말합니다. - 루트 노드에서 시작하여 인접한 노드를 탐색하는 방법입니다. Q. 너비우선 탐색을 하면 순서가 어떻게 될까요? A. 0 - 1 - 2 - 3 - 4 - 5 -6 1) 특징 - 두 노드사이의 최단 경로를 찾을 때, 임의의 경로를 찾을 때 사용 - 코드가 DFS보단 복잡하지만 속도는 더 빠르다 2) 알고리즘 구현 방법 BFS의 결과 : 1 - 2 - 6 - 3 - 4 -5 - 큐를 이용하여 구현함 void bfs(int st) { q.push(st); visited1[st] = 1; while (!q.empty()) { int now = q.front(); q.pop(); printf("%d ", now); for (int i = 0; i < adj[..

1260번: DFS와 BFS (acmicpc.net) 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 난이도 : 실버2 풀이과정 : DFS는 재귀함수를 이용해서 풀었습니다 [Algorithm] DFS 정리 (tistory.com)

1. DFS란? - DFS 는 깊이 우선 탐색 을 말합니다. - 루트 노드에서 시작하여, 해당 노드들의 자식을 우선적으로 탐색합니다. * 미로찾기로 예시를 들면, 한 방향으로 갈 수 있을 때까지 계속 가다가 더이상 갈 수 없게 되면 다시 가까운 갈림길로 되돌아 와서 다시 탐색을 진행하는 것과 유사합니다. Q. 깊이우선 탐색을 하면 순서가 어떻게 될까요? A. 0-1-3-4-2-5-6 1) 특징 > 모든 노드를 탐색할 때 좋은 방법입니다. > BFS보다 좀 더 간단하지만 느립니다. 2) 알고리즘 구현 방법 DFS의 결과 : 1 - 2 - 3 - 5 - 4 -6 ⓐ 재귀함수 이용 #include #include using namespace std; bool visited[10]; //방문했던 노드를 기억하는..

2309번: 일곱 난쟁이 (acmicpc.net) 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 난이도 : 브론즈2 풀이 과정 : 전형적인 완전 탐색 문제입니다. 저는 9명의 난쟁이의 키를 배열로 입력받아서 모두 더한다음 2명을 빼서 키의 합이 100이되는 경우의 수를 다 탐색해보는 방법으로 풀었습니다. 2명을 빼는 방법은 이중반복문을 이용해서 모든 경우의 수를 다 탐색할 수있게 합니다. 그리고 오름차순으로 출력해야 하기 때문에 입력받은다음 바로 정렬해줬습니다. 코드 : #include #include using n..

1. 완전탐색 1) 개념 : 말 그대로 가능한 모든 경우의 수를 다 탐색하는 것 2) 방법 ⓐ 브루트 포스(Brute-Force) : 영어를 번역하면 무차별 대입이라는 뜻이다. ⓑ 비트마스크(BitMask) : 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법 ⓒ 순열 ⓓ BFS(너비우선탐색) ⓔ 백트래킹 : DFS에 가지치기를 통해 가도되지 않는 루트는 고려하지 않고 탐색하는 완전탐색 기법 2. 해결방법 1) 주어진 문제를 선형 구조로 구조화 2) 구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색 3) 구성된 해를 정리 EX) 10의 약수구하기 - 10의 약수가 될 수있는 모든 자연수를 구조화 (1,2,3,4,5,6,7,8,9,10} - 탐색을 이..

1. 시간복잡도 1) 의미 : 알고리즘이 동작하는데 걸리는 시간을 대략적으로 나타냄 🔎 코드는 최대한 간결하고 빠르게 작동하는 것을 원칙으로 한다. 2) 표기법 ⓐ O(Big O) : 시간의 상한 값(최악의 성능일 때 걸리는 시간) ⓑ θ(theta) : 오와 오메가의 중간(평균) ⓒ Ω(omega) : 시간의 하한 값(최고의 성능일 때 걸리는 시간) - 보통 빅 O표기법을 씀 이유 : 알고리즘이 최악일 때 어떤 성능을 지녔는지 판단해야 사용유무를 판단할 수 있기 때문! (어떠한 알고리즘이 최소 1의 속도가 걸린다고 해도 최악의 경우 N속도가 걸리면 무의미 함) 3) 대표적인 시간복잡도 - O(1) : 상수 시간 : 입력값 n 이 주어졌을 때, 알고리즘이 문제를 해결하는데 오직 한 단계만 거칩니다. - ..

17478번: 재귀함수가 뭔가요? (acmicpc.net) 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 난이도 : 실버 5 오타확인 필수! 풀이과정 : 문제그대로 재귀함수를 이용해서 풉니다 1. n의 값이 함수에 들어오면 0이 될때까지 question~answer03까지 출력후 n--해주고 재귀함수로 다시들어갑니다. (그 후에꺼(end1)는 n의 값대로 출력되겠죠?) 2. n이 0이되면 진짜 답을 출력해줍니다. (question,answer2,end1) 간단해보여도 미리 어떻게 풀건지 메모장에 정리하기 ㅠ..

2960번: 에라토스테네스의 체 (acmicpc.net) 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 난이도 : 실버 4 생각보다 오래 걸렸던 문제였어요 ㅠ 에라토스테네스의 체를 공부하고 관련된 코드를 보면서 짜다가 보통의 에라토스테네스 알고리즘 코드랑 이 문제가 약간 다르잖아요? P를 포함해가지고 제거되는 거라.. 하튼간 쉽지 않았던 문제!! 였습니다. 저한테는... 풀이과정 : 1. visited배열에 2부터 N까지 집어넣는다! (v(2) =2, v(3)=3 ... 이런식으로) 2. i가 2일때는 2, 4, 6, 8.... 3일때는 3,6,9,... 이런식으로 지워져야 하기때문에 이중 fo..

2167번: 2차원 배열의 합 (acmicpc.net) 2167번: 2차원 배열의 합 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 www.acmicpc.net 난이도 : 브론즈1 비교적 쉬운 문제였습니다. 문제 이해만 잘 한다면? 문제 이해가 안가시는 분들을 위해 설명을 해드리자면 2, 3 = 행이 2이고, 열이 3인 배열OR벡터를 생성 밑에 두줄은 배열에 들어가는 수를 뜻하구요 (0,0)=1, (0,1) =2 ... (편의를 위해 배열의 시작을 0,0으로 가정) 3 밑에 세줄이 이해 안가실 거같은데 위와같은 방식으로 더해가는 거랍니다..