1일 1코테6 [알고리즘] 나무 조각 - 구현 문제 링크 나무 조각 : 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. [알고리즘] 생일 - 정렬 문제링크생일 : https://www.acmicpc.net/problem/5635 문제탐색기본 원리 탐색생년월일이 주어진 학생들의 나이 중 최소값과 최대값을 구하는 문제입니다.이 문제를 해결하기 위해 다음과 같은 조건에 따라 정렬하거나, 데이터를 순회하며 최소/최대 값을 갱신해야 합니다:출생 연도를 기준으로 비교합니다.출생 연도가 같다면 출생 월을 기준으로 비교합니다.출생 월이 같다면 출생 일을 기준으로 비교합니다. 시간복잡도와 알고리즘시간제한 : 1초=> 약 1억번의 연산을 기준으로 합니다. 회원수 : 최대 100명 => 이 경우, 시간 복잡도가 O(n²) 인 알고리즘이라 하더라도 최대 10,000번의 연산만 필요합니다.따라서 이 문제는 시간 복잡도가 크게 영향을 미치지 않습니다. => 따라서 구현을 .. 2025. 1. 9. [알고리즘] 단어 정렬 - 정렬 문제 링크 단어 정렬 : https://www.acmicpc.net/problem/1181 문제탐색기본 원리 탐색주어진 문제는 N개의 알파벳을 특정 조건에 따라 정렬하는 것입니다.조건은 다음과 같습니다:길이가 짧은 순서로 정렬길이가 같다면 사전순으로 정렬또한, 중복된 단어는 하나만 남기고 제거해야 합니다.정렬 기준이 길이와 사전순 두 가지로 명확히 나뉘므로,각 단어를 [길이, 단어] 형태로 묶은 뒤 Python의 sorted 함수 기본값을 이용하면 해결할 수 있습니다.단, 중복 제거를 위한 추가 작업이 필요하므로 이를 고려해 풀이를 설계해야 합니다. 시간복잡도와 알고리즘 시간 제한: 2초Python에서 약 2억 번의 연산이 가능하다고 가정합니다.단어 수: 최대 20,000개시간 복잡도가 O(n²)인 .. 2025. 1. 8. [알고리즘] 나이순 정렬 - 정렬 문제 링크나이순 정렬 : https://www.acmicpc.net/problem/10814 문제탐색기본 원리 탐색이 문제는 정수를 기준으로 오름차순 정렬을 수행하는 문제입니다.정렬 시 아래 두 가지 조건을 충족해야 합니다:같은 나이일 경우 입력받은 순서를 유지해야 합니다. 나이와 이름이 세트로 엮여 있는 구조를 처리해야 합니다. 시간복잡도와 알고리즘시간 제한: 3초3초=> 약 3억 번의 연산을 기준으로 합니다.회원 수 : 최대 100,000이 경우 시간 복잡도가 O(n²) 인 알고리즘은 약 100억 회 이상의 연산이 필요하므로 불가능합니다. 파이썬의 sorted 함수는 최악의 경우에도 O(n log n) 복잡도를 가지므로 약 500,000회 가 예상됩니다.=> python의 sorted함수를 사용하.. 2025. 1. 8. [알고리즘] 일곱 난쟁이 - 정렬 문제탐색 기본 원리 탐색 총합은 무조건 100을 초과합니다.따라서, 총합에서 100을 뺀 값을 계산합니다.이 값은 난쟁이가 아닌 두 명의 키의 합이 됩니다.즉, 난쟁이들 중 두 명의 키의 합이 (총합 - 100)과 같은 경우를 찾아야 합니다. 시간복잡도와 알고리즘 시간 복잡도를 최소화하기 위해 (총합 - 100)보다 큰 수는 제외합니다.남은 수를 오름차순 정렬합니다.처음부터 순서대로 이전 숫자와 더하면서 (총합 - 100)을 초과하는지 확인합니다.즉, x번째 숫자 + (x-1)번째 숫자의 합을 계산합니다.(총합 - 100)보다 커지면, 해당 숫자 이전 값들로 조합을 시도합니다.만약 찾지 못하면, 다음 숫자로 넘어가 반복합니다. => 생각해보니 입력값의 길이가 9로 고정되어 있고, 완전탐색으로도 숫자 .. 2025. 1. 6. 이전 1 다음