WOONY's 인사이트

오늘부로 정글이 끝났다. 소회글도 한 번 적었어야 했는데, 여기에 개발 글 외에 다른 글을 쓰기가 부담스러워지는 바람에...나중에 회사 합격하고 한 번에 쓰는 걸로 할 예정이다. 당분간은 딴소리 없이 공부 관련 내용만 올릴 생각! 바로 가보자. -- 알고리즘 공부를 다시 시작하면서 프로그래머스 고득점 kit을 풀기 시작했다. 가장 먼저 나오는 단원인 해시부터 호기롭게 시작했건만 Level 2부터 턱 막혀버리는..게 아닌가. 그래서 내리 연달아 2문제를 공부하고 나서 관련 개념을 정리했다. 해시(Hash table) Hash table: key를 value에 매핑하는 array 형태의 자료구조 우리가 흔히 해시라고 부르는 자료구조는 엄밀히 말하면 해시 테이블(Hash table), 또는 해시 맵(Hash ..

드디어 4주 간의 알고리즘 커리큘럼이 끝나는 날. 시원섭섭하다. 드디어 끝나서 후련한 마음 반, 지금부터 본격적으로 빡센 일정인 C언어 기반 커리큘럼이 다가왔다는 사실에 두려움 반. 하지만 그 알고리즘마저 해낸 마당에, 앞으로도 지금처럼 꾸역꾸역 하면 어떻게든 하겠지. 알고리즘 커리는 오늘로 끝이지만 앞으로 매일 한 문제씩 꼬박꼬박 풀 예정. 꾸준히 리뷰해야겠다. 이제 알고리즘 풀이 리뷰는 따로 카테고리를 만들어서 올릴 예정. 1. 계단 오르기(#2579) 마침 어제 풀었던 문제가 시험에 나와서 아주 기분 좋게 풀었더랬다. dp를 처음 계단을 오를 때 기점으로 생각하는 게 아니라 n번째 계단에 도착했을 때를 기점으로 거꾸로 생각하면 훨씬 간단하게 풀 수 있다. 아래 그림을 보자. n번째 계단에 도착하는 ..

1. 코치님 조언 1. 혹시 아직도 뭐가 뭔지 모르겠다? 내가 생각한 것을 프로그램으로 만들 수 있는지 자기 자신에게 질문해보기. 이 과정의 가장 근본적인 목표는 (코테 통과가 아니라) 내가 원하는 작업을 컴퓨터에게 시키는 능력을 키우는 것입니다. 일단, 내가 원하는 것을 컴퓨터에게 쉽게 시킬 수 있다면 잘 따라가고 있다고 생각합니다. 미래에 내가 원하는 것, 해내야 할 작업이 뭐가 될 지 모르기 때문에 정형화된 문제들로 연습하는 것이고 이왕이면 효율적으로 빠르게 컴퓨터에게 일을 시키기 위해 계산 복잡도를 고려하고, 문제 유형을 나누어 익히고, 정해진 시간 안에 프로그램을 짜는 연습을 하는 것입니다. 2. 이제까지 배운 것들 사이 상관관계 눈치 빠른 분들은 알고 계시겠지만 각 주의 keyword들은 서로..

1. 점프(#2253) 처음에 떠올렸던 아이디어는 출발지점에서 중간 도착지점을 저장하는 방식으로 DP 테이블을 짜는 방식이었다. 예를 들어 1번 돌에서 10번 돌까지 간다고 하면 1번 (+1)=> 2번 (+2)=> 4번 => 7번 => 10번이니까 D[1][2] = 1, D[2][4] = 2, D[4][7] = 3, D[7][10] = 3 이렇게 해서 최종적으로 D[1][10] = D[1][2] + D[2][4] + D[4][7] + D[7][10] 이런 식으로. 그런데 점화식을 짜려니 뭔가 꼬이기 시작하더라..가장 관건은 속도였는데, 나는 속도를 dp 테이블에 value로 저장했으나 이를 어떻게 점화식으로 풀어내야 할지 감이 잘 오지 않았다. 결국 풀지 못하고 풀이를 검색해서 찾아봤다. 풀이에서는 속도..

오늘은 그리디 알고리즘에 대해 공부한 내용을 빠르게 정리하고 마무리. 앞에서 배웠던 재귀 관련 알고리즘으로는 크게 두 가지가 있었다. 분할 정복(Divide and Conquer)과 동적계획법(Dynamic Programming)이 그것이다. 1. 분할정복은 큰 문제를 중복 없는 작은 문제들로 분할하는 방법이다. 재귀적으로 작은 문제부터 해결한다. 2. 반면, 동적계획법은 작은 문제들로 쪼개되 이 작은 문제들 중 중복되는 애들을 DP 테이블에 저장해두고 같은 값이 나왔을 때 계산 없이 바로 테이블에서 꺼낸다. 그러면 오늘 다룰 그리디 알고리즘은 어떤 친구일까? 이름처럼 말 그대로 Greedy하게 선택하는 알고리즘을 뜻한다. 즉, 현재 상태에서 가장 좋은 선택을 반복해서 해를 구성한다. 예제로 동전 교환 ..

0. 목차 1. 다익스트라 알고리즘 2. 최소비용 구하기(#1916) 1. 다익스트라 알고리즘 다익스트라 알고리즘은 DP를 이용한 대표적인 최단경로 알고리즘이다. 특정한 하나의 노드(출발점을 고정)에서 다른 모든 노드로 가는 최단 경로를 알려주는 알고리즘이다. 다익스트라 알고리즘의 핵심 개념만 요약정리하면 우선순위 큐(Heap)을 사용한다는 점 (최소 비용을 뽑아내기 위해) 이차원 배열에 값을 미리 저장(DP)해둔다는 점(그때그때 최단 경로/최소 비용 등 최솟값을 배열에 저장해두고 갱신하는 식으로) 다익스트라에서 음의 간선은 포함할 수 없다는 점 (음의 간선까지 고려 가능한 알고리즘은 벨만포드가 있다는데 이번에는 쓸일이 없어서 패스) 다익스트라와 DP 다익스트라 알고리즘은 하나의 최단거리를 구할 때 그 ..

문제 링크 링크 풀이 이제 어느 정도 bfs를 풀다보니 이런 구현 기반 bfs 문제에 대한 감이 잡힌다. 지도 위에서 인접한 곳에 뭔가를 찾는다거나 바꾼다거나 할 때 흐름을 보면 1. dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]과 같이 x, y를 기준으로 위/아래/양옆으로 갈 수 있는 방향을 설정한다. 2. 문제에서 주어지는 지도를 MAP이라 하고 해당 위치를 방문했는지 체크하는 지도를 visited로 새로 생성한다. (아직 어디도 방문하지 않았으니 전부 방문 X로 체크. False로 만들어도 되고 0으로 만들어도 되는데 지금 문제와 같이 각 구역마다 새로운 번호를 매길 때는 0으로 만들어놓고 서로 다른 구역에 대해 다른 번호를 매기는 식으로 해도 괜찮을듯.) 3. 이중 for문을..

0. 목차 1. 플로이드 와샬 개념 정리 2. 구슬 찾기 문제 풀이 3. 동전 2 풀이 (with DP) 1. 플로이드 와샬 개념 정리 개념 정리 출처: 나동빈 유튜브 플로이드 와샬 알고리즘은 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산하는 알고리즘이다. 다익스트라와 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다. 하지만 다익스트라가 출발점을 고정했을 때의 최단 경로만을 계산한다면 플로이드 와샬은 전체 통으로 스캔하는 개념이라고 생각하면 될듯. 하지만 여기서 무식하게 싹다 스캔하는 게 아니라 일종의 DP를 이용해 최단거리 노드를 기록한다. 시간복잡도 플로이드 와샬의 시간 복잡도는 O(n**3)이다. 점화식 Dab = min(Dab, Dak + Dkb)이며, 각 단계마다 ..

0. 목차 1. 아침 산책 풀이 2. 위상 정렬 점점 말이 없어진다.. 바로 풀이로 가자. 1. 아침 산책 (#21606) 먼저 문제 링크. 문제 풀이의 논리는 아래와 같다. 문제에서는 실내 노드에서 출발해 실내 노드로 도착한다고 설명한다. 그래서 실내를 기준으로 생각하게 되나, 이 문제는 실외 노드를 중심에 놓고 인접한 실내 노드를 세는 방식이 훨씬 편하다. 먼저 실외 노드를 기준으로 인접해있는 실내 노드 수를 count한다. 실외 노드를 가운데 놓고 인접한 실내 점 n개가 붙어있을 때, 갈 수 있는 경로의 수는 n * n-1 (n개의 실내 점 중 하나 고르는 경우의 수 X 실외 점 1개 고르는 경우의 수 1 X 앞에서 고른 1개의 실내 점 제외한 n-1개 점 중 하나 고르는 경우의 수) for문 돌면..

1. 이진 탐색(Binary Search) 보통 우리가 탐색을 시도할 때는 순차적으로 탐색하는 방법을 이용한다. 기존의 순차 탐색은 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 하나씩 데이터를 확인하는 방법이다. 리스트에서 특정 데이터를 찾기 위해 검사할 때, 별 다른 조건이 없으면 순차적으로 탐색을 시도한다. 이와 달리 이진 탐색은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 여기서 전제는 탐색하려는 리스트가 정렬되어 있어야 한다는 점이다! 이진 탐색을 하기 위해서는 탐색 범위를 설정해줘야 하는데, 총 세 가지 포인트가 있다. 시작점 (start) 끝점 (end) 중간점 (mid = (start+end)//2) 이 셋을 이용해 탐색한다. 순서는 아래와 같..