Study28 [알고리즘] 병든 나이트 문제 링크 병든 나이트 : 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://school.programmers.co.kr/learn/courses/30/lessons/161990?language=python3 문제탐색기본 원리 탐색좌표를 기준으로 파일이 존재하고 그 파일을 최소한의 드래그로 전부 선택하는 문제입니다.다만 조건이 비교적 쉬운편입니다.무조건 정수 좌표에서 시작해서 끝나는 드래그드래그 이동거리 기준이 x축이동거리 + y축이동거리단, 파일의 크기가 있으므로 그점을 유의하여 문제를 잘 읽고 풀어야합니다. 시간복잡도와 알고리즘결국 파일이있는 x좌표의 최소값 과 y좌표의 최소값, x좌표의 최대값과 y좌표의 최대값 을 구하면 되는것으로 보입니다. 모든 경우를 직접구현하지 않는한 시간복잡도에는 큰 영향을 받지 않을것으로 보입니다. 코드설계.. 2025. 4. 2. [알고리즘] 결혼식 문제 링크 결혼식 : 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. [알고리즘] 1로 만들기 - DP 문제 링크1로 만들기 : https://www.acmicpc.net/problem/1463 문제탐색기본 원리 탐색정수 N이 주어졌을때 [3으로 나누기], [2로 나누기], [1을 빼기] 세가지중 하나를 수행하는것을 반복하여 최소한의 연산으로 1을 만들어야 하는 문제입니다. 얼핏보면 우선순위를 두어 그리디를 적용할수 있을것 처럼 보이지만 불가 합니다. (ex 10) 시간복잡도와 알고리즘시간제한 : 0.15초약 1500만 번의 연산, 매우 까다로운 시간제한을 가지고 있습니다.N 최대값 : 10^6 = 1,000,000 해당 문제는 규칙을 찾기 힘들고 실제로 동작을 시켜서 경우의 수를 찾아야합니다.하지만 완전탐색을 적용하기엔 N의수가 매우크며, 시간제한이 까다롭습니다. 그러므로 동적 계획법 알고리즘을 통해 접.. 2025. 1. 17. 이전 1 2 3 4 다음