파이썬80 [알고리즘 이론] 계수 정렬(Counting Sort) 1. 계수 정렬이란?계수 정렬(Counting Sort)은 비교 기반이 아닌 정렬 알고리즘으로, 정수나 정수로 표현할 수 있는 데이터를 정렬할 때 사용됩니다. 이 알고리즘은 각 항목이 몇 번 등장하는지 세어서 정렬하는 방식으로 작동합니다. 특히 정수의 범위가 작을 때 매우 효율적인 알고리즘입니다.2. 계수 정렬의 기본 원리계수 정렬의 기본 아이디어는 다음과 같습니다:입력 배열의 최댓값과 최솟값을 찾아 범위를 결정합니다.해당 범위만큼의 크기를 가진 카운트 배열을 생성합니다.입력 배열을 순회하며 각 요소의 출현 횟수를 카운트 배열에 기록합니다.카운트 배열을 누적합으로 변환합니다(선택 사항).누적합을 이용하여 각 요소의 정확한 위치를 계산하고 결과 배열에 배치합니다.3. 계수 정렬 알고리즘 단계별 설명계수 정.. 2025. 4. 23. [Leetcode] 802. Find Eventual Safe States 문제 요약알고리즘 분류: 백트레킹, 수학, 배열난이도: Medium문제내용:개의 노드로 구성된 방향 그래프가 있으며, 각 노드는 0부터 n - 1까지 레이블이 지정되어 있습니다.그래프는 0-인덱스 기반의 2D 정수 배열 graph로 표현되는데, graph[i]는 노드 i에 인접한 노드들의 정수 배열입니다.터미널 노드(Terminal Node): 나가는 간선이 없는 노드입니다.안전 노드(Safe Node): 해당 노드에서 시작하는 모든 가능한 경로가 터미널 노드나 다른 안전 노드로 이어지는 노드입니다.사이트 주소: 문제풀이 이 문제는 얼핏 보면 복잡해 보이지만, 그래프 이론의 위상 정렬(Topological Sort)을 응용하여 해결할 수 있습니다. 여기서 주요 인사이트는 문제를 역방향으로 생각하는 것입.. 2025. 4. 22. [BAEKJOON]25206 너의 평점은 문제 요약알고리즘 분류: 구현, 수학난이도: Silver5문제내용:전공평점은 (학점 × 과목평점)의 합을 학점의 총합으로 나눈 값P/F 과목 중 등급이 'P'인 과목은 계산에서 제외해야 함20줄에 걸쳐 과목명, 학점, 등급이 주어짐사이트: https://www.acmicpc.net/problem/25206문제풀이 이번 문제는 단순하게 구현과 소수 계산을 요구 하는 문제이다. 등급에 따른 과목평점을 정의 한 다음 과목평점이 P를 제외한 총학점과 총 과목 평점을 계산한 뒤 총 과목 평점 / 총 학점계산만 하면 끝이다. 자세한것은 아래 코드보면 된다.CodePython# 등급에 따른 과목평점 정의grades = { "A+" : 4.5, "A0": 4.0, "B+": 3.5, "B0": 3.. 2025. 4. 17. [Leetcode]554. Brick Wall 문제 요약알고리즘 분류: 배열, 해쉬난이도: Medium문제내용:. n개의 벽돌 행으로 이루어진 직사각형 벽돌 벽이 있습니다. 각 행의 벽돌들은 같은 높이(1단위)를 가지지만, 너비는 다를 수 있습니다. 모든 행의 총 너비는 동일합니다.벽에 대한 정보를 담고 있는 2D 배열 wall이 주어졌을 때, 이러한 수직선을 그린 후 가로지르는 벽돌의 최소 개수를 반환 하여라사이트 주소: https://leetcode.com/problems/brick-wall/description/문제풀이이 문제를 해결하기 위한 핵심 아이디어는 다음과 같습니다:벽돌을 가로지르지 않으려면, 선이 벽돌의 경계(두 벽돌 사이)를 통과해야 합니다.최소 개수의 벽돌을 가로지르려면, 최대한 많은 행에서 벽돌 경계를 통과해야 합니다.즉, 벽.. 2025. 4. 15. [Leetcode]984. String Without AAA or BBB 문제 요약알고리즘 분류: 그리디, 정렬난이도: Medium문제내용:.두 정수 a와 b가 주어질 때, 다음 조건을 만족하는 문자열 s를 반환하세요:s의 길이는 a + b이고, 정확히 a개의 'a' 문자와 정확히 b개의 'b' 문자를 포함합니다.부분 문자열 'aaa'는 s에 나타나지 않습니다.부분 문자열 'bbb'는 s에 나타나지 않습니다.사이트 주소:https://leetcode.com/problems/string-without-aaa-or-bbb/description/문제풀이 이번문제는 완전탐색아닌 그리디로 최적의 해로 시간복잡도가 최소화를 할 후 있다.그리디 관련 내용은 아래글로 참고 하면된다.https://jih3508.tistory.com/70 [알고리즘 이론] 그리디(Greedy)이론 그리디 알.. 2025. 4. 14. [Leetcode]1863. Sum of All Subset XOR Totals 문제 요약알고리즘 분류: 백트레킹, 수학, 배열난이도: Medium문제내용:수 배열 nums가 주어진다.XOR 총합(XOR total)은 배열의 모든 요소를 비트 단위 XOR 연산한 값이며, 배열이 비어 있는 경우에는 0으로 정의한다.[2, 5, 6]의 XOR 총합은 2 XOR 5 XOR 6 = 1 이다.정수 배열 nums가 주어질 때, nums의 모든 부분집합에 대한 XOR 총합의 합을 구하여 반환하여라사이트 주소: https://leetcode.com/problems/sum-of-all-subset-xor-totals/description/문제풀이 이번 문제는 백트레킹 문제이다. 백트레킹 관련 자세한 내용은 아래의 사이트에 참조하면된다.https://jih3508.tistory.com/84 [알고리.. 2025. 4. 9. 이전 1 2 3 4 5 ··· 14 다음
