본문 바로가기
728x90
728x90

C++

[c++][백준 22856][그래프탐색] 트리 순회 - 컴도리돌이 22856번: 트리 순회 노드가 $N$개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자. 순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. www.acmicpc.net 풀이 과정 해당 문제는 중회 순회를 하면서 이동 횟수를 출력을 해야 한다. 그래서 기본 적인 중회 순회 알고리즘에서 전체 이동 횟수 * 2에서 루트 노드에서 오른쪽 노드의 이동 횟수를 뺀 값을 출력하면 된다. 문제는 map 함수를 이용해서 부모 노드가 갖고 있는 자식 노드를 pair를 사용해서 왼쪽 자식 노드, 오른쪽 자식 노드를 표현하였다. 탐색 함수 dfs(int, bool) 탐색을 할 때는 루프 노드부터 시작하고, 해당 노드의 값이 -1일 경우 반환시킨다... 더보기
[c++][백준 21939][multiset] 문제 추천 시스템 Version 1 - 컴도리돌이 21939번: 문제 추천 시스템 Version 1 tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다. 깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다. 만들려고 하는 명령 www.acmicpc.net 해당 문제는 multiset을 이용해서 풀었다. multiset을 값을 삽입할 때 작은 수부터 정렬되어서 삽입이 되는 특징이 있고, 삭제도 해당 값만 안다면 쉽게 삭제도 할 수 있기에 multiset을 이용해서 문제를 풀었다. 먼저 입력을 받을 때 문제 번호와 난이도 순으로 받는다. 나는 해당 값을 {난이도, 문제 번호} 순으로 multiset 함수에 집어넣었다. 그리고 나중에 삭제를 할 때 해당 값을 온전히 받아야 하기에 map 함.. 더보기
[c++][백준 21940][플로이드-와샬] 가운데에서 만나기 - 컴도리돌이 21940번: 가운데에서 만나기 위 조건을 만족하는 도시 $X$의 번호를 출력한다. 만약 가능한 도시 $X$가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다. www.acmicpc.net 해당 문제는 플로이드 와샬로 해결하였다. 일단 플로이드-와샬이 뭔지 알아야 한다. 플로이드-와샬이란 모든 최단 경로를 구하는 방법이다. 플로이드-와샬로 문제 푸는 과정 문제를 해결하기 위한 setting 1. 크기가 n+1이 정방 2차원 배열을 사용하였고, 해당 2차원 배열의 모든 값을 생각보다 큰 수를 입력해서 넣었다. 2. 문제에서 제공하는 경로에 대한 값을 넣어 줬다. 2차원 배열[출발][도착] = 시간 3. 자기 자신으로 가는 것은 없다. 2차원 배열[i][i] = 0 4. 플로이드-와샬 2차원 배열[출발.. 더보기
[c++][백준 21944][multiset + map] 문제 추천 시스템 Version2 - 컴도리돌이 21944번: 문제 추천 시스템 Version 2 recommend, recommend2, recommend3 명령이 주어질 때마다 문제 번호를 한 줄씩 출력한다. 주어지는 recommend, recommend2, recommend3 명령어의 총 개수는 최소 1개 이상이다. www.acmicpc.net 해당 문제는 저번 포스팅에 언급한 version 1가 유사하게 풀었다. 문제에서 알고리즘 분류, 전체 문제, 난이도의 크기에 따라 문제 번호를 출력을 요구했기에 version 1 문제 보다는 map함수와 multiset 함수를 조금 더 사용하였다. 요번 포스팅은 함수의 쓰임만 언급하겠다.. 1. map group 그룹에서 가장 어려운 문제 또는 쉬운 문제를 출력하는 명령어가 있기에 그룹에 해당한 번호에 대.. 더보기
[c++][백준 21937][bfs] 작업 - 컴도리돌이 21937번: 작업 민상이가 작업할 개수 $N$와 작업 순서 정보의 개수 $M$이 공백으로 구분되어 주어진다. 두 번째줄부터 $M + 1$ 줄까지 작업 $A_i$와 작업 $B_i$가 공백으로 구분되어 주어진다. 이때 두 값의 의미는 작 www.acmicpc.net 풀이 과정 해당 문제는 bfs,dfs로 풀어도 될 것같다. 나는 bfs가 친숙해서 해당 문제를 bfs를 풀었다. 입력 값 'process'라는 벡터는 이차원 배열로 구성하였고 해당 노드의 자식 노드를 삽입해줬다. 그 다음 문제에서 요구하는 x라는 입력 값을 받아서 해당 x에 대한 bfs 탐색을 한다. 그 다음부터는 평범한 bfs 코드이다. x 밑에 있는 자식 노드가 있고 해당 자식 노드를 방문하지 않았다면 큐에 삽입하여 해당 자식노드를 탐색.... 더보기
[c++][백준 21938][bfs] 영상 처리 - 컴도리돌이 21938번: 영상처리 화면의 세로 $N$, 가로 $M$ 값이 공백으로 구분되어 주어진다. 두 번째 줄부터 $N + 1$줄까지 $i$번째 가로를 구성하고 있는 픽셀의 $R_{i,j}$, $G_{i,j}$, $B_{i,j}$의 값이 공백으로 구분되어 총 $M$개 주어진 www.acmicpc.net 풀이 과정 해당 문제는 bfs로 문제를 해결할려고 결정하였고, 정말 쉽게 풀었다. 하지만 결과는 실패.. 정말 맞왜틀.. 처음에는 내 로직이 틀린 줄 알았다. 그래서 다른 사람 코드를 보고 참고했는데 좀 더 간단하게 구현했을 뿐이지 별 차이가 없는 정말 쉬운 문제였는데,,, 그래서 반환 값 문제인가 해서 long long으로도 바꿔보고 double형으로도 바꿔봤지만 계속 실패만 하였다. 그래서 차근차근 input.. 더보기
[c++][백준 21923][BFS] 곡예 비행 - 컴도리돌이 21923번: 곡예 비행 동헌이는 모형 비행기 조종 대회에 참가하였다. 이 대회에서는 격자 모양의 공간에서 모형 비행기를 조종하여 얻는 비행 점수로 순위를 매긴다. 격자의 각 칸에는 점수가 부여되어 있고, 비행 www.acmicpc.net 풀이 과정 상향과 하향을 나누어서 BFS 탐색을 하였다. (상향) 방향은 위, 오른쪽으로 오른쪽과 위로만 탐색하며, 정해진 2차원 배열 안에서 시작점부터 오른쪽 모서리까지 이동하면서 최대 이동 값을 저장한다. (하향) 방향은 위, 왼쪽으로 왼쪽과 위로만 탐색하며, 정해진 2차원 배열 안에서 끝점에서 왼쪽 모서리까지 이동하면서 최대 이동 값을 저장한다. 끝점과 시작점의 BFS 탐색이 끝났으면 위치에 따른 둘의 합이 제일 큰 값을 출력한다. #include #include.. 더보기
[c++][백준 21924][최소 신장 트리][MST] 도시 건설 - 컴도리돌이 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net 풀이 과정 알고리즘 코딩 문제를 어느 정도 풀었으면 해당 문제에서 예로 사용한 그림만 봐도 최소 신장 트리 알고리즘으로 풀어야한다는 것을 단번에 알 수 있을것이다. 여기서 최소 신장 트리는 그래프 내의 모든 정점을 포함하는 트리중에서 사용된 간선들의 가중치 합이 최소인 트리이다. 최소 신장트리는 각 간선의 가중치가 동일하지 않을 때 단순히 가.. 더보기

티스토리툴바