programmer life guidance 101

> 다익스트라 알고리즘 이제부터 그래프에 대한 글만 엄청 쓸 겁니다. 한 11~12개 정도 예정되어 있네요. 그래프... 정말 어렵고, 답없고, 온갖 문제가 많기로 유명합니다. 그 중에서도 처음을 장식할 최단 경로 알고리즘은 그 종류부터 3개나 됩니다. 그 중 첫 번째 알고리즘인 다익스트라 알고리즘(Dijkstra's algorithm)에 대해서 알아보겠습니다. 이 알고리즘이 하는 일은 그래프의 어떤 정점 하나를 시작점으로 선택하고, 나머지 정점들로의 최단거리를 모두 구합니다. 시작점 자신이야 뭐 그냥 0입니다. 정점 개수가 V, 간선 개수가 E일 때 기본적인 최적화를 거치면 O(ElogV)의 시간복잡도를 갖습니다. 그래프는 무향이거나 유향인데 대체로 유향인 경우가 많고, 간선마다 이동거리가 존재합니다...

Two Pointer & Sliding Window:facepunch: > Two Pointer 1차원 배열이 있고, 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가며 원하는 것을 얻는 형태의 알고리즘!! 대표적인 유형으로는 백준 2003 : 수들의 합2 문제를 보겠습니다. N칸의 1차원 배열이 있을 때, 부분 배열 중 그 원소 합이 M이 되는 경우의 수를 구하여라!? 모든 경우의 수를 다 테스트한다면, 구간 합을 구간합 배열로 O(1)만에 구한다고 해도 경우의 수가 이미 O(N2)이라 fail이다. 이 문제에서 각 원소는 자연수이고 M 또한 자연수인데, 이 조건이 성립하면 사용할 수 있는 알고리즘은 아래와 같다. 포인터 2개를 준비한다. (lo, hi), (l, r), (p, q)..

www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 문제 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다. 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오. 친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다. 입력 첫째 줄에 테스트 케이스의 개수..

www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 �� www.acmicpc.net 문제 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 반드시 먼저 완료되어야 할 작업들이 있다. 이 작업들은 번호가 아주 예쁘게 매겨져 있어서, K번 작업에 대해 선행 관계에 있는(즉, K번 작업을 시작하기 전에 반드시 먼저 완료되어야 하..

> Iterator Iterator는 자바의 컬렉션 프레임웍에서 컬렉션에 저장되어 있는 요소들을 읽어오는 방법을 표준화 하였는데 그중 하나가 Iterator 인터페이스이다. public interface iterator { boolean hasNext(); Object next(); void remove; } boolean hasNext() : 읽어올 요소가 남아있는지 확인한다. 있으면 true, 없으면 false를 반환 Obejct next() : 읽어올 요소가 남아있는지 확인하는 메소드. 있으면 true 없으면 false를 반환 void remove() : next()로 읽어온 요소를 삭제한다. 따라서 next()를 호출한 다음에 remove()를 호출해야 한다. ( 선택적 기능임 ) List 정렬시..

> 최소 신장 트리(MST) Minimum Spanning Tree Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리 각 간선의 가중치가 동일하지 않을 때 단순히 가장 적은 간선을 사용한다고 해서 최소 비용이 얻어지는 것은 아니다. MST는 간선에 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것이다. 즉, 네트워크(가중치를 간선에 할당한 그래프)에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결하는 것이다. MST의 특징 간선의 가중치의 합이 최소여야 한다. n개의 정점을 가지는 그래프에 대해 반드시 (n-1)개의 간선만을 사용해야 한다. 사이클이 포함되어서는 안된다. MST의 사용사례 통신망, 도로망, 유통망에서 길이, 구축비용, 전송시간 등을 최소..

> 스패닝 트리(ST) 그래프 내의 모든 정점을 포함하는 트리 Spanning Tree = 신장 트리 = 스패닝 트리 Spanning Tree는 그래프의 최소 연결 부분 그래프이다. 최소 연결 = 간선의 수가 가장 적다. n개의 정점을 가지는 그래프의 최소 간선 수는 (n-1)개이고, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것이 바로 Spanning Tree가 된다. 즉, 그래프에서 일부 간선을 선택해서 만든 트리 스패닝 트리의 특징 DFS, BFS를 이용하여 그래프에서 신장 트리를 찾을 수 있다. 탐색 도중에 사용된 간선만 모으면 만들 수 있다. 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. Spanning Tree는 트리의 특수한 형태이므로 모든 정점들이 연결되어..

programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 문제설명 n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 제한사항 섬의 개수 n은 1 이상 100 이하입니다. costs의 길이는 (..

> 유니온 파인드(Union-Find) 그래프 알고리즘으로 합집합 찾기 알고리즘이다. 상호 배타적 집합(Disjoint-set)이라고도 한다. Disjoint Set이란 서로 중복되지 않는 부분집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다. 유니온파인드의 특징 Union-Find란 Disjoint Set을 표현할 때 사용하는 알고리즘이다. 집합을 구현하는 데는 비트 벡터, 배열, 연결 리스트를 이용할 수 있으나 그중 가장 효율적인 트리 구조를 이용하요 구현한다. make-set(x) 초기화 x를 유일한 원소로 하는 새로운 집합을 만든다. union(x,y) 합하기 x가 속한 집합과 y가 속한 집합을 합친다. find(x) 찾기 x가 속한 집합의 대표값(루트 노드값)을 반환한다. 즉 ..

> 위상정렬(Topological Sort) 어떤 일을 하는 순서를 찾는 알고리즘 => 즉, 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것 위상정렬의 특징 하나의 방향 그래프에는 여러 위상 정렬이 가능하다. 위상 정렬의 과정에서 선택되는 정점의 순서를 위상 순서(Toplogical Order)라 한다. 위상 정렬의 과정에서 그래프에 남아 있는 정점 중에 진입 차수가 0인 정점이 없다면, 위상 정렬 알고리즘은 중단되고 이러한 그래프로 표현된 문제는 실행이 불가능한 문제가 된다. => 위상정렬이 가능하려면 DAG(Directed Acyclic Graph, 방향성이 있으며 사이클이 없는 그래프)여야 한다. 말 그대로 두 노드 A, B 사이에 A->B 같은 관계가 성..

문제설명 n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요. 제한사항 노드의 개수 n은 2 이상 20,000 이하입니다. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다. 입출력 예 입출력 예 설명..

프로그래머스 힙 - 디스크컨트롤러 :programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를�� programmers.co.kr 처음 문제를 접했을 때는 가장 빠른 시간을 기준으로 정렬한 뒤 계산하는 greedy 알고리즘이 생각났다. 하지만 곧 문제유형이 Heap인 것을 보고 클래스를 정의하여 우선순위큐에 사용해야함을 인지했다. 하지만 나는 단순히 pq하나만 구현하여 그 안에서 정렬해준 뒤 계산하면 되는 줄 알았지만... 문제는 풀리지 않았고 ( 언제쯤 혼자..

> 트라이(Trie) 문자열에서의 검색을 빠르게 해주는 자료구조 래딕스 트리(radix tree) 나 접두사 트리(prefix tree)라고도 한다. 우리는 정수형 자료형에 대해서 이진검색트리를 이용하면 O(logN)의 시간만에 원하는 데이터를 검색할 수 있다. 하지만 문자열에서 이진검색트리를 사용한다면 문자열의 최대길이가 M이라면 O(MlogN)의 시간 복잡도를 가지게 될 것이다. 우리는 문자열 검색을 개선하기 위해 트라이를 이용하여 O(M)의 시간만에 원하는 문자열을 검색할 수 있다. 트라이라는 명칭은 Retrieval에서 유래한다. 트라이가 retrieve(탐색)하는데 유용한 걸 생각하면 납득ㅇ ㅣ디ㅗㄴ다. 자 그러면 트라이는 어떻게 문자열의 검색을 O(M)만에 처리할까? 아래 그림은 문자열 집합 ..

프로그래머스 2020 KAKAO BLIND RECRUITMENT 블록 이동하기 :https://programmers.co.kr/learn/courses/30/lessons/60063 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr 대표적인 BFS 구현문제 인줄 알고 쉽게 덤벼들었지만, 고려해야 할 게 많아 꽤 까다로웠다. 처음 생각은 bfs로 회전과 직선이동을 나누고 동서남북대각선 체크해주면서 벽이 아닌 곳의 최대좌표를 리턴해주며 최소시간을 구하는 것이었다. 하지만 테스트케이스를 충족하지 못하였고, 다른 블로그를 참고해서 답을 고쳤다. (..

===Operation Diagram===:ballot_box_with_check: 크게 CLE로 동작되는 커맨드 사이클, ALE로 동작되는 어드레스 사이클, 데이터사이클(WE, RE)로 나뉘어진다. 보통 낸드플래시의 작업 순서는 삭제 - 쓰기 - 읽기 이다. > ERASE CLE로 전체 사이클을 시작하고 ERASE의 의미로 60h를 때려준다 그 다음은 ALE 사이클이다. 이번에는 Column Address 없이 Row Address만 적어준다. 그 이유는 블럭단위로 ERASE가 일어나기 때문이다. 커맨드 버스 사이클이 CLE 진행되어 지우기 2nd 커맨드가 기록된다. 기둘기둘.....(tBERS) R/B신호를 GPIO 포트 단자로 감시하다가 종료되는걸 캐치 상태비트 체크! 블록 기반 지우기 작업은 Er..