본문 바로가기
728x90

Lang/알고리즘

 (9)
[알고리즘/C++] 요세푸스 순열 문제 Josephus problem # 요세푸스 문제 Josephus problem 요세푸스 문제 Josephus problem 혹은 요세푸스 순열 Josephus permutation 이라고 합니다. 자연수 n, k ( k < n )이 있습니다. n명이 동그랗게 앉아있을 때 임의의 한 명부터 순서를 세어 k번 째 사람을 제외합니다. 다음 사람부터 k번째 사람을 제외합니다. 이렇게 제외되는 사람의 순서가 요세푸스 순열이고, 마지막에 남는 (혹은 제외되는)사람을 구하는 문제가 요세푸스 문제입니다. # 알고리즘 이해 n=5; k=3; 으로 가정합니다. 즉 다섯 명이 모여있고, 세 번째 순서일 때마다 제외합니다. # 코드 예제 #include #include using namespace std; int main(){ int n, k, x, re..
[알고리즘/C] 등수 매기기 (브루트 포스: brute force) # 문제 여러명의 점수가 배열로 있을 때, 각 점수의 등수를 매겨야 합니다. 점수 배열이 20 40 10 50 30 이렇게 들어오면 등수는 4 2 5 1 3 로 나와야 합니다. # 브루트 포스 : 전체 탐색 알고리즘 int score[5] = {20, 40, 10, 50, 30}; int rank[5] = {1, 1, 1, 1, 1}; for(int i=0; i
[알고리즘] 너비 우선 탐색 Breadth First Search # 문제 설명 아래 그림과 같은 이진트리를 너비 우선 탐색해봅니다. 간선의 정보를 입력받아 처리합니다. 인접 리스트를 이용합니다. queue 자료구조를 직접 구현합니다. 너비 우선 탐색은 시작 노드부터 인접한 노드들을 모두 우선 방문하는 방식의 탐색 방법입니다. 시작 노드인 노드1을 방문 한 후 노드1에 인접한 노드2, 노드3을 방문합니다. 노드2에 인접한 노드4, 노드5를 방문합니다. 노드3에 인접한 노드6, 노드7을 방문합니다. 노드4는 인접한 노드가 없으므로 끝입니다. 노드5 ~ 노드7은 노드4와 같습니다. 다르게 이야기하면 시작 노드부터 간선 한 번에 인접한 노드들을 순회하고, 간선 두 번에 인접한 노드들을 순회하고, 간석 세 번에 인접한 노드들을 순회하는 방식으로 볼 수 있습니다. # 입출력 예..
[알고리즘/C] 미로찾기 경로탐색 (2차원 행렬 DFS: Depth First Search) ★ 이 미로찾기 경로탐색은 격자판에서 길찾기 알고리즘을 알아보는 2차원 행렬 DFS입니다. 방향 그래프상의 길찾기 알고리즘인 그래프 DFS는 아래 링크에서 확인바랍니다. ★ 또한 인접행렬과 경로탐색의 기초에 대해서도 아래 링크를 참고해주시기 바랍니다. 2022.12.05 - [Lang/알고리즘] - [알고리즘] 인접행렬과 경로탐색 기초 (그래프 DFS: Depth First Search) [알고리즘] 인접행렬과 경로탐색 기초 (그래프 DFS: Depth First Search) # 인접 행렬 (隣接行列, adjacency matrix) 인접 행렬은 노드들이 간선으로 어떻게 연결되어 있는지 나타내는 정사각 행렬입니다. 위 그림을 말로 설명하면 노드 1은 노드 2로 연결되었고, 노드 1은 노 siku314...
[알고리즘] 인접행렬과 경로탐색 기초 (그래프 DFS: Depth First Search) # 인접 행렬 (隣接行列, adjacency matrix) 인접 행렬은 노드들이 간선으로 어떻게 연결되어 있는지 나타내는 정사각 행렬입니다. 위 그림을 말로 설명하면 노드 1은 노드 2로 연결되었고, 노드 1은 노드 3으로 연결되었고, 노드 1은 노드 4로 연결되었고, 노드 2는 노드 4로 연결되었고, 노드 3은 노드 4로 연결되었고, 노드 4는 노드 5로 연결되어있습니다. 이 것을 행렬로 표현하면 행의 1,2,3,4,5는 출발 노드로 열의 1,2,3,4,5는 도착 노드로 하여 다음과 같습니다. 0은 연결되지 않았음 1은 연결되었음을 표현합니다. 1행 2열은 노드 1에서 노드 2로 연결되었음을, 1행 3열은 1에서 3으로 연결되었음을, 1행 4열은 1에서 4로 연결되었음을, 2행 4열은 2에서 4로 연결..
[알고리즘/C++] 합병 정렬 Merge Sort # 문제 설명 n 개의 자연수 배열을 병합 정렬을 이용해 오름차순으로 정렬한다. # 입출력 예 입력 출력 8 7 6 3 1 5 2 4 8 1 2 3 4 5 6 7 8 # 문제 풀이 #include using namespace std; int arr[101], tmp[101]; void d(int left, int right){ int mid; int p1, p2, p3; if(left
[알고리즘/C++] 부분집합 구하기 - 이진트리 완전탐색 (DFS) # 문제 설명 자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요. # 제한사항 1
[알고리즘/C++] 구슬을 나누는 경우의 수 # 문제 설명 머쓱이는 구슬을 친구들에게 나누어주려고 합니다. 구슬은 모두 다르게 생겼습니다. 머쓱이가 갖고 있는 구슬의 개수 balls와 친구들에게 나누어 줄 구슬 개수 share이 매개변수로 주어질 때, balls개의 구슬 중 share개의 구슬을 고르는 가능한 모든 경우의 수를 return 하는 solution 함수를 완성해주세요. # 제한사항 1 ≤ balls ≤ 30 1 ≤ share ≤ 30 구슬을 고르는 순서는 고려하지 않습니다. share ≤ balls # 입출력 예 baslls share result 3 2 3 5 3 10 # 힌트 서로 다은 n개 중 m개를 뽑는 경우의 수 공식 # 문제 풀이 #include #include #include // balls가 30이고 share가 15이면..
[알고리즘/C] 코딩테스트 모스부호 # 문제 설명 머쓱이는 친구에게 모스부호를 이용한 편지를 받았습니다. 그냥은 읽을 수 없어 이를 해독하는 프로그램을 만들려고 합니다. 문자열 letter가 매개변수로 주어질 때, letter를 영어 소문자로 바꾼 문자열을 return 하도록 solution 함수를 완성해보세요. 모스부호는 다음과 같습니다. morse = { '.-':'a','-...':'b','-.-.':'c','-..':'d','.':'e','..-.':'f', '--.':'g','....':'h','..':'i','.---':'j','-.-':'k','.-..':'l', '--':'m','-.':'n','---':'o','.--.':'p','--.-':'q','.-.':'r', '...':'s','-':'t','..-':'u','....
728x90

티스토리툴바