WOONY's 인사이트

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

오늘도 어김없이 찾아오는 시험날. 이번 주차는 망이다...ㅎ.. 자꾸 출가하는 멘탈을 억지로 억지로 잘 붙잡다가도 다잡기가 쉽지 않았다. 설상가상으로 정글 1기 관련 소식을 접하고 나니 더욱 마음이 불안해진다. 이럴 때는 책만큼 좋은 도구가 없다. 박지웅 대표의 는 책이 요즘 화젯거리다. 바로 오늘 푼 문제 정리부터 하려다 말고 잠깐 책을 읽었다. 맞다. 깜빡하고 있었다. 분명 이 길을 선택할 때 이기는 게임을 한다는 확신이 있었다. 커리어를 전향하는데 6개월을 절대 넘기지 않겠다는 자신이 있었다. 정글은 그 시작이었다. 하지만 정글이라는 판 하나 가지고 100%라는 승률이 나오겠나. 이길 수 있는 판을 짰다면 나머지는 내 몫이다. 압도적인 양과 전략으로 승부한다. 목표를 잘 생각하자. 내 목표는 개발자..

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문을..

파이썬 내장함수인 map을 이용하면 숫자를 담고 있는 numbers 내에 있는 리스트 값들을 string으로 바꾸고, join을 사용하여 최종적으로 string이 출력되도록 한다. numbers = [10, 20, 30] ' '.join(map(str, numbers)) ## 출력 결과 10 20 30 이전에 썼던 방법은 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문 돌면..

크루스칼 알고리즘 오늘은 크루스칼 알고리즘만 빠르게 정리하는 것으로. 크루스칼 알고리즘은 대표적인 최소 신장 트리 알고리즘에 해당한다. 최소 신장 트리는 무엇이냐? 최소 신장 트리 최소 신장 트리는 최소한의 비용으로 구성되는 신장 트리를 말한다. 예를 들어 N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게 도로를 설치하는 경우를 생각해보자. 두 도시 A, B를 선택했을 때 A에서 B로 이동하는 경로가 반드시 존재하도록 도로를 설치한다. 이때 모든 노드는 서로 연결되면서 & 최소 비용으로 연결될 수 있도록 한다. 1->3에서 비용은 25에 해당하므로, 이를 제거하고 1->2, 2->3으로 트리를 구성할 때 최소 비용으로 트리를 구성할 수 있다. 크루스칼 알고리즘..

0. 목차 1. 트리 순회 - Preorder / Inorder / Postorder 2. 이진 검색 트리 - 재귀를 활용해 검색하는 방법 3. 서로소 집합 구조 & 유니온 파인드 & 크루스칼 알고리즘: 서로소인 부분집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 1. 이진 검색 트리 & 데이터 탐색 방법: 트리 순회 - Preorder / Inorder / Postorder 개념 정리부터 먼저 하고 넘어가자. 이진 트리란, 부모 노드가 왼쪽/오른쪽 자식 이렇게 두 개의 자식 노드만을 갖는 트리를 말한다. 이때, 왼쪽/오른쪽 자식을 구분한다. 이진 트리에 대한 보다 자세한 정리는 아래 챕터에서 하기로 하고, 여기서는 곧바로 문제를 보면서 이진 트리에서 데이터를 탐색하는 방법인 트리 순회에 대해..

오늘 2주차 시험에서는 1시간 반 동안 겨우 1문제 풀었다. 공부할 때도 엄청 빡셌지만 어찌어찌 익혔다는 느낌이 없잖았는데 결과가 이러니 참담하다 싶지만..! 그래도 한 문제 푼 게 어딘가! 아자자! 잘했다! 한 걸음씩 가는 거지! 1. MOO 게임(#5904) 문제 링크는 여기. 도저히 어떻게 접근해야 좋을지 몰라, 맨 처음에는 아예 수열 자체를 구해버리려고 했다. 10^9를 넘는 가장 작은 수열을 뽑으려고 해봤는데 대략 n이 10~20 사이에서 될 것 같더라! 문제는 n=12를 넣을 때부터 연산이 뻗는다는 느낌이 들기 시작하더니 n=15쯤 가니 허송세월하고 있더라. 이렇게는 도저히 못 풀겠다 확신만 하고 끝남..^_^ 지훈이의 풀이를 공부한 내용을 정리하자면, 이 문제는 재귀로 이루어진 점화식을 길이..