시뮬레이션 (Simulation)

시뮬레이션 (Simulation) 1) 시뮬레이션이란?문제에서 주어진 조건과 규칙을 그대로 구현하여 상황을 재현해 나가는 방식의 알고리즘이다. 즉, 문제에서 말한 게임 규칙, 이동 방식, 회전 조건, 충돌 처리 등을 논리 흐름에 따라 직접 구현하는 것이 핵심이다 2) 시뮬레이션의 특징 항목 내용 핵심 포인트"문제를 읽은 그대로" 구현하는 능력자료구조 사용배열, 2차원 배열, 큐, 리스트 등수학적 개념거의 없음 또는 간단한 연산만 사용중요 능력조건 분기, 상태 추적, 좌표/인덱스 계산난이도쉬워 보이지만 디버깅과 구현이 매우 까다로움 3) 동작 원리 1. 상태 정의위치, 방향, 점수, 체력, 타이머 등 초기 상태 정의 2. 조건 처리문제에서 요구하는 행동 규칙을 조건문/반복문으로 구현..

• format_list_bulleted Algorithm/이론
• · 2025. 5. 22.

백트래킹

백트래킹 (Back Tracking) 1) 백트래킹란?백트래킹은 모든 경우의 수를 탐색하되, 조건을 만족하지 않는 경우 탐색을 중단하고 이전 단계로 되돌아가는 방식의 탐색 알고리즘이다. DFS 기반의 완전 탐색 기법 중 하나로, 불필요한 탐색을 줄여주는 가지치기(pruning) 기법이 포함된다. 2) 백트래킹 동작원리 1. 가능한 모든 경우를 시도한다 (DFS 기반 탐색). 2. 탐색 도중 조건에 맞지 않는 경우 더 이상 진행하지 않고 되돌아간다 (backtrack). 3. 조건을 만족하는 경우 정답 처리한다. 4. 다음 탐색을 위해 상태를 복구하고(undo), 새로운 경우의 수를 시도한다. // 백트래킹 구조void backtrack(int depth) { if (종료 조건) { ..

• format_list_bulleted Algorithm/이론
• · 2025. 5. 21.

순열 / 조합 / 부분집합

순열 / 조합 / 부분집합 1) 순열 ( Permutation )모든 순서의 경우를 구하는 것주어진 원소들을 순서를 고려해 나열 // 예: [1, 2, 3] → 가능한 순열:[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]// 총 경우의 수 : n! (팩토리얼) 예시 문제 https://devwarriorjungi.tistory.com/entry/%EB%B0%B1%EC%A4%80-15649-Java-N%EA%B3%BC-M-1 [백준 15649] Java - N과 M (1)https://www.acmicpc.net/problem/15649 N과 M (1) 1) 문제자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을..

• format_list_bulleted Algorithm/이론
• · 2025. 5. 2.

재귀함수 (Recursion)

재귀함수 1) 재귀함수 란?함수가 자기 자신을 호출하는 방식의 함수입니다.대표적으로, 팩토리얼 계산, 피보나치 수열, 하노이 탑, DFS, 백트래킹 등 모든 깊이 탐색 알고리즘의 기반이 됩니다. 2) 재귀함수의 동작원리재귀 함수는 내부적으로 '스택 구조'를 따릅니다.즉, 함수가 호출될 때마다 현재 함수는 잠깐 멈추고, 새로운 함수 호출이 먼저 끝날 때까지 기다립니다.맨 마지막 호출이 종료되면 차례로 다시 돌아옵니다. 3) DFS 활용분야활용 분야설명경로 찾기특정 노드까지의 경로 유무, 경로 목록 찾기미로 탐색출구가 있는지 확인하거나 모든 경로 탐색백트래킹 문제N-Queen, 순열/조합, 스도쿠 해결 등트리 탐색전위/중위/후위 순회 구현사이클 탐지그래프 내 순환 여부 확인위상 정렬DFS 기반 ..

• format_list_bulleted Algorithm/이론
• · 2025. 5. 2.

DFS 깊이 우선 탐색 (스택 방식)

DFS 1) DFS란?시작 노드에서 가능한 깊이까지 탐색한 뒤, 더 이상 갈 곳이 없으면 되돌아(backtrack) 하여 다음 경로를 탐색하는 방식입니다.한 방향으로 계속 깊게 파고들며, 재귀 또는 스택(Stack)으로 구현 가능하고, 경로 탐색, 조합 탐색, 미로 문제, 백트래킹 등에 유리합니다. 2) DFS 시간복잡도와 공간복잡도시간복잡도 : O(V + E)V = 정점(노드)의 개수E = 간선의 개수공간복잡도 : O(V) 또는 O(h) V = 정점(노드)의 개수h = 그래프의 최대 깊이 3) DFS 활용분야활용 분야설명경로 찾기특정 노드까지의 경로 유무, 경로 목록 찾기미로 탐색출구가 있는지 확인하거나 모든 경로 탐색백트래킹 문제N-Queen, 순열/조합, 스도쿠 해결 등트리 탐색전..

• format_list_bulleted Algorithm/이론
• · 2025. 5. 1.

DFS 깊이 우선 탐색 (재귀방식)

DFS 1) DFS란?시작 노드에서 가능한 깊이까지 탐색한 뒤, 더 이상 갈 곳이 없으면 되돌아(backtrack) 하여 다음 경로를 탐색하는 방식입니다.한 방향으로 계속 깊게 파고들며, 재귀 또는 스택(Stack)으로 구현 가능하고, 경로 탐색, 조합 탐색, 미로 문제, 백트래킹 등에 유리합니다. 2) DFS 시간복잡도와 공간복잡도시간복잡도 : O(V + E) V = 정점(노드)의 개수E = 간선의 개수공간복잡도 : O(V) 또는 O(h) V = 정점(노드)의 개수h = 그래프의 최대 깊이 3) DFS 활용분야활용 분야설명경로 찾기특정 노드까지의 경로 유무, 경로 목록 찾기미로 탐색출구가 있는지 확인하거나 모든 경로 탐색백트래킹 문제N-Queen, 순열/조합, 스도쿠 해결 등트리 탐색..

• format_list_bulleted Algorithm/이론
• · 2025. 5. 1.