분류 전체보기
-
JUNGOL/Intermediate_Coder/그래프탐색-DFS/3428 : 등수 찾기(ranking)코딩 테스트/JUNGOL 2022. 1. 25. 11:24
Intermediate_Coder/그래프탐색-DFS/등수 찾기(ranking) 문제 KOI 본선 대회에 N명의 학생이 참가했다. 이 학생들을 각각 1부터 N까지 정수로 표현하자. 대회가 끝나고 성적을 발표하는데, 이 대회는 전체 학생의 등수를 발표하는 대신, 두 학생 A, B가 대회 본부에 찾아가면 본부는 두 학생 중 어느 학생이 더 잘 했는지를 알려준다. 둘 이상의 학생이 동점인 경우는 없다. 자신의 전체에서 등수가 궁금한 학생들은 둘 씩 짝을 지어서 대회 본부에 총 M번 질문을 했다. 여러분은 등수를 알고 싶은 학생 X와 대회 본부의 질문에 대한 답들로부터, 이 학생 X의 등수 범위를 찾아서 출력한다. 물론 이 학생의 등수는 1등, 즉 전체에서 제일 잘한 경우부터 N등, 즉 전체에서 제일 못한 경우..
-
알고리즘...106일지 2022. 1. 24. 21:27
그래프 구현 준비 그래프는 다음의 표현 방식이 존재한다. 인접 행렬 표현 방식 인접 리스트 표현 방식 그래프는 다음의 종류가 존재한다. 방향 그래프 무방향 그래프 그래프의 순회는 다음의 방법을 쓸 수 있다. 너비 우선 탐색(BFS) 깊이 우선 탐색(DFS) 또, 그래프는 필요에 따라 가중치를 표현할 수 있다. 이에 따라 클래스의 생성자에서 방향, 무방향 그래프를 설정하고 그래프를 출력할 때 순회 방법을 선택할 수 있도록 한다. Graph.h #pragma once #include "../Common.h" #include #include #include using std::string; using std::vector; /// /// 그래프의 간선 처리 방식 /// enum class GraphOption..
-
JUNGOL...183일지 2022. 1. 24. 18:23
Intermediate_Coder/그래프탐색-DFS/등수 찾기(ranking) 문제 KOI 본선 대회에 N명의 학생이 참가했다. 이 학생들을 각각 1부터 N까지 정수로 표현하자. 대회가 끝나고 성적을 발표하는데, 이 대회는 전체 학생의 등수를 발표하는 대신, 두 학생 A, B가 대회 본부에 찾아가면 본부는 두 학생 중 어느 학생이 더 잘 했는지를 알려준다. 둘 이상의 학생이 동점인 경우는 없다. 자신의 전체에서 등수가 궁금한 학생들은 둘 씩 짝을 지어서 대회 본부에 총 M번 질문을 했다. 여러분은 등수를 알고 싶은 학생 X와 대회 본부의 질문에 대한 답들로부터, 이 학생 X의 등수 범위를 찾아서 출력한다. 물론 이 학생의 등수는 1등, 즉 전체에서 제일 잘한 경우부터 N등, 즉 전체에서 제일 못한 경우..
-
JUNGOL...182일지 2022. 1. 21. 13:40
Intermediate_Coder/그래프탐색-DFS/등수 찾기(ranking) 문제 KOI 본선 대회에 N명의 학생이 참가했다. 이 학생들을 각각 1부터 N까지 정수로 표현하자. 대회가 끝나고 성적을 발표하는데, 이 대회는 전체 학생의 등수를 발표하는 대신, 두 학생 A, B가 대회 본부에 찾아가면 본부는 두 학생 중 어느 학생이 더 잘 했는지를 알려준다. 둘 이상의 학생이 동점인 경우는 없다. 자신의 전체에서 등수가 궁금한 학생들은 둘 씩 짝을 지어서 대회 본부에 총 M번 질문을 했다. 여러분은 등수를 알고 싶은 학생 X와 대회 본부의 질문에 대한 답들로부터, 이 학생 X의 등수 범위를 찾아서 출력한다. 물론 이 학생의 등수는 1등, 즉 전체에서 제일 잘한 경우부터 N등, 즉 전체에서 제일 못한 경우..
-
그래프 알고리즘프로그래밍 기초/알고리즘 2022. 1. 21. 13:33
동적 프로그래밍 그래프 기본 개념 현상이나 사물을 정점과 간선으로 표현하는 것을 말한다. 정점(Vertex) 대상이나 개체 간선(Edge) 대상이나 개체 간의 관계 그래프는 간선이 상호 통행이 가능한지, 일방통행만 가능한지에 따라 유향 그래프와 무향 그래프로 나뉜다. 유향 그래프 정해진 방향으로만 이동이 가능한 그래프, 화살표로 간선을 표현한다. 무향 그래프 쌍방으로 이동이 가능한 그래프, 실선으로 간선을 표현한다. 또, 각각의 정점이 가지는 관계의 정도를 간선에 가중치로 표현하기도 한다. 인접 행렬을 이용한 그래프의 표현 각 행, 열을 순서대로 정점을 나타내고 각각의 간선은 해당하는 행, 열의 위치에 값을 할당하는 방식으로 그래프를 표현하여 이해하기 쉽고 간선의 존재 여부를 곧바로 파악할 수 있다. 가..
-
알고리즘...105일지 2022. 1. 20. 17:19
너비 우선 탐색과 깊이 우선 탐색 그래프에서 모든 정점을 탐색하는 방법에는 레벨의 모든 노드를 방문하는 것을 우선하는 너비 우선 탐색(Breath First Search)과 루트에서부터 한 방향으로 리프 노드가 나올 때까지 진행하는 깊이 우선 탐색(Depth First Search)이 존재한다. 너비 우선 탐색 알고리즘 너비 우선 탐색은 먼저 방문한 노드를 먼저 처리하는 FIFO 방식이므로 Queue를 사용한다. BFS 알고리즘 BFS(G, s) { for each v ∈ V - {s} { visited[v] ← NO; } visited[s] ← YES; enqueue(Q, s); while (Q ≠ ∮) { u ← dequeue(Q); for each v ∈ L(u) { if (visited[v] = ..
-
JUNGOL/Intermediate_Coder/그래프탐색-DFS/2462 : 키 순서코딩 테스트/JUNGOL 2022. 1. 20. 16:51
Intermediate_Coder/그래프탐색-DFS/키 순서 문제 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자. 1번 학생의 키 < 5번 학생의 키 3번 학생의 키 < 4번 학생의 키 5번 학생의 키 < 4번 학생의 키 4번 학생의 키 < 2번 학생의 키 4번 학생의 키 < 6번 학생의 키 5번 학생의 키 < 2번 학생의 키 이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 ..
-
JUNGOL...181일지 2022. 1. 19. 16:07
Intermediate_Coder/그래프탐색-DFS/키 순서 문제 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자. 1번 학생의 키 < 5번 학생의 키 3번 학생의 키 < 4번 학생의 키 5번 학생의 키 < 4번 학생의 키 4번 학생의 키 < 2번 학생의 키 4번 학생의 키 < 6번 학생의 키 5번 학생의 키 < 2번 학생의 키 이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 ..