알고리즘, 자료구조

https://hongjw1938.tistory.com/47 알고리즘 - Dynamic Programming(동적 계획법) 1. 개요 DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 hongjw1938.tistory.com DP란? DP는 하나의 큰 문제를 여러 개의 작은 문제로 나눠서 결과를 저장하여 큰 문제를 해결할 때 사용하는 문제해결 패러다임이다. 쉽게 표현하면 큰 문제를 작은 문제로 쪼개서 답을 저장해두고 재활용하는 것이다. 장점 DP는 재귀와 유사하다. 재귀의 단점은 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산을 할 수 있다는 것이다. DP는 재귀의..

https://velog.io/@gillog/Java-Priority-Queue%EC%9A%B0%EC%84%A0-%EC%88%9C%EC%9C%84-%ED%81%90 [Java] Priority Queue(우선 순위 큐) PriorityQueue란 우선순위 큐로써 일반적인 큐의 구조 FIFO(First In First Out)를 가지면서, 데이터가 들어온 순서대로 데이터가 나가는 것이 아닌 우선순위를 먼저 결정하고 그 우선순위가 높은 데이터 velog.io 우선순위 큐란? 큐 : FIFO 구조로 먼저 들어간 값이 먼저 나오는 자료구조이다. 우선순위 큐 : 들어간 값 중 우선순위가 가장 높은 값이 먼저 나오는 자료구조이다. Java에서 우선순위 큐 java에서 우선순위 큐는 java.util.Priority..

이분탐색이란 ? 이분탐색은 정렬되어있는 리스트에서 탐색 범위를 반씩 좁혀가며 탐색하는 방식이다. https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net package codingtest; import java.util.*; import java.io.*; public class Main{ static int N; static int M; static int[] A; static int[] B; publi..

https://loosie.tistory.com/237 [알고리즘] 분할정복 알고리즘 정리 (합병 정렬, 퀵 정렬, 이진 탐색) (Java) 분할정복(divide and conquer) 알고리즘 분할정복 알고리즘 (Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다. 대표적인 예로는 정렬 알고리즘 loosie.tistory.com 분할 정복이란 ? 분할 정복은 해결할 수 없는 문제를 작은 문제로 분할하여 해결하는 방법이다. 대표적으로 퀵 정렬, 합병 정렬, 이진 탐색, 선택 문제, 고속 푸리에 변환 등이 있다. 선택 정렬과 삽입 정렬은 O(n^2)의 시간복잡도를 갖는다. 분할정복 방식인 합병 정렬은 O(nlogn), 퀵 정렬..