반응형 코딩테스트/개념정리4 동적 계획법(DP:Dynamic programming) 개념 및 구현 동적 계획법은 복잡한 문제를 작은 하위 문제로 나누어 해결하고, 그 결과를 저장하여 동일한 하위 문제가 다시 나타날 때 재활용함으로써 연산을 줄이는 알고리즘 설계 기법이다. DP는 다음과 같은 두 가지 중요한 특징이 있다. 1. 최적 부분 구조 : 문제의 최적 해결 방법이 하위 문제들의 최적 해결 방법으로 구성될 수 있다. 2. 중복되는 부분 문제 : 동일한 작은 문제들이 반복적으로 계산된다. 또한 DP에는 메모이제이션(탑다운), 타뷸레이션(바텀업) 2가지 방법이 있다.비효율적인 재귀를 이용한 비보나치 수열 구현public class FibonacciRecursive { public static void main(String[] args) { int n = 10; // 예를 들어 1.. 2024. 5. 27. 시간/공간복잡도 개념(코테 대비 팁) 1. 시간/공간 복잡도를 알아야 하는 이유 2. 빅오(Big O)표기법 : 알고리즘의 성능을 분석할 때 사용하는 수학적 표현 방식이다. 이는 특히 알고리즘이 처리해야할 데이터의 양이 증가할 때, 그 알고리즘이 얼마나 빠르게 실행되는지 나타낸다. 여기서 중요한 것은 알고리즘의 정확한 실행 시간을 계산하는 것이 아니라, 데이터 양의 증가에 따른 성능의 변화 추세를 이해하는 것이다. - 시간 복잡도 : 입력된 N의 크기에 따라 실행되는 조작의 수 1. O(1) - 상수 시간 : 입력 데이터의 크기에 관계없이 알고리즘의 실행 시간이 일정하다. 예) 배열에서 인덱스를 사용하는 경우2. O(n) - 선형 시간 : 알고리즘의 실행 시간이 입력 데이터의 크기에 비례하여 증가한다. 예) 배열의 검색, 배열의 모든 요.. 2024. 5. 13. DFS와 BFS 개념 및 구현 DFS(Depth-First Search) : 그래프를 탐색할 때, 현재 위치에 인접한 노드를 우선적으로 선택하여 깊이가 증가하는 방향으로 탐색하는 알고리즘 구현 : 재귀를 이용 (그래프 표현 방법 : 인접 행렬)static int[][] graph; static boolean[] visited;static void dfs(int node){ visited[node] = true; System.out.print(node + " "); for (int i = 0; i BFS(Breadth First Search) : 시작 정점부터 옆으로 좌우로 탐색하는 너비 우선 탐색 방법 구현 : 큐를 이용 (그래프 표현 방법 : 인접 행렬)static int[][] graph;static b.. 2024. 5. 13. [자료구조] 스택(stack) ,큐(Queue) / [알고리즘] 이진 탐색(binary search) 1 . 스택(stack)은 모든 원소들의 삽입과 삭제가 리스트의 한쪽 끝에서만 수행되는 제한 조건을 가지는 선형 자료구조이다.삽입과 삭제가 일어나는 리스트의 끝을 top이라고 하고, 다른 한쪽 끝을 bottom이라고 한다. 즉, 후입선출(Last in First Out - LIFO)이라고 한다.기록을 쌓아가며 직전의 상태를 복원해야하는 상황에 유용하다. ex) 웹 브라우저 뒤로 가기, 프로그램 실행 취소, 함수 호출 등등 기억하기 쉬운 예시 : 펜케이크 펜케이크를 다 굽고 그릇 위에 옮긴다. 접시에 한 개씩 쌓아간다. 이때 손님이 펜케이크를 달라고 한다. 그럼 어떤 펜케이크를 줄 것인가? 사회통념상 쌓던 펜케이크 중에서 맨 위에 있는 펜케이크를 줄 것이다. 펜케이크 굽는 것을 멈추고 그릇에 쌓여있던 .. 2024. 5. 6. 이전 1 다음 반응형
