본문 바로가기

알고리즘 문제/BOJ17

[BOJ][2003] 수들의 합 2 문제 : https://www.acmicpc.net/problem/2003 부분합 + 투포인터 로 풀었다. N개의 수를 입력받으면서 부분합 배열을 만든다.subSum[i] = i까지 수들의 합. 인덱스 변수 2개를 준비한다. (l, r)2개의 변수는 부분합의 범위를 구하는데 사용되며 범위는 (l, r] 이다.범위가 (l, r] 일 때 해당 부분 배열의 합은 subSum[r] - subSum[l] 이 된다. l, r을 0에서부터 증가시키면서 해당 부분 배열의 합이 M과 같다면 정답이 될 수 있는 경우이다.합이 M보다 작다면 부분 배열의 합이 더 커져야 하므로 r을 증가시키고M보다 크다면 합이 더 작아져야 하므로 l을 증가시킨다. 시간복잡도는 O(N). 소스코드 : https://gist.github.com.. 2019. 2. 16.
[BOJ][1504] 특정한 최단 경로 문제 : https://www.acmicpc.net/problem/1504 최단거리를 구하는 문제이다.플로이드 알고리즘으로 먼저 모든 정점 간의 최단 거리를 구한다.1 -> N 까지 이동하는데 반드시 지나야 하는 지점 2개가 a, b라면나올 수 있는 경로는 1 -> ... -> a -> ... -> b -> ... -> N1 -> ... -> b -> ... -> a -> ... -> N위 경로 2개이다. 따라서 1 -> a 최단 거리 + a -> b 최단거리 + b -> N 최단거리1 -> b 최단 거리 + b -> a 최단거리 + a -> N 최단거리위 2개 중 짧은 거리가 정답이 된다.만약 구한 짧은 거리가 무한대라면 불가능한 경우이므로 -1을 출력한다. 소스코드 : https://gist.gith.. 2019. 1. 27.
[BOJ][1516] 게임 개발 문제 : https://www.acmicpc.net/problem/1516 전형적인 위상정렬 문제.입력값들로 위상 정렬을 위한 그래프를 먼저 만든다.건물의 cost 정보를 배열에 따로 저장해둔다. 큐를 하나 만들어서 우선시 개발되어야 하는 건물들이 없는 건물 인덱스를 모두 넣는다.큐에 들어갈 때 각 건물이 완성되기까지 걸리는 최소 시간이 정해진다.처음 큐에 값을 세팅할 때는 자기 자신이 만들어지는데 걸리는 시간이 각 건물이 완성되기까지 걸리는 최소 시간이 된다. 큐를 pop하면서 가져온 인덱스 건물(A)과 앞서 만든 그래프에서 간선을 가지고 있는 건물(B)에서 해당 간선 (A -> B)을 제거한다.간선이 있다는 뜻은 B 건물을 만드는데 A 건물이 우선시되어 만들어져야 한다는 의미이다.따라서 B 건물을 만.. 2019. 1. 20.
[BOJ][3665] 최종 순위 문제 : https://www.acmicpc.net/problem/3665 위상정렬 문제다.등수가 3등인 사람은 1, 2등이 정해지는 경우 3등이 정해진다.이를 그래프로 나타내면 위와 같다. 1등은 앞에 아무도 없는 경우 1등이다.2등은 1등이 정해져서 화살표가 없어지면 2등 앞의 등수가 아무도 없게되고 2등이 정해진다.3등도 마찬가지로 1, 2등이 정해지면 3등이 정해진다. m개 등수가 바뀌는 쌍이 주어지면 2개 화살표를 반대로 바꾼다.만약 m이 2이고 (1,2), (2,3)이 입력값으로 주어지면 위 그림과 같이 화살표가 바뀐다.이때, 1, 2, 3 사이에는 싸이클이 생겨서 1등을 정할 수 없게 되서 IMPOSSIBLE을 출력한다.모든 등수 뿐만 아니라 2개 이상의 등수 사이에 위와 같이 싸이클이 발생.. 2019. 1. 19.
[BOJ][1181] 단어 정렬 문제 : https://www.acmicpc.net/problem/1181 문제 조건 중 단어가 여러 번 입력된 경우 한 번씩만 출력을 하라는 항목이 있다.그래서 중복을 제거하기 위해 set을 이용해서 풀었다.그리고 set의 정렬 조건을 수정하였다. 정렬 조건은만약 비교하는 문자열 2개의 길이가 다르다면 앞에 있는 문자열이 길이가 더 짧은 경우 true, 앞에 있는 문자열이 길이가 더 긴 경우 false를 반환.문자열 2개의 길이가 같다면 사전순 정렬로 되어있으면(앞에 있는 문자열 < 뒤에 있는 문자열) true, 아닌 경우 false를 반환한다. C++ set.insert 의 시간복잡도는 O(log(set.size()) 이므로, 총 시간복잡도는 대략 O(NlogN) 소스코드 : https://gist... 2019. 1. 6.