Yeon’s Dev Log

BFS, DFS란? 그래프를 탐색하는 방법으로는 BFS와 DFS가 있다. BFS(Breadth-First Search)는 너비우선탐색이고, DFS(Depth-First Search)는 깊이우선탐색이다. BFS는 최대한 옆으로 넓게 이동하는 방법으로, 더이상 옆으로 갈 수 없을때 아래로 이동하기때문에 너비우선탐색으로 불린다. 루트노드와 제일 인접한 노드서부터 차례대로 탐색을 하기때문에 주로 두 노드사이의 최단경로를 찾을때 많이 사용되고 큐를 이용하여 구현된다. DFS는 최대한 아래로 이동하는 방법으로, 더이상 내려갈때가 없을때 다른 브랜치로 넘어가 탐색하기때문에 깊이우선탐색으로 불린다. 주로 미로찾기 문제, 모든 노드를 방문하고자 하는 경우에 사용되며, BFS보다는 성능이 떨어지지만 코드는 조금 간단하다...

이진탐색이란? 이진탐색은 이미 정렬된 배열에서, 특정한 숫자를 찾는 정렬 알고리즘이다. 찾고자하는 숫자를 배열의 중간값과 비교하여, 만약 작다면 왼쪽을 다시 탐색, 크다면 오른쪽을 다시 탐색하면서 숫자를 찾아낸다. 원하는 값을 찾아내면 탐색은 종료되며, 존재하지 않는다고 판단하여도 탐색을 종료한다. 존재하지 않는다고 판단하는 기준은 탐색할 인덱스가 없을때 이다. 구현방법은 반복문을 사용할 수도 있고, 재귀를 사용할 수도 있는데 아래의 코드는 재귀를 사용하여 구현한 것이다. 구현코드 int binarySearch(int arr[], int l, int r, int x) { if (r >= l) { int mid = l + (r - l) / 2; if (arr[mid] == x) return mid; if ..

1) 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 2) 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 3) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 4) 해결방법 전체적인 코드 구조는 백준 15649번의 N과 M 두번째 문제와 비슷하..

1) 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 2) 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 3) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 4) 해결방법 전체적인 코드 구조는 백준 15649번의 N과 M 첫번째 문제와 비슷하다. 아직 첫번째 문제를 풀지 않았다면, 그 문제부터 푸는 것을 추천한다. 2021.04.30 - [백준 문제풀이/Backtracking] -..

1) 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 2) 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 3) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 4) 해결방법 전체적인 코드 구조는 백준 15649번의 N과 M 첫번째 문제와 비슷하다. 아직 첫번째 문제를 풀지 않았다면, 그 문제부터 푸는 것을 추천한다. 2021.04.30 - [백준 문제풀이/Backtrack..

1) 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 2) 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 3) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 4) 해결방법 DFS와 backtracking을 이용하여 푸는 문제이다. n개의 숫자를 'DFS를 통해 완전탐색'하되, 만약 m개의 숫자가 선정되었으면, 'backtracking을 이용하여 그 전의 성공단계'로 돌아와야한다. arr 배열에 m개의 숫..