Data Structure and Algorithm (7) 썸네일형 리스트형 LIS(최장 증가 부분 수열, Longest Increasing Subsequence) 요즘 코테를 소홀히 한 것도 있지만 부쩍 코테 난이도가 올라간 것 같다. CS 기본 공부를 하건, 면접 준비를 하건, 자소서를 쓰건, 결국 취업을 하기 위해서는 코테를 통과해야하는데 매번 떨어진다. 단순히 양치기가 아니라 효율적인 공부 방법을 마련하고 더 제대로, 본격적으로 코테를 준비해야할 것 같다. 예전에 11053번 문제를 풀 때, 참고하고 알고리즘을 공부했었는데 이보다 조금 더 난이도 높은 11054번(가장 긴 바이토닉 수열) 문제를 풀다가 알고리즘을 까먹어 내꺼로 만들고자 정리한다. https://www.acmicpc.net/problem/11053https://www.acmicpc.net/problem/11054 최장 증가 부분 수열이란(LIS)?원소 n개일 때, 일부 원소들만 골라내서 만든.. 최단 경로(Shortest Path)란? 이것이 코딩 테스트다 with 파이썬 - Ch. 9 최단 경로를 공부하고 기록했습니다.이코테 유튜브 영상을 참고해 작성했습니다.Shortes Path(최단 경로)- 가장 짧은 경로를 찾는 알고리즘- '길 찾기' 상황에 따른 효율적인 알고리즘들이 있다.예를 들어, 1대 1, 1대 다, 다대 다 등 다양한 목적에 따른 알고리즘 최단 경로 문제는 주로 그래프를 이용해 표현한다. 각 지점 = '노드', 연결된 도로 = '간선'. 해당 책에서 설명하는 알고리즘은 2가지다.1. 다익스트라 알고리즘2. 플로이드 알고리즘 다익스트라 알고리즘(Dijkstra)- 특정한 노드에서 다른 노드들까지의 각각의 최단 경로를 구해주는 알고리즘- 즉, 특정 1개의 노드에서 다른 노드들까지의 거리를 구하는 알고리즘이다.- '음의 .. 동적 계획법(Dynamic Programming)이란? 이것이 코딩 테스트다 with 파이썬 - Ch. 8 다이나믹 프로그래밍을 공부하고 기록했습니다. Dynamic Programming(동적 계획법)- 메모리 공간을 더 사용해서 연산 속도를 증가시키는 방법- 대표적인 예시) 피보나치 수열 DP를 사용해서 문제를 풀 수 있는 조건큰 문제를 작은 문제로 나눌 수 있는 경우작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.Memorization 기법- DP 구현 방법 중 하나- 사전에 메모리 공간을 정의하고 한번 구한 결과를 메모- 이후 같은 식을 다시 호출할 시, 메모한 결과를 그대로 가져오는 기법- 값을 저장하는 방법이기에 캐싱(Caching) 이라고도 함 탑다운 방식- 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식- 메모 및 방문결과.. 이진 탐색(Binary Search)란? 이것이 코딩 테스트다 with 파이썬 - Ch. 7 이진 탐색을 공부하고 기록했습니다.이진 탐색(Binary Search)- 반으로 나눠가면서 값을 찾아가는 알고리즘이다.- 조건 : 값이 정렬되어 있어야 한다!!- 시간 복잡도 : O(logN) 해당 알고리즘을 활용해서 풀 수 있는 문제가 많이 출제된다. 시작점, 끝점, 그리고 중간점을 활용해 값들의 크기 및 높낮이를 비교하며 탐색해야하는 문제들에 효과적인 알고리즘이기에 필수적으로 암기하고 활용할 수 있도록 해야한다. 사용하는 변수의 갯수는 3개- 시작점, 끝점, 중간점 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 희망하는 데이터를 찾는 과정이다. 1번 확인할때마다, 중간점을 옮기며 원소의 갯수가 절반씩 줄기에 시간 복잡도가 O(lo.. DFS(Depth-First Search)/BFS(Breadth-First Search)란? 이것이 코딩 테스트다 with 파이썬 - Ch. 5 DFS/BFS를 공부하고 기록했습니다. 탐색(Search)- 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 그래프, 트리 등 다양한 자료구조에 대한 탐색 알고리즘들은 코딩 테스트에서 흔하게 출제되기에 필수적으로 알아둬야한다. 해당 알고리즘을 활용해 다양한 솔루션들로 문제를 해결할 수 있기에 꼭 제대로 숙지하자. DFS, BFS 알고리즘을 설명하기 이전, 스택(Stack)과 큐(Queue) 자료구조, 재귀에 대한 설명은 생략하고 진행한다. DFS(Depth-First Search)- 깊이 우선 탐색- 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘- 스택 최상단 노드의 방문하지 않은 인접 노드들을 우선적으로 처리하는 방법- 즉, 가능한 깊이 내려.. 구현(Implementation)이란? 이것이 코딩 테스트다 with 파이썬 - Ch. 4 구현을 공부하고 기록했습니다.구현(Implementation) 이란?- 특정 알고리즘을 의미하는 것이 아니라 머릿속에 있는 알고리즘을 소스코드로 바꾸는 문제 유형을 의미한다. 요즘 많은 기업들이 코딩테스트 문제 유형으로 구현을 많이 내는 트렌드라 구현 문제들을 몇 번 풀어봤는데, 이게 뭔 문제인가 싶었다. 늘 그렇듯 어떤 알고리즘 유형이고 어떻게 풀어야할까 고민했지만 못 풀었었다. 구현 문제는 해결책을 떠올리는 것은 어렵지 않지만 정확히 구현하는 것이 어렵다. 사용하는 언어의 정확한 문법과 라이브러리 등을 활용해 구현하는 것이 실력으로 결국 많은 문제를 풀어보면서 실력을 키우는 것이 중요하다. 구현 문제에서 고려해야할 것 중 하나는 메모리 용량이다. 파.. 그리디 알고리즘(Greedy)이란? 이것이 코딩 테스트다 with 파이썬 - Ch. 3 그리디 알고리즘을 공부하고 기록했습니다. 그리디 (Greedy) 알고리즘이란?- 각 상황에 대해 더 좋은 선택지만 선택하는 알고리즘 위 특징처럼 매 순간 좋은 선택지를 고르기에 이후에 발생하는 결과를 고려하지 않는 알고리즘이다.즉, 매 순간 좋은 결과를 선택하는 방법이 정답을 확실하게 보장하는지 확인해야한다! 딱히 별도로 외워야하는 코드 및 그런 건 없다.그러나, 문제를 보고 최소한 그리디로 풀 수 있다는 걸 확인할 수 있다는 걸 파악하는 게 핵심이다.즉, 정당성을 검토해봐야한다는 뜻이다! 주로 문제 지문에서 힌트가 주어진다.EX) ''가장 큰 순서대로", "가장 작은 순서대로" 이런 기준을 제시해준다. 실전 문제 1. 큰 수의 법칙목표 : 다양한 수로.. 이전 1 다음
