전체 글 (24) 썸네일형 리스트형 [백준, DP] 1149 RGB 거리 https://www.acmicpc.net/problem/1149 DP 문제를 볼때마다 풀 수 있을 것 같았지만 역시나 ㅎ.. 잘 안된다. 점화식을 잘 만들었다 생각했으나 오산이었다. 기존 $$ a_{n} = a_{n-3} + min(a_{n-2}, a_{n-1})$$ 처음에는 3개의 집이 서로 다른 색이어야하는 것으로 이해했다.그래서 누적합으로 저장한 뒤, 연속 3개의 색이 올 수 없기에 무조건 3번째마다 같은 색이 올 것이라고 생각하고 위와 같은 점화식을 생각했었다. 잘못된 점화식이었다.개선점화식을 고민하다 결국 찾을 수 없어서 다른 분들의 풀이를 참고했다.정답을 확인한 이후, 내가 잘못 이해했다는 것을 인지했다. 정답은 n번째 집의 색에 따라 이전 n-1 번째 집의 남은 2개의 색에 대한 경우.. 최단 경로(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. 큰 수의 법칙목표 : 다양한 수로.. [백준, 분할정복/재귀] 1074_Z https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 고민을 했지만 결국 해결책을 얻지 못했다. 처음 풀어볼 때, 재귀쪽으로 2 X 2까지 나누어진 뒤에 무언가 진행되어야한다라는 방식으로 고민했지만 항상 재귀와 관련한 문제만 만나면 블루스크린 뜨는 것 마냥 머리가 돌아가다 만다... 이 문제도 다른 분의 해결책을 참고해서 풀었다. 2가지 방법으로 풀 수 있었다. 1. 분할정복 2. 재귀 분할정복 N X N 배열을 4개의 사분면으로 나눠서 생.. 이전 1 2 3 다음
