본문 바로가기

Develop52

그리디 알고리즘과 배낭 문제 1. 그리디 알고리즘(Greedy Algorithm)이란?그리디(Greedy) 알고리즘은 '탐욕법'이라고도 불리며, 매 순간 가장 좋아 보이는 것을 선택하여 미래의 선택에 영향을 주지 않고 현재의 최적해를 찾는 방식입니다.장점: 구현이 간단하고 직관적이며, 특정 문제에서는 매우 빠르게 최적해를 찾을 수 있습니다.단점: 현재의 최적 선택이 전체의 최적해를 보장하지는 않습니다. 따라서 그리디 알고리즘을 사용하기 위해서는 '현재의 최적 선택이 미래에도 영향을 미치지 않고 전체의 최적해를 보장하는가?'를 반드시 검증해야 합니다.그리디 알고리즘 예제: 거스름돈 문제그리디 알고리즘이 최적해를 보장하는 대표적인 예는 '거스름돈 문제'입니다.문제: 870원을 거슬러 줘야 할 때, 500원, 100원, 50원, 10원짜.. 2025. 11. 6.

[BOJ] 9095번 1, 2, 3 더하기 - 분석 및 Java 풀이 https://www.acmicpc.net/problem/9095백준 9095번: 1, 2, 3 더하기문제 번호문제 이름난이도 (Silver 3)분류90951, 2, 3 더하기⭐⭐⭐다이나믹 프로그래밍 (DP)문제 분석: 목표와 조건주어진 양의 정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 문제입니다. 여기서 순서가 다른 합은 서로 다른 방법으로 간주합니다.입력: 테스트 케이스의 개수 T와 각 테스트 케이스에 대한 정수 n (1 n )출력: 각 n에 대해, 1, 2, 3의 합으로 나타내는 방법의 수.예시: n=44를 나타내는 방법은 총 7가지입니다.1+1+1+11+1+21+2+12+1+12+21+33+1문제 풀이의 핵심 분석: 점화식 찾기 (DP)이 문제는 작은 문제의 해답을 이용하여 큰 .. 2025. 10. 17.

[BOJ] 9251번: LCS / Java 풀이 백준 9251번: LCShttps://www.acmicpc.net/problem/9251부분 수열(subsequence) 은 원래의 수열에서 일부 원소를 빼서 만든 새로운 수열- 순서는 그대로 유지해야 한다.- 원소들을 건너뛰어도 상관 없다. (비연속성)ex) ABCDE- 가능) ACE, BD, ABCDE, C, ...- 불가능) ECA, BA, ... 부분 문자열(substring) 은 반드시 연속되어야 한다. LCS(Longest Common Subsequence), 최장 공통 부분 수열, 순서는 같지만 연속하지 않아도 되는 공통된 글자들의 가장 긴 묶음주어진 여러 개의 수열(문자열) 모두에 포함되는 부분 수열 중에서 가장 긴 것을 찾는 문제 동적 계획법(Dynamic Programming, DP.. 2025. 9. 26.

이진 트리 트리(Tree) 는 방향이 존재하는 그래프의 일종으로 부모 정점 밑에 여러 자식 정점이 연결되고, 자식 정점 각각에 다시 자식 정점이 연결되는 재귀적 형태의 자료구조입니다. 그 중에서 각 정점이 최대 2개의 자식 정점을 가지는 트리를 이진 트리(Binary Tree) 라고 합니다.종류정점이 채워져 있는 형태에 따라서 대표적으로 포화 이진 트리, 완전 이진 트리, 편향 이진 트리가 존재합니다.포화 이진 트리마지막 레벨까지 모든 정점이 채워져 있는 경우, 포화 이진 트리라고 부릅니다. 1 --- level 1 / \\\\ 2 3 --- level 2 / \\\\ / \\\\ 4 5 6 7 .. 2025. 8. 11.

퀵 정렬 (Quick Sort)의 기본 개념과 동작 원리 1. 퀵 정렬이란? 왜 필요한가?퀵 정렬(Quick Sort) 은 이름에서 알 수 있듯 매우 빠른 정렬 속도를 자랑하는 알고리즘입니다. '분할 정복(Divide and Conquer)'이라는 전략을 사용하여 전체 리스트를 더 작은 단위로 나누어 정렬합니다.왜 필요할까요? 수많은 정렬 알고리즘 중 퀵 정렬이 널리 사랑받는 이유는 평균적인 상황에서 최고의 성능을 보이기 때문입니다. 특히, 정렬해야 할 데이터의 양이 많을 때 그 진가가 드러납니다. 대부분의 프로그래밍 언어에서 표준 정렬 라이브러리의 일부로 채택될 만큼 효율성과 범용성이 뛰어납니다.java.util.Arrays.sort() (primitive types): Java의 Arrays.sort() 메서드는 듀얼 피벗 퀵 정렬(Dual-Pivot Qu.. 2025. 7. 23.

트라이(Trie) 자료구조 트라이(Trie) 는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료 구조입니다. 트라이는 문자열을 탐색할 때 단순히 비교하는 것에 비해서 효율적으로 찾을 수 있지만, 각 정점이 자식에 대한 링크를 모두 가지고 있기 때문에 저장 공간을 더욱 많이 사용한다는 특징이 있습니다. 주로, 검색어 자동완성이나 사전 찾기 기능을 구현할 때 트라이 자료구조를 고려할 수 있습니다.출처 : 위키백과구현 방법트라이 자료구조에서 루트는 항상 비어있으며, 각 간선은 추가될 문자를 키로 가지고 있습니다. 또한, 각 정점은 이전 정점의 값과 간선의 키를 더한 결과를 값으로 가집니다. 트라이를 구현할 때는 이러한 구조를 염두에 두면서 해시 테이블과 연결 리스트를 이용하여 구현할 수 있습니다.class Trie.. 2025. 7. 18.

선택 정렬 (Selection Sort) 배열의 모든 요소를 하나씩 확인하면서, 현재 위치에 와야 할 가장 작은(혹은 가장 큰) 요소를 찾아 그 위치에 배치하는 방식입니다.1. 동작 방식선택 정렬은 다음과 같은 단계를 반복하여 정렬을 수행합니다.최소값(또는 최대값) 찾기: 배열의 정렬되지 않은 부분에서 가장 작은(또는 가장 큰) 요소를 찾습니다.위치 교환: 찾아낸 최소값(또는 최대값)을 정렬되지 않은 부분의 첫 번째 요소와 교환합니다.반복: 위 과정을 정렬되지 않은 다음 부분을 대상으로 반복합니다. 배열 전체가 정렬될 때까지 이 과정을 계속합니다.2. 예제선택 정렬 이용 오름차순으로 정렬하는 과정 설명 초기 배열: [64, 25, 12, 22, 11]1단계: 첫 번째 요소(인덱스 0) 위치 결정정렬되지 않은 부분: [64, 25, 12, 22,.. 2025. 7. 9.

[BOJ] 15657번: N과 M (8) https://www.acmicpc.net/problem/15657* 백트래킹: "경로를 탐색하다가 해가 될 가능성이 없으면 즉시 되돌아가 다른 경로를 탐색하는" 알고리즘문제 정리N개의 자연수 중에서 M개를 고른 수열: N개의 주어진 숫자들 중에서 M개를 선택하여 수열을 만듭니다.같은 수를 여러 번 골라도 된다: 중복 선택이 허용됩니다.고른 수열은 비내림차순이어야 한다: A1≤A2≤⋯≤AM 와 같이, 뒤에 오는 숫자는 앞에 오는 숫자보다 작으면 안 됩니다.수열은 사전 순으로 증가하는 순서로 출력: 최종 결과도 사전 순으로 정렬되어야 합니다. (이 조건은 입력으로 주어진 N개의 수를 미리 정렬하고, DFS 탐색 시 올바른 순서로 탐색하면 자동으로 만족됩니다.)백트래킹의 적용 원리백트래킹은 "경로를 탐.. 2025. 6. 11.

연결 리스트 연결 리스트(Linked List) 는 리스트 내의 요소(노드)들을 포인터로 연결하여 관리하는 선형 자료구조입니다. 각 노드는 데이터와 다음 요소에 대한 포인터를 가지고 있는데요. 이때, 첫 번째 노드를 HEAD, 마지막 노드를 TAIL 이라고 합니다. 연결 리스트는 메모리가 허용하는 한 요소를 계속 삽입할 수 있으며, 시각 복잡도는 탐색에는 O(n), 노드 삽입과 삭제는 O(1)라는 특징을 가지고 있습니다. 해당 아이디어로 파생된 자료구조는 단일 연결 리스트(Singly Linked List), 이중 연결 리스트(Doubly Linked List, Circular Linked List)가 존재합니다.배열은 순차적인 데이터가 들어가기 때문에 메모리 영역을 연속적으로 사용합니다. 반면, 연결 리스트는 메모.. 2025. 5. 30.

이전 1 2 3 4 ··· 6 다음

728x90

티스토리툴바