본문 바로가기

알고리즘213

[알고리즘 이론] 분할 정복(Divide and Conquer) 분할 정복(Divide and Conquer) 알고리즘 완벽 가이드1. 분할 정복이란?분할 정복(Divide and Conquer)은 복잡한 문제를 더 작고 관리하기 쉬운 하위 문제들로 나누어 해결하는 알고리즘 패러다임입니다. 이 방법론은 컴퓨터 과학의 여러 분야에서 광범위하게 사용되며, 많은 효율적인 알고리즘의 기초가 됩니다.분할 정복은 다음 세 가지 주요 단계로 구성됩니다:분할(Divide): 원래 문제를 여러 개의 작은 하위 문제로 나눕니다.정복(Conquer): 하위 문제들을 재귀적으로 해결합니다. 하위 문제가 충분히 작으면 직접 해결합니다.결합(Combine): 하위 문제들의 해결책을 결합하여 원래 문제의 해결책을 만듭니다.2. 분할 정복의 장점분할 정복 접근법은 다음과 같은 여러 가지 장점을 .. 2025. 5. 14.
[BAEKJOON]7785 회사에 있는 사람 문제 요약알고리즘 분류: 집합난이도: Silver5문제내용:사람 이름하고 "enter"나 "leave"가 주어진다. "enter"인 경우는 출근, "leave"인 경우는 퇴근이다. 출근 한 사람 역순으로 출력해라사이트: https://www.acmicpc.net/problem/7785 문제풀이 이번 문제는 간단한 집합문제이다. 각 언어마다 Set이라는 자료 구조만 활용 잘하면 된다. Set에 대한 기본 설명 하면 아래와 같다. O(1) 시간에 추가/삭제 가능자동으로 중복 제거빠른 검색 가능 구현은 아래와 같이 하면 된다.enter 기록은 Set에 추가leave 기록은 Set에서 제거마지막에 Set의 내용을 역순 정렬하여 출력마무리 위와 같이 구현 하면 시간 복잡도는 정렬 때문에 O(NlogN) 만큼 나.. 2025. 5. 12.
[Leetcode]1306. Jump Game III 문제 요약알고리즘 분류: Tree, DFS, BFS난이도: Medium문제내용:배열 arr이 주어지고, 여러분은 처음에 start 인덱스에 위치해 있습니다.인덱스 i에 있을 때, 여러분은 i + arr[i] 또는 i - arr[i]로 점프할 수 있습니다.값이 0인 인덱스에 도달할 수 있는지 true, false로 반환 하면 됩니다.사이트 주소: https://leetcode.com/problems/jump-game-iii/description/문제풀이 이번 문제는 방향성 그래프는 아니지만 잘보면 간단하게 그래프 탐색으로 풀수 있는 문제이다. 그레프 탐색은 대표적으로 깊이 우선 탐색(DFS), 넓이 우선 탐색(BFS)이 있다. 그래프 탐색에 대한 내용은 아래 글에서 확인 해보면 된다.깊이 우선 탐색(DFS.. 2025. 5. 7.
[Leetcode] 3016. Minimum Number of Pushes to Type Word II 문제 요약알고리즘 분류: 그리디, , 정렬, Counting 난이도: Medium문제내용:각 키(2~9)는 서로 다른 알파벳 집합에 매핑될 수 있습니다.키는 어떤 개수의 문자로든 재매핑할 수 있습니다.각 알파벳은 정확히 하나의 키에만 매핑되어야 합니다.키에 매핑된 n번째 문자를 입력하려면 키를 n번 눌러야 합니다.예: 키 '2'에 ['a','b','c']가 매핑되면, 'a'는 1번, 'b'는 2번, 'c'는 3번 눌러야 합니다.주어진 단어 word를 입력하기 위한 최소 키 누름 횟수를 반환하세요.사이트 주소: https://leetcode.com/problems/minimum-number-of-pushes-to-type-word-ii/description/문제풀이이번 문제에서는 완전탐색으로 풀수 있지만.. 2025. 5. 6.
[BAEKJOON]5639 이진 검색 트리 문제 요약알고리즘 분류: 트리, 트리 탐색난이도: Gold4문제내용:이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.위 트리에서 전위 순회 한것을 후위 순회한 결과를 출력하여라사이트: https://www.acmicpc.net/problem/5639문제풀이 이번에는 문제 유형은 트리 탐색에 관련 문제이다. 트리에 관한 자세한 내용은 여기에서 보면된다.문제 접근방법이 문제의 핵심은 전위 순회 결과만 가지고 후위 순회 결과를 어떻게 구하느냐는 것입니다. 아래 와 같이 처음부터 집어 넣는 식으로 만들면 시간 .. 2025. 4. 29.
[BAEKJOON]11005 진법 변환 2 문제 요약알고리즘 분류: 구현, 수자난이도: Bronze1문제내용:10진수 N을 B진법으로 변환 하여라사이트: https://www.acmicpc.net/problem/11005문제풀이 이번 문제는 각 언어마다 진법을 변환 하는 방법만 알면 문제 푸는데 지장이 없을 것이다. CodePython 파이썬 다른 언어와 다르게 진법을 바꿔주는 함수가 없어서 직접 구현 해야 한다.number = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"N, B = map(int, input().split())s = ""while N: s += number[N % B] N //= Bprint(s[::-1])JavaInteger.toString(N, B): 10진수 N을 B진법으로 변환impor.. 2025. 4. 29.

티스토리툴바