본문 바로가기

백준17

[알고리즘] 병든 나이트 문제 링크 병든 나이트 : https://www.acmicpc.net/problem/1783 문제탐색기본 원리 탐색체스에서의 나이트의 기본 이동반경을 4가지로만 제한하여 모든경우의 수 중 최대값을 구하는 문제입니다.문제를 이해하고 풀이법을 찾아가는 과정이 중요합니다. 시간복잡도와 알고리즘시간제한 : 2초약 2억번의 연산이 가능하다고 가정합니다.N,M의 크기 : 20억 시간복잡도가 O(n) 인 알고리즘 조차도 20억을 넘어가며 시간초과가 나게 됩니다. 즉 구현은 물론이며 반복을 한번이라도 사용할수 없는 문제이므로 해당 문제는 수학적인 수식으로 해결할 수 있는문제라고 판단할 수 있습니다. => 규칙을 찾고 수식으로 해결하는 그리디 해결법을 사용합니다. 코드설계하기N과  M의 값을 입력받습니다.아래 규칙에 따.. 2025. 4. 12.
[알고리즘] 쇠막대기 문제 링크 문제명 : https://www.acmicpc.net/problem/10799 문제탐색기본 원리 탐색입력된 문자열을 순차적으로 처리하면서 정답을 도출해 내야합니다. 시간복잡도와 알고리즘시간제한 : 1초약 1억번의 연산이 가능하다고 가정합니다.문자열 최대수 : 10만시간복잡도가 O(n²) 인 알고리즘은 약 100억회의 연산이 필요하므로 시간복잡도를 초과하게 됩니다.2중첩이상의 for문은 불가합니다. => stack을 활용하여 한번의 for문으로 "구현" 합니다. 코드설계하기라인을 입력받습니다.아래 규칙에따라 반복문을통해 문자열을 순회합니다.( 다음항목이바로 ) 일경우 레이저로 판단레이저가 아닌경우 ( 이 나오면 리스트에 값 1 하나 추가하며 정답에 +1만약 레이저로 판단될시, 리스트의 길이만큼 .. 2025. 4. 8.
[알고리즘] 결혼식 문제 링크 결혼식 : https://www.acmicpc.net/problem/5567 문제탐색기본 원리 탐색상근이를 기점으로 구성된 양방향 그래프에서 거리가 2인 노드수를 구하는 문제입니다. 시간복잡도와 알고리즘시간제한 : 1초약 1억번의 연산이 가능하다고 가정합니다.동기의 수  : 500명거리가 2인 노드를 탐색하려면 범위탐색에 좋은 BFS를 사용할 수 있습니다. BFS의 시간복잡도는 O(N+m)으로 약 1만회로 문제없습니다. 하지만 거리가 2로 고정되어 있으므로 간단하게 그래프를 인접리스트로 구현한 뒤 상근이 친구의 친구들을 모두 집합으로 묶는 방법을 사용합니다.=> 인접리스트를 활용한 집합연산을 수행합니다. 코드설계하기입력을 인접리스트로 받습니다.집합에 상근이와 상근이 친구를 포함합니다.상근이 친.. 2025. 1. 23.
[알고리즘] 도비의 난독증 테스크 문제 링크도비의 난독증 테스크 : https://www.acmicpc.net/status?user_id=dlehdql&problem_id=2204&from_mine=1 문제탐색기본 원리 탐색주어진 영단어를 사전순으로 정렬해야합니다.단, 대문자 소문자를 구분하지 않는다는것을 유의해야합니다. 시간복잡도와 알고리즘시간제한 : 1초약 1억번의 연산이 가능하다고 가정합니다.최대 단어 수 : 1000 파이썬 정렬함수 sorted 의 시간복잡도는 O(n log n) 3000회 으로 시간복잡도상 문제는 없습니다.  =>  sorted함수를 사용하여 정렬을 수행합니다.단, 모두 소문자로 변환하여 대소문자 구분을 없앱니다. 코드설계하기아래 과정을 n=0일때까지 반복합니다.단어를 입력받으면서 소문자로 변환한 것과 같이 리스.. 2025. 1. 22.
[알고리즘] 촌수계산 - 그래프 문제 링크촌수계산: https://www.acmicpc.net/problem/2644 문제탐색기본 원리 탐색두 사람의 촌수를 구한다는 것은, 그래프에서 두개 지점의 거리를 구하는 것과 같습니다.단, 친척관계가 없다면 (그래프가 이어져있지 않다면) -1을 출력해야 합니다. 시간복잡도와 알고리즘시간제한 : 1초약 1억번의 연산이 가능하다고 가정합니다.최대 사람 수 : 100  BFS혹은 DFS로 그래프를 탐색할때 시간복잡도는 O(N+M)이며  이 문제는 부모가 1명만 존재하므로  M은 N보다 클수 없는 트리구조를 따르고 있습니다. 그러므로 시간복잡도는 입력을 포함해 O(2N+M) = 300회 미만으로 충분합니다. => BFS,DFS모두 사용할 수 있지만, 두 지점사이 거리를 구하는 문제(최단거리) 이므로 B.. 2025. 1. 21.
[알고리즘] 연결 요소의 개수 문제 링크연결 요소의 개수 : 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.

티스토리툴바