본문 바로가기

알고리즘/백준

 (263)
[백준] 2263번 : 트리의 순회 https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 해당 문제는 분할정복과 재귀를 사용하여 문제를 해결 하였습니다. 문제를 풀기 이전에 트리의 개념에 대하여 학습이 필요 합니다. 트리의 순회는 3가지가 있습니다. 선위순회(프리오더), 중위순회(인오더), 후위순회(포스트오더) 가 있습니다. - 선위순회(프리오더) : 루트 노드 -> 왼쪽 노드 -> 오른쪽 노드 순으로 방문을 하는 방식 - 중위순회(인오더) : 왼쪽 노드 -> 루트 노드 -> 오른쪽 노드 순으로 방문을 하는 방..
[백준] 1197번 : 최소 스패닝 트리 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 해당 문제는 Union, Find 문제로 최소 신장 트리를 구하는 문제이다. 간선의 개수를 입력받고, 간선을 짧은순으로 정렬한뒤 순서대로 정점을 Union 하는데, 사이클이 생기지 않게 Find로 부모를 확인한뒤 Union 하면된다. V, E = map(int, input().split()) parent = [v1 for v1 in range(V+1)..
[백준] 17472번 : 다리 만들기 2 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 해당 문제는 각각의 그룹을 나누는 과정을 너비우선탐색으로 구하였고, 그룹 A에서 그룹 B까지 갈 수 있는 다리 경로를 모두 구한다. 그러니까 특정 그룹에서 다른그룹까지 갈 수 있는 다리의 경로를 깊이우선탐색으로 구한다. 다리의 경로를 구했으면 해당 그룹으로부터 다른그룹까지 다 연결되어있으면서 최소거리를 구해야하니, 최소신장트리를 이용하면 된다. 코드로 구현하면 다음과 같다. ..
[백준] 1011번 : Fly me to the Alpha Centauri https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 해당 문제는 다이나믹 문제로 해결하려 하였으나 메모리 초과가 발생하였습니다. 방법이 떠올리지 않아서 아래의 글에서 규칙을 알게되었습니다. https://eunhee-programming.tistory.com/99 코딩테스트 준비 - 백준 1011번 풀이/자세한 풀이(파이썬) 백준 1011번 문제 코드는 맨 아래 있습니다. 1. 문제 2. 풀이 3. 코드..
[백준] 2573번 : 빙산 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 해당 문제는 너비우선탐색 으로 문제를 해결하였습니다. 빙산을 녹이는 함수 ( 너비우선탐색으로 구현 ), 빙산의 그룹의 개수를 체크하는 함수 ( 너비우선탐색으로 구현) 으로 구현하였습니다. 그룹의 개수가 2이상일경우 년도를 출력하고 그룹의 개수가0 인경우는 모두 바다이기때문에 0을 출력합니다. from collections import deque N, M = map(int, input().sp..
[백준] 4991번 : 로봇 청소기 https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 해당문제는 다이나믹프로그래밍, 비트마스킹, 완전탐색, 깊이우선탐색, 너비우선탐색을 활용하여 문제를 해결 하였습니다. 너비우선탐색으로는 0과 *, *과* 사이의 거리를 구하였고, dp 테이블에 각각의 사이를 메모리제이션 하였습니다. 완전탐색과 깊이우선탐색, 비트마스킹으로 모든 경우의수를 방문 합니다. from sys import stdin from collections import deque input = ..
[백준] 1194번 : 달이 차오른다, 가자. https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net 해당 문제는 비트마스킹 및 너비우선 탐색으로 문제를 해결 하였습니다. 깊이, 너비중 너비를 고른 이유는 최소거리를 구해야 하는 문제는 너비우선 탐색이 더 편하기 때문입니다. 키를 얻을때마다 새로운 탐색범위가 생기고 문을 다 열어보면서 1을 찾아가는 식으로 문제를 해결 하였습니다. OR 연산과 AND 연산을 통하여 Key를 등록하는 로직과 해당 Door를 방문하였을때 ..
[백준] 1806번 : 부분합 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N O(N) 의 시간복잡도로 문제를 해결 할 수 있다. p1과 p2로 포인터를 2개를 두고, p1=0 인상태 p2=1인 상태 그리고 초기 ..

티스토리툴바