알고리즘/문제 유형

백트래킹현재 상태에서 가능한 모든 선택지를 따라 들어가며 탐색하는 알고리즘  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를 설명할 때는 보통 ‘번호가 낮은 인접 노드부터 방문..