풀이12 [알고리즘] 연결 요소의 개수 문제 링크연결 요소의 개수 : https://www.acmicpc.net/problem/11724 문제탐색기본 원리 탐색정점의 갯수와 간선의 수가 주어지면, 연결 요소 (묶음) 가 몇개인지 구해야 하는 문제입니다. 어떤방식으로 그래프가 고립되어있는지 체크하는것이 중요할것으로 보입니다. 시간복잡도와 알고리즘시간제한 : 3초약 3억번의 연산이 가능하다고 가정합니다.정점(N) 및 간선(M) 수 : 각 최대 1000개 , 499,500개 이 그래프의 최대 정점 수는 1000개이며 간선 수는 약 500,000개 입니다.일반적으로 인접리스트를 BFS로 탐색하면 시간복잡도는 O(N+M)입니다.이는 약 50만회로 시간복잡도상 문제가 없습니다. => 인접리스트를 생성하여 그래프를 생성합니다. 그리고 BFS를 사용하여 .. 2025. 1. 20. [알고리즘] 다리 놓기 - DP 문제 링크다리 놓기 : https://www.acmicpc.net/problem/1010 문제탐색기본 원리 탐색강 서쪽에서 강 동쪽으로 다리를 건설하는 것은 곧 M개의 수에서 N개만큼 뽑는것과 같습니다.이 때, 다리가 겹치면 안된다는 것은, 뽑은 N개의 수에 순서를 정할 필요가 없다는 것입니다.이것은 조합으로 C(M,N) 으로 나타낼 수 있습니다. 시간복잡도와 알고리즘시간제한 : 0.5초약 5000만 번의 연산이 가능하다고 가정합니다.서,동 사이트 수 : 최대 29조합에서의 최악의 경우의수는 M과N의 최대치가 같다는 가정하에 C(M,N/2) 으로 알려져 있습니다. itertools.combinations 함수를 사용하여 모든 경우의 수를 구하면 , 최악의경우 C(29,14)가 되며 이것은 문제 예.. 2025. 1. 16. [알고리즘] 부녀회장이 될테야 - DP 문제 링크 부녀회장이 될테야 : https://www.acmicpc.net/problem/2775 문제탐색기본 원리 탐색"a층b호에 살려면 a-1층 1호~b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야한다" 라는 규칙에 따라 수를 나열 한 후 k층 n호에는 몇명이 사는지 구하는 문제이다.기본적으로 0층은 1, 2, 3, 4, 5 ... 이런식으로 나열되며 그에따라 1층은 1, 3, 6, 10 ....순으로 나열될 것이다. 시간복잡도와 알고리즘시간제한 : 0.5초약 5천만 번의 연산이 가능하다고 가정합니다.최대 층,호 : 14 해당 문제의 경우 k층 n호의 거주민수가 어떻게 계산되는지 파악하는것이 우선입니다.각 층,호 의 주민 수를 2차원 리스트에 담았다는 가정하에, k층 n호의 거주민 수 를파이.. 2025. 1. 15. [알고리즘] 피보나치 수 2 - DP 문제 링크 피보나치 수 2 : https://www.acmicpc.net/problem/2748 문제탐색기본 원리 탐색피보나치 수열을 구현하는 문제입니다.피보나치 수열은 n번째 항의 수 를 곧바로 구할수 없는 형태입니다.그러므로 처음부터 n번째 까지 피보나치 수열의 규칙 (다음수 = 현재 수 + 이전 수) 에 따라 다음 피보나치 수를 계산해 나가면 됩니다. 시간복잡도와 알고리즘시간제한 : 1초약 1억번의 연산이 가능하다고 가정합니다.N : 90다음 피보나치수를 구할땐 N-1 회 만큼 이전값+현재값을 해주면 되므로 =O(n) 시간복잡도에서 자유롭다고 볼수 있습니다. 단, 만약 90회 만큼 반복하였을때 변수가 받아들일수 없을만큼 큰 정수가 된다면 추가적인 방법을 생각해야 합니다. 우선 파이썬은 해당.. 2025. 1. 14. [알고리즘] 빙고 - 구현 문제 링크빙고 : https://www.acmicpc.net/problem/2578 문제탐색기본 원리 탐색5x5 빙고를 구현하는 문제입니다.구체적으로는 시간의 흐름에따라 3개의 빙고가 나오는것을 캐치하는 문제입니다.빙고는 가로, 세로, 대각선 3종류가 가능하며 대각선은 5개를 모두 지우는 경우만 가능합니다.그러므로 2차원배열을 사용하여 순차적으로 빙고를 진행하며 3개의 빙고가 나오는것을 계속 감지하는 코드를 짜야 합니다. 시간복잡도와 알고리즘시간제한 : 1초약 1억번의 연산이 가능하다고 가정합니다.빙고 크기 : 5x5빙고의 크기가 5x5로 고정되어있어 시간복잡도상 문제가 없을것으로 생각되지만 시간복잡도를 구해봅니다.빙고게임의 과정을 크게 3가지로 나누면 아래와 같습니다. X표시 : 사회자가 부르는 수에.. 2025. 1. 13. [알고리즘] 덩치 - 구현 문제 링크 덩치 : https://www.acmicpc.net/problem/7568 문제탐색기본 원리 탐색 두 숫자가 모두 차이가 날 때 우위를 가려 등수를 매기는 문제입니다. 단, 조건 정렬을 해서 줄을세워 순위를 매기는것은 애매합니다.예) ['60', '80'], ['56', '88'], ['62', '86'] => 1번과 2번은 동점이고 2번과 3번은 동점이지만 1번과3번은 우위가 가려짐 그러므로 문제에 나와있는 "만일 자신보다 더 큰 덩치의 사람이 k명이라면 그 사람의 덩치 등수는 k+1이 된다" 는 조건을 바탕으로 구현을 해야합니다. 시간복잡도와 알고리즘시간제한 : 1초약 1억번의 연산이 가능하다고 가정합니다.사람수 : 최대 50 명요소 1개당 모든요소를 순환하며 등수를 매기므로, N x N.. 2025. 1. 12. [알고리즘] 나무 조각 - 구현 문제 링크 나무 조각 : https://www.acmicpc.net/problem/2947 문제탐색기본 원리 탐색● 무작위로 배치된 나무 조각을 특정 규칙에 따라 오름차순 정렬시키는 문제입니다.● 버블정렬의 원리와 같으며 매 횟수마다 출력해야 하므로 버블정렬을 구현해야만 합니다. 시간복잡도와 알고리즘시간제한 : 1초약 1억번의 연산이 가능하다고 가정합니다.나무조각 수 : 5 개 나무조각수가 5개로 고정이므로 사실상 시간복잡도에서 자유롭다고 볼수 있습니다. => 이중 반복문을 사용하여 모든나무 조각을 순환 처리하고(1중), 정렬이 완료될때까지 반복(2중) 합니다. 코드설계하기map을 사용하여 숫자를 리스트에 입력 받습니다.마지막을 제외한 리스트를 순회하며 앞의 나무도막과 값을 비교하여 순서를 바꿉니.. 2025. 1. 11. [알고리즘] 커트라인 - 구현 문제 링크 커트라인 : https://www.acmicpc.net/problem/25305 문제탐색기본 원리 탐색● N명의 응시자 중 상위 k명에게 상을주며 그 커트라인을 구하는 것은,성적이 높은순으로 정렬하여 k 번째 점수를 출력하는 것과 같습니다. 시간복잡도와 알고리즘시간제한 : 1초약 1억번의 연산이 가능하다고 가정합니다.최대 학생수 : 1000명 시간복잡도가 O(n log n) 인 정렬 알고리즘은 약 3000회의 연산을 수행하므로 정렬을 사용하는데 지장이 없습니다.=> 그러므로 python 정렬함수인 sorted를 사용하기러 합니다. 코드설계하기성적을 리스트에 입력받습니다. 단, 한줄에 공백을 기준으로 입력되므로 map함수를 활용합니다.리스트를 내림차순 정렬합니다.리스트의 k-1번째 항목을 .. 2025. 1. 10. 이전 1 2 다음