본문 바로가기
728x90
728x90

Language

[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++][백준 21923][BFS] 곡예 비행 - 컴도리돌이 21923번: 곡예 비행 동헌이는 모형 비행기 조종 대회에 참가하였다. 이 대회에서는 격자 모양의 공간에서 모형 비행기를 조종하여 얻는 비행 점수로 순위를 매긴다. 격자의 각 칸에는 점수가 부여되어 있고, 비행 www.acmicpc.net 풀이 과정 상향과 하향을 나누어서 BFS 탐색을 하였다. (상향) 방향은 위, 오른쪽으로 오른쪽과 위로만 탐색하며, 정해진 2차원 배열 안에서 시작점부터 오른쪽 모서리까지 이동하면서 최대 이동 값을 저장한다. (하향) 방향은 위, 왼쪽으로 왼쪽과 위로만 탐색하며, 정해진 2차원 배열 안에서 끝점에서 왼쪽 모서리까지 이동하면서 최대 이동 값을 저장한다. 끝점과 시작점의 BFS 탐색이 끝났으면 위치에 따른 둘의 합이 제일 큰 값을 출력한다. #include #include.. 더보기
[c++][백준 21919][에라토스테네스의 체][유클리드 호제법] 소수 최소 공배수 - 컴도리돌이 21919번: 소수 최소 공배수 수열 중에 소수는 2, 3, 5가 있다. www.acmicpc.net 풀이과정 1. 주어진 입력 값중에서 소수가 존재하는지 판정한다. -> 에라토스테네스의 체를 이용하여 소수를 찾는다. 에라토스테네스의 체 : 소수란 약수가 오로지 1인 수이다. 즉, 1을 제외한 수의 배수가 되는 수는 소수가 아니다. 에라토스테네스의 체는 이러한 소수의 개념을 이용한 알고리즘으로 임의의 수 n까지의 소수르 구하고자 할 때 2부터 n의 제곱근까지 돌며 모든 배수들을 소수에서 제외시키는 방식이다. 시간 복잡도 : O(Nlog(logN)) 2. 소수가 존재할 경우 -> 유클리드 호제법을 이용하여 최대 공약수를 구한다. 시간 복잡도 : O(log(N)) 3. 주의 사항 : 최소 공배수의 크기를 고.. 더보기
[c++][백준 13023][DFS] ABCDE - 컴도리돌이 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 풀이 과정 - 모든 노드들은 ABCDE 친구 관계가 성립하는지 그래프 탐색을 한다. - 방문한적이 없는 노드는 해당 DFS로 탐색하고 깊이를 1 증가 시킨다. 깊이가 총 5번이면 관계가 성립 되었기에 ans 값을 true로 설정하고 return 해준다. - dfs로 탐색이 끝났는데 ans 값이 false 면 해당 탐색했던 노드는 다시 방문 표시를 false로 설정한다. #include #include #include using namespace std; int n,m; map friends; vector visited; bool ans = false; void dfs(.. 더보기
[c++][백준 9663][BFS] N-Queen - 컴도리돌이 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 과정 - 퀸은 가로, 세로, 대각선으로 나아갈 수 있는 말이다. 즉, 퀸 하나를 놓으면, 그 퀸과 같은 가로, 세로, 대각선에는 또 다른 퀸을 놓을 수 없다. - 해당 문제는 dfs의 재귀 호출로 해결하였으며, 2차원 배열과 1차원 배열 두 가지로 해결을 하였다. 1차원 배열을 사용하는 게 미숙하여 다른 블로거님들의 풀이를 보면서 이해하면 문제를 풀었고 혼자 풀 때는 1차원 배열을 풀어야겠다는 생각을 못하여 2차원 배열로 해결하였다. - 0번째 행부터 각 행에 대해 각각 .. 더보기
[c++][백준 15686][prev_permutaion] 치킨 배달 - 컴도리돌이 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net * 풀이 과정 1. 치킨 집 수에서 최대 M개를 선택해야 하기 때문에 본 문제는 순열 문제로 인식. prev_permutaion으로 문제를 해결하였다. 2. 초기 치킨집의 개수로 순열을 돌려서 시간 초과가 발생하였다. ->해결 방안) combination이라는 치킨 집의 개수정도의 크기로 할당한 배열을 생성하여 인덱스가 0부터 m까지 true로 설정하였다. 치킨집을 순열로 돌리지 않고 combination 배열을 순열로 돌려 해당 값이 fal.. 더보기
[c++][백준 2146][BFS] 다리 만들기 - 컴도리돌이 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net * 풀이 과정 1. 육지와 육지 사이의 구분이 필요하기 때문에 육지마다 번호를 표시하였다.(처음 육지를 1로 입력받는 것을 -1로 입력받았다.) 2. 육지와 육지 사이의 다리를 놓는다. 1) 번호에 따른 육지의 x, y 값들을 queue에 넣고 방문 표시를 한다. 2) 다른 육지 번호가 나오면 다리의 값을 return 한다. 3) 바다가 나오면 queue에 넣고 다리가 설치했다고 가정을 하고 bridge 값도 +1을 시켜서 queue에 넣는다. 해당 좌표는 방문 표시.. 더보기
[프로그래머스][level2][C++][BFS] 찾아라 프로그래밍 마에스터 - 게임 맵 최단거리 - 컴도리돌이 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr N * M 행렬에서 최단 거리를 보장해주는 탐색 알고리즘인 BFS를 사용하였다. 단순히 N*M의 범위를 넘지 않고 벽이 아닌 곧이 있을 경우 해당 값을 큐에 삽입 후 좌표의 값을 1 증가시켰다. 최종적으로 반환 값은 N*M 좌표의 값을 반환시켰다. 하지만 해당 값이 1인 경우 모든 벽에 둘러 쌓여서 탐색을 하지 못한 경우이기에 -1 값을 반환하도록 설정하였다. #include #include using na.. 더보기

티스토리툴바