728x90 반응형 자료구조21 [자료구조 & 알고리즘] 그리디 알고리즘(Greedy Algorithm) 그리디 알고리즘(Greedy Algorithm)1. 개요그리디 알고리즘(Greedy Algorithm)이란 현재 단계에서 가장 최적의 선택을 반복하여 문제를 해결하는 알고리즘입니다. 탐욕법이라고도 불리는 이 방식은 매 순간 최선의 선택이 결국 전체 문제의 최적해로 이어진다고 가정합니다.이 접근법이 성공적으로 작동하려면 문제에 대한 몇 가지 조건이 만족되어야 합니다. 그렇지 않으면 전역 최적해(Global Optimal Solution)를 보장하지 못할 수 있습니다.2. 그리디 알고리즘의 조건Greedy 선택 속성 (Greedy Choice Property)각 단계에서의 선택이 이후 단계에 영향을 주지 않고, 그 순간 최적의 선택을 하면 전체 최적해에 도달할 수 있는 속성을 의미합니다.최적 부분 구조 (O.. 2025. 2. 2. C - [백준 14888] 연산자 끼워넣기 (feat. 백트래킹 + DFS) 참조 포스트 2025.01.02 - [Computer Science/알고리즘 문제] - C - [백준 15649, 15650] N 과 M 시리즈 정복하기 (feat. 백트래킹, 순열) C - [백준 15649, 15650] N 과 M 시리즈 정복하기 (feat. 백트래킹, 순열)참조 포스트 2024.12.30 - [Computer Science/자료구조 & 알고리즘] - [자료구조 & 알고리즘] 백트래킹 (feat. DFS, 재귀) [자료구조 & 알고리즘] 백트래킹 (feat. DFS, 재귀)DFS2024.12.19 - [Computer Science/자료구조 &rnasterofmysea.tistory.com2025.01.02 - [Computer Science/알고리즘 문제] - C - [백준 9663.. 2025. 1. 7. C - [백준 1759] 암호 만들기 (feat. 백트래킹 + DFS) 참고 포스트2025.01.02 - [Computer Science/알고리즘 문제] - C - [백준 15649, 15650] N 과 M 시리즈 정복하기 (feat. 백트래킹, 순열)2025.01.02 - [Computer Science/알고리즘 문제] - C - [백준 9663] N-Queen (feat. 백트래킹, DFS) 예제 입력 1 4 6a t c i s w예제 출력 1 acisacitaciwacstacswactwaistaiswaitwastwcistciswcitwistwhttps://www.acmicpc.net/problem/1759BOJ 1759번: 암호 만들기문제의 핵심은 알파벳 C개 중 L개의 알파벳으로 구성된 암호를 생성하는 것입니다. 암호는 다음 조건을 만족해야 합니다:모음(a, e, .. 2025. 1. 5. C - [백준 1987] 알파벳 (feat. 백트래킹, DFS & 최장거리 탐색) 참고 포스트 2024.12.25 - [Computer Science/알고리즘 문제] - C - [백준 2178] 미로탐색 (feat. BFS & 최단거리 탐색) C - [백준 2178] 미로탐색 (feat. BFS & 최단거리 탐색)참고 포스트https://rnasterofmysea.tistory.com/47 C - [Backjoon 1260] DFS와 BFS[참고 포스트]https://rnasterofmysea.tistory.com/45 [자료구조 & 알고리즘] 그래프 + DFS그래프에 대해 기초부터 차근차근 학습해보겠습니rnasterofmysea.tistory.com2024.12.30 - [Computer Science/자료구조 & 알고리즘] - [자료구조 & 알고리즘] 백트래킹 (feat. DFS,.. 2025. 1. 5. C - [백준 9663] N-Queen (feat. 백트래킹, DFS) https://www.acmicpc.net/problem/9663 백준 9663번 - N-Queen 문제N-Queen 문제는 N×N 체스판 위에 N개의 퀸을 놓는 방법의 수를 찾는 문제입니다. 퀸은 같은 행, 열, 대각선 상에 위치한 다른 퀸을 공격할 수 있으므로, 서로 공격하지 않도록 배치해야 합니다. 입력N(1 ≤ N ≤ 15): 체스판의 크기 및 퀸의 개수출력조건을 만족하는 퀸 배치의 경우의 수 예제 입력 18 예제 출력 192 Checkpoint 1.각 행의 퀸은 1개씩 밖에 놓을 수 없기 때문에 첫 행에 퀸을 하나 배치하고 다음 행에 놓을 수 있는 공간에 퀸을 배치하고 그 다음 행에 놓일 수 있는 공간에 퀸을 배치하고 N개 행까지 전부 배치가 된다면 그 경우의 수는 성공이기 때문에 카운트를 하면.. 2025. 1. 4. C - [백준 15649, 15650] N 과 M 시리즈 정복하기 (feat. 백트래킹, 순열) 참조 포스트 2024.12.30 - [Computer Science/자료구조 & 알고리즘] - [자료구조 & 알고리즘] 백트래킹 (feat. DFS, 재귀) [자료구조 & 알고리즘] 백트래킹 (feat. DFS, 재귀)DFS2024.12.19 - [Computer Science/자료구조 & 알고리즘] - [자료구조 & 알고리즘] 그래프 + DFS [자료구조 & 알고리즘] 그래프 + DFS그래프에 대해 기초부터 차근차근 학습해보겠습니다. 그래프는 DFS와 BFS를rnasterofmysea.tistory.com 백트래킹의 기본 문제는 N과 M 문제는 (1)~(12)등 여러가지 문제가 존재하는데,BOJ_15649, BOJ_15650 두 문제만 재대로 이해해도 나머지 문제를 해결하는 데에 전혀 어려움이 없었.. 2025. 1. 3. 이전 1 2 3 4 다음 728x90 반응형
