본문 바로가기

전체 글

 (351)
[BOJ] 1753. 최단경로 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 한 점 시작, 모든 거리 : 다익스트라 - 간선, 인접리스트 저장 - 거리 배열 무한대로 초기화 - 시작점 : 거리 배열 0, 힙에 넣어주기 - 힙이 빌떄까지 다음을 반복 - 최신값인지 먼저 확인 - 간선을 타고 간 비용이 더 작으면 갱신 2. 시간복잡도 - 다익스트라 : O(ElogV) 3. 자료구조 - heap : (..
[BOJ] 16398. 행성 연결 https://www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - MST 이용 - 행성의 개수를 입력, 행성 간의 거리 비용를 2차원 배열로 입력 (Cij) - [비용, 목적지 행성]의 형태로 행성의 인접리스트를 생성 - heap이 빌때까지 다음을 반복 - 힙에서 최솟값을 꺼내고 방문 여부를 체크 - 방문하지 않았다면 result에 비용을 추가, 방문을 했다면 pass - 인접리스트에 인덱스 값을 가져와서 방문하지 않은 행..
[BOJ] 4386. 별자리 만들기 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - MST 이용 - 입력하는 2차원 배열 x, y를 입력 - 별들 사이의 거리를 계산후에 star_dis 리스트에 append - heap에 초기값 [0, 1]을 저장 - heap이 빌때까지 반복 - 힙의 최소값을 pop후에 해당 별 좌표의 방문 여부를 체크 - result에 비용 추가 - 방문하지 않았다면 방문 체크하고 해당 별의 좌표가 포함된 인접리스트를 fo..
[BOJ] 1647. 도시 분할 계획 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 1. 해결방법 1. 아이디어 - MST 이용 - 입력하는 a, b ,c를 이용해서 간접리스트에 append - 힙에 시작점을 저장 - 힙이 빌때까지 다음의 내용을 반복 - 힙에서 최솟값을 꺼내고 방문 여부를 확인 - 방문하지 않았다면 인접리스트를 이용해서 인접노드를 힙에 push, 방문했자면 pass - 비용을 result에 추가 2. 시간복잡도 - O(Mlo..
[BOJ] 1922. 네트워크 연결 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - MST 이용 - 입력하는 a, b ,c를 이용해서 간접리스트에 append - 힙에 시작점을 저장 - 힙이 빌때까지 다음의 내용을 반복 - 힙에서 최솟값을 꺼내고 방문 여부를 확인 - 방문하지 않았다면 인접리스트를 이용해서 인접노드를 힙에 push, 방문했자면 pass - 비용을 result에 추가 2. 시간복잡도 - O(MlogM) 3. 자료구조 - 힙 : [비용, 연결 노드] - 방문 : chk[] - 인접리스트 : [비용, 연결 노드] """..
[BOJ] 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 1. 해결방법 """ 1. 아이디어 - MST 기본문제 : 외우기 - 간선을 인접리스트에 삽입 - 힙에 시작점 삽입 - 힙이 빌때까지 다음 작업을 반복 - 힙의 최솟값을 꺼내서 해당 노드에 방문 여부를 확인하고 안했다면, - 방문 표시, 해당 비용 더, 연결된 간선들 힙에 삽입 2. 시간복잡도 - O(ElogE) 3. 자료구조 - 간선 저장 되는 인적..
[BOJ] 2579. 계단 오르기 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 첫 번째 계단의 값을 초기 값을 result에 append - 두 번째와 첫번째의 합, 두 번째를 비교해서 큰 값을 result에 append - 세 번째는 첫 번째와 세 번째 합, 두 번째와 세 번째의 합을 비교해서 큰 값을 result에 append - 3번째 부터 n번째 까지 for문을 돌린다. - 네 번째는 네 번째 인덱스와 result[i-2]의 합과 네 번째 ..
[BOJ] 1003. 피보나치 함수 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 피보나치 수열을 이용해서 1이 출력된 횟수와 0이 출력된 횟수를 카운트 한다. - 카운트 된 횟수를 배열에 append해서 print 2. 시간복잡도 - O(40N) == O(N) """ 처음에 zero는 1,0로 나열되고 one은 0,1로 나열된다. 그 이후의 n번째부터는 피보나치 수열(N2 = N1 + N0)로 나열된다. 그렇다면 이제, 규칙을 가지고 구현해보자. 0과 1의 초기배열을 먼저 만들어준다. 0은 [1,0] 1은 [0,1] 로 정해져있음. ..

티스토리툴바