알고리즘/문제 유형

A* 알고리즘 (최단 거리 알고리즘) : 그래프 탐색과 최단 경로 찾기를 위한 알고리즘으로, 다익스트라 알고리즘과 휴리스틱(Heuristic) 탐색을 결합한 방식 각 경로의 비용을 평가하는 F 값을 기반으로 탐색을 수행열린 목록: 내가 앞으로 갈 수 있는 노드들닫힌 목록: 내가 이미 갔던 노드들노드: 각 좌표부모 노드: 이동할 때 현재 노드의 이전 노드F: G + HG: 출발지에서 얼마나 떨어져 있나 (상, 하, 좌, 우 = 10, 대각선 = 14)H: 목적지까지 얼마나 이동해야 하나(대각선 이동과 장애물은 고려하지 않는다.) 시작점을 열린 목록에 넣는다. 열린 목록이 비어있지 않으면 반복 열린 목록에서 F값이 가장 적은 하나를 가져온다. (가져온 노드는 목록에서 삭제) 가..

백트래킹현재 상태에서 가능한 모든 선택지를 따라 들어가며 탐색하는 알고리즘  DFS와 헷갈릴 수도 있지만, 백트래킹 = DFS가 아니라 백트래킹 방법 중의 하나가 DFS인 것이다. DFS는 깊이 우선 탐색으로 모든 경우의 수를 다 탐색하지만,백트래킹은 조건에 맞지 않는다면 그 부분은 탐색하지 않고 탐색을 중지한 다음 그 이전으로 돌아가서 다른 경우를 탐색한다.연습 문제[백준`15649] N과 M (1)문제자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)  출력한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되..

알고리즘 언어를 파이썬에서 자바로 바꾸기로 결정하면서입출력 받는 방법을 계속 까먹어서 정리 Scanner보다 BufferedReader가 속도가 더 빠르기 때문에속도가 중요한 코딩테스트에서는 BufferedReader 사용하기!  입력1. 한 줄에 하나씩 정수 입력 받기// 예제 입력1 2import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new..

순열서로 다른 n개의 원소에서 r개를 중복 없이 선택하여 순서대로 나열선택하는 순서가 다르면 서로 다른 것 (즉, AB와 BA가 다르다)cards = ['A', 'B', 'C', 'D']k = 3visited = [False] * len(cards)answer = []def dfs(count, arr): if count == k: answer.append(arr[:]) return for i, card in enumerate(cards): if not visited[i]: arr.append(card) visited[i] = True dfs(count + 1, arr) arr.p..

그리디 알고리즘 (탐욕 알고리즘) : 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘 : 관찰을 통해 탐색 범위를 줄이는 알고리즘 그리디 알고리즘이 최적의 답을 보장해주는 문제 1. 최적 부분 구조 - 부분 문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구할 수 있다는 것 2. 탐욕적 선택 속성 - 각 단계에서의 탐욕스러운 선택이 최종 답을 구하기 위한 최적의 선택

동적 프로그래밍 (Dynamic Programming) : 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘 목적 수행 시간을 단축하고자 만든 알고리즘 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘 메모리를 사용해서 중복 연산을 줄이고, 중복 연산을 줄여서 수행 속도 개선 메모리 사용: 배열 또는 자료구조 생성 중복 연산 줄임 : 한 번 연산한 결과를 배열에 저장 푸는 과정 테이블 정의하기 점화식 찾기 초기값 정하기 구현 방법 1. Memoization 중복되는 계산은 한 번만 계산 후 메모 하향식 접근 (Top-down), 재귀 기반 코드 한 번 계산 후 저장해놓고, 저장해둔 결과를 꺼내서 사용하며 구현 2. Tabulati..

대표 문제 유형 경로 탐색 (최단 거리, 시간) 최단 거리 : BFS 경로의 가짓수(경우의 수) : DFS 네트워크 (연결) 조합 (모든 조합 만들기) 구현 방법 DFS : Stack, 재귀함수 BFS : Queue, LinkedList 무방향 그래프 # 각 노드가 연결된 정보를 표현 (2차원 리스트) # 보통 문제에서 1부터 시작하기 때문에 인덱스 0은 비워둠 graph = [ [], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7] ] # 각 노드가 방문된 정보를 표현 (1차원 리스트) visited = [False] * 9 DFS (Depth First Search) DFS를 설명할 때는 보통 ‘번호가 낮은 인접 노드부터 방문..