그냥 개발블로그에요

알아보기 큰 문제를 직관적으로 이해할 수 있는 작은 문제로 바꾸어서 소형화시킴. 작은 문제의 답을 메모이제이션, 그렇게 점점 큰 문제로 확장시켜 나간다. 사용 예시 예를 들어 계단오르기 문제가 그렇다. 계단을 오를때 한번에 한 계단 또는 두 계단씩 올라갈 수 있을 때, 총 7 계단을 올라간다면 그 방법의 수를 구해보자. 차근차근 처음부터 알 수 있는 것부터 따져보자. 먼저 첫번째 계단을 올라가는 방법은 한가지다. 두번째 계단을 올라가는 방법은 한칸+한칸, 두칸으로 두가지다. 세번째 계단을 올라가는 방법은, 두번째 계단에서 올라갈때와 첫번째 계단에서 올라갈때 경우로 나눠진다. 첫번째 계단으로 가는 방법은 한가지였고, 두번째 계단으로 가는 방법은 두가지였으므로, 세번째 계단으로 가는 방법은 세가지이다. 그렇..

알아보기 Greedy는 탐욕스러운 이라는 뜻이다. 선택의 순간마다 당장 제일 좋아보이는 경우를 선택한다. 여러 경우 중에 하나를 선택해야할 때, 그 순간 최적이라고 생각하는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 그 순간 선택한 결정은 지역적으로는 최적이지만, 전역적인(최종적인) 해답이 최적이라는 보장은 없다. 따라서 그리디 알고리즘을 적용하려면, 지역적으로 최적이면서 전역적으로 최적이어야 한다. 조건 Greedy choice property - 탐욕적 선택 속성 - 앞의 선택이 이후의 선택에 영향을 주지 않는다. optimal substructure - 최적 부분 구조 - 문제에 대한 최종 해결법은 부분 문제에 대한 최적해이다. 이러한 조건이 성립하지 않을때에도, 근사 알고리즘..

들어가며 코딩테스트를 잘 보기 위해서는 자료구조와 알고리즘을 공부해야한다고는 하는데 이 둘이 정확히 뭔지 둘 사이의 관계는 무엇인지 코테는 왜 이러한 지식을 요구하는지 이번에 정리하고자 한다. 둘 사이의 관계가 너무 헷갈렸다.. 자료구조 단어 그대로 자료를 담는 구조를 말한다. 그 구조는 논리적인 규칙으로 정해는 것이다. 예를 들어보자! 책장에 책을 꽂아두는 상황에서, 아무렇게나 꽂으면 원하는 책을 찾기 어렵다. 규칙1. 가나다 순으로 꽂아넣기 규칙2. 분야별로 꽂아넣기 등등 규칙을 정해서 꽂아넣으면 찾기 쉬울것이다. 하지만 여기서도 문제가 생길 수 있다. 규칙2로 정해진 책장 구조에서 분야별로 동일한 공간을 마련했지만 소설책은 거의 없어 공간이 널널하고, 만화책은 너무 많아 공간이 비좁다면, 공간을 비..

알아보기 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조이다. 정점은 노드, 간선은 노드를 연결하는 선으로 생각하면 된다. 그렇다고 해서 노드 간 부모 자식이라는 관계는 존재하지 않고 그냥 연결관계만 나타낸다. Tree와 비슷하지만, 그래프는 간선이 없는 노드도 존재한다는 점에서 차이를 나타낸다. 탐색방법 그래프 탐색이란 하나의 정점으로 부터 모든 정점들을 한번씩 방문하는 행위를 뜻한다. 예를 들어 섬끼리 이동할 수 있을지, 이동할 수 있다면 시간이 얼마나 걸리는지 등의 예시에서 사용될 수 있다. 어떤식으로 방문해야 할까? 여기서 두가지 방법이 있다. DFS 깊이 우선 탐색 BFS 너비 우선 탐색 구현 인접 행렬과 인접리스트 방식으로 구현할 수 있다. 인접행렬 2차원 배열 안에 모든 정점들의 ..