본문 바로가기
728x90
728x90

백준

[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 풀이 과정 알고리즘 코딩 문제를 어느 정도 풀었으면 해당 문제에서 예로 사용한 그림만 봐도 최소 신장 트리 알고리즘으로 풀어야한다는 것을 단번에 알 수 있을것이다. 여기서 최소 신장 트리는 그래프 내의 모든 정점을 포함하는 트리중에서 사용된 간선들의 가중치 합이 최소인 트리이다. 최소 신장트리는 각 간선의 가중치가 동일하지 않을 때 단순히 가.. 더보기
[c++][백준 14499][구현] 주사위 굴리기 - 컴도리돌이 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 풀이 과정 더 쉽게 풀 수 있는 방법이 있을거 같지만 시간을 재고 푸는 바람에 하드 구현을 했던거 같다.. 방향 값이 입력 받을 때마다 먼저 주사위를 이동시켜서 바깥으로 이동할 경우는 제외시켰다. 안쪽으로 이동할 경우 rotation 함수를 실행 시키는데 해당 함수는 방향과 이동된 좌표(주사위 입장에서는 바닥)를 넘겨 주었다. 그 이후에는 간단하게 구현하는 방법이 생각나지 않아서 주사위의 배열 값을.. 더보기
[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.. 더보기

티스토리툴바