일지 & 개발

이론 이번에 볼 자료구조는 깊이 우선 탐색(DFS)이다. 깊이 우선 탐색은 영어로 Depth First Search이고 줄어서 DFS라고 많이 부른다. 그래프 탐색 알고리즘 중 하나인데 그래프 말고도 트리에서도 적용이 된다. 반대로 넓이 우선 탐색(BFS)도 있는데 코드 테스트에서는 DFS 보다 BFS가 많이 나오지만 그래도 공부를 해야 되는 기본적인 알고리즘이다. DFS알고리즘을 알기위해서는 트리, 그래프, Stack 자료구조를 알아야 이해가 되는데 이 부분은 우선 공부한 뒤로 이 알고리즘을 공부하는 것을 추천한다. 안 그러면 이 뒤에 내용이 이해가 안 될수가 있기 때문이다. 자세한 설명은 아래의 사이트에 참조하면된다. https://namu.wiki/w/%EA%B9%8A%EC%9D%B4%20%EC%9..

이론 이번에 볼 알고리즘은 동적계획법(Dynamic Programming)이다. 이 알고리즘은 줄어서 dp라고 많이 불리고 코딩테스트에도 자주 나오는 유형이라서 무조건 알아야 되는 알고즘이다. 동적계획법 알고리즘은 복잡하고 여러개의 연산이 있는데.. 작은 단위를 연산을 한다음 반복되거나 중복 되는 연산은 최소화 해서 풀어 나가는 알고리즘이다. 동적계획법은 시간 복잡도상에서 최적으로 나타낼수있는 강력한 알고리즘이지만 완벽한 알고리즘이라고 할수는 없다. dp로 해결하는 이유는 메모리 절약과 시간복잡도의 최적화로 되어 있지만 문제 푸는데는 어느정도 한계가 있고 이론보다는 접근 방법이나 아이디어가 더 많이 요구되기도 한다. 자세한 설명은 아래 사이트에서 찾아 보면된다. https://ko.wikipedia.or..

이론 이번에 볼 자료구조는 트리이다. 트리는 연결리스트(Linked List)에서 노드간의 부모와 자식을 갖는 자료 구조이다. 연결리스트는 앞과 뒤로 이루어 져 있는데 트리는 계층별로 상하 관계로 되어 있는 구조이다. 트리는 코딩테스트 뿐만 아니라 실무나 실생활에서도 많이 접하기 때문에 반드시 알아야 될 기본 자료구조이다. 자세한 설명은 밑에 사이트에 참조하면된다. https://namu.wiki/w/%ED%8A%B8%EB%A6%AC(%EA%B7%B8%EB%9E%98%ED%94%84) 트리(그래프) - 나무위키 트리를 정의할 때에는 다양한 정의가 쓰이고, 다음은 모두 동치이다. GGG는 회로가 없는 연결 그래프이다.GGG는 회로가 없고, 단순 그래프의 형태를 유지하면서 간선을 추가할 경우 회로가 생긴다 ..

이론 이번에 볼 알고리즘은 백트래킹이다. 백트래킹을 알아두면 대부분 해를 찾는데 도움이 될것이다. 백트레킹은 탐색하는 도중 중복되거나 해를 찾는 방향이 맞지 안 맞으면 그 부분을 탐색하지않는다. 이를 가지치기라고 하는데, 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미이다. 이러면 불필요한 탐색을 할 필요가 없어서 기존 완전 탐색보다 시간적이나 메모리가 단축할수 있다. 자세한것은 아래 사이트에서 확인해보면된다. https://ko.wikipedia.org/wiki/%ED%87%B4%EA%B0%81%EA%B2%80%EC%83%89 퇴각검색 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 퇴각검색(영어: backtracking, 한국어: 백트래킹)은 한정 조건을 가진 문제를 풀..

이론 이번에 볼 자료구조는 힙이다. 힙은 완전 이진트리에서 최대값 또는 최소값을 찾아내는 자료구이다. 자세한 설명은 아래 사이트에서 확인해보면된다. https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) 힙 (자료 구조) - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 1부터 100까지의 정수를 저장한 최대 힙의 예시. 모든 부모노드들이 그 자식노드들보다 큰 값을 가진다. 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 ko.wikipedia.org

이론 그리디 알고리즘은 탐욕 알고리즘이라고 부르기도 한다. 즉, 매 순간 선택할때 가장 좋은것을 선택하는 알고리즘이다. 이 알고리즘은 이론상 설명 단순하고 다른 알고리즘에서 기초적으로 다루는 알고리즘이다.

이론 1차원 배열 누적합 누적합부터 먼저 설명하면 0번째 인덱스 부터 N 번째 인덱스까지 탐색하면서 인덱스 i일때 0번째 인덱스 부터 0번째 인덱스합을 말한다. Python array = [1, 8, 7, 4, 3, 5, 6] n = len(array) prefix_sum = [0] * n for i in range(n): for j in range(i+1): prefix_sum[i] += array[j] Java import java.util.Arrays; public class Main { public static void main(String[] args){ int[] array = {1, 8, 7, 4, 3, 5, 6}; int n = array.length; int[] prefix_sum = n..

이론1. LIS이란? LIS 개념을 이해하기 전에 기본적으로 DP(동적 계획법)또는 이분탐색을 알아야 된다. DP 에 관련 내용은 아래 사이트에 참조하면된다.https://jih3508.tistory.com/89 [알고리즘 이론] 동적계획법(Dynamic Programming, DP)이론 이번에 볼 알고리즘은 동적계획법(Dynamic Programming)이다. 이 알고리즘은 줄어서 dp라고 많이 불리고 코딩테스트에도 자주 나오는 유형이라서 무조건 알아야 되는 알고즘이다. 동적계획법 알jih3508.tistory.com  LIS, 최장 증가 부분 수열은 나열된 배열이나 리스트에서 원소를 몇개 제외하고 오름차순또는 내림차순으로 가징 긴 수열을 말한다 예를 들어 {1, 5, 3, 6, 7, 9, 4, 2, ..