728x90 반응형 algorithm6 [파이썬 알고리즘] 정렬 알고리즘 (6) - 계수 정렬 지금까지 버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬의 개념을 하나하나 빠짐없이 공부한 뒤에 전부 파이썬으로 구현해보는 시간을 가졌습니다. 앞서 배운 정렬 중에서 가장 빠른 정렬 알고리즘의 시간 복잡도는 O(NlogN)이였습니다. 하지만 만약 이것보다 더욱 빠르게 정렬을 해야 한다면 어떻게 할까요?1. 계수 정렬계수 정렬은 정수 데이터가 작은 범위 내에 존재할 때 사용할 수 있는 특화된 정렬 알고리즘입니다.기본 아이디어는 다음과 같습니다.각 숫자가 몇 번 나왔는지 세어서 정렬 결과를 만드는 방식 즉, 비교 기반 정렬이 아닌, 빈도 기반 정렬입니다. 특징은 아래와 같습니다. 특징설명시간 복잡도O(N + K) (K: 데이터의 최댓값)공간 복잡도O(K)안정성불안정 정렬 (원소의 순서가 보장되지 .. 2025. 7. 20. [파이썬 알고리즘] 정렬 알고리즘 (3) - 삽입 정렬 이번 시간에는 정렬 알고리즘 시리즈의 세 번째로 삽입 정렬(Insertion Sort)에 대해 알아보겠습니다. 삽입 정렬은 우리가 카드 게임에서 손에 카드를 한 장씩 정리해 나가는 방식과 매우 유사한 정렬 알고리즘입니다.1. 삽입 정렬삽입 정렬은 위 문제를 풀 때 각 숫자를 적절한 위치에 삽입하는 방법으로 문제를 해결합니다. 다른 정렬 방식들은 무조건 위치를 바꾸는 방식이었다면 삽입 정렬은 ‘필요할 때만’ 위치를 바꾸게 됩니다.즉, 각 숫자를 적절한 위치에 삽입하면 어떨까? 동작 방식삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘입니다.즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는.. 2025. 7. 16. [BFS] 백준 17836. 공주님을 구해라! 며칠간 코딩 테스트와 면접 준비로 문제를 풀지 못했지만, 이런 시기일수록 천천히, 꼼꼼하게, 꾸준하게 나아가야 한다고 다시 다짐했습니다. 오늘은 BFS 응용 문제인 백준 17836번 - 공주님을 구해라!를 풀어봤습니다. 제한 시간, 벽 통과 조건, 특수 아이템(그람)을 고려해야 해서 단순한 BFS보다 조금 더 꼼꼼한 구현이 필요했습니다.1. 문제: 백준 17836. 공주님을 구해라!단계: 🥇 골드 5단계주제:그래프 이론그래프 탐색너비 우선 탐색격자 그래프출처: https://www.acmicpc.net/problem/17836문제용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용.. 2025. 6. 27. [백트래킹] LeetCode 77. Combinations 이전 순열 문제에 이어서 오늘은 조합 문제를 풀어보았습니다. 순열과 헷갈리기 쉬운 개념이지만, 핵심은 “순서를 고려하지 않는다”는 점! 그럼 바로 시작해보겠습니다. Let’s GOGO 🚀1. 문제: LeetCode 77. Combinations단계: Medium주제: Backtracking출처: https://leetcode.com/problems/combinations/description/문제Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].You may return the answer in any order. Example 1:Input: n = 4, k = 2 O.. 2025. 6. 21. [BFS, DFS] 백준 1743. 음식물 피하기 오늘은 BFS와 DFS의 전형적인 활용 문제를 소개합니다. 문제 자체는 심플하지만, 실제로는 섬의 개수 구하기 문제처럼 연결된 영역을 탐색해야 하므로 플러드 필(Flood Fill) 알고리즘을 연습하기에 매우 좋은 예제입니다.1. 문제: 백준 1743. 음식물 피하기단계: 🥈 실버 1단계주제:그래프 이론그래프 탐색너비 우선 탐색깊이 우선 탐색격자 그래프플러드 필출처: https://www.acmicpc.net/problem/1743문제코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다.이 문제를 출제한 선생님은 개인적으로 이러한 .. 2025. 6. 13. [DP] 백준 2839. 설탕 배달 오늘은 예전에 그리디 알고리즘으로 풀어봤던 문제를 다이내믹 프로그래밍(DP) 관점에서 다시 풀어보았습니다.한 문제를 여러 방식으로 접근해 보는 경험은 알고리즘 실력을 한 단계 업그레이드하는 좋은 방법이죠.1. 문제: 백준 2839. 설탕 배달단계: 🥈 실버 4단계주제:수학다이내믹 프로그래밍그리디 알고리즘출처:https://www.acmicpc.net/problem/2839문제상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬.. 2025. 4. 17. 이전 1 다음 728x90 반응형
