황현석 코드 일지

  제 6회 (4주차)  - 스위핑 알고리즘의 이론적 학습과 구현, 및 백준 응용 문제 풀기 2170번: 선 긋기 (acmicpc.net) 어려운 내용이 아닌 그냥 한번 훑으면서 같은 라인 단위로 만드는 방법이었다. 아직 스위핑 알고리즘이 뭔지 감을 잡지 못하였다. BaekJoon/선 긋기.java at main · Hy3ons/BaekJoon (github.com) 2836번: 수상 택시 (acmicpc.net) 해당 문제는 손님이 뒤로 가는 상황일 경우 역주행을 효율적으로 하는 것을 묻고 있다. 현재 나의 위치에서 내 위치 전으로 역주행 하는 상황이 앞에 안 나올 때, 모든 손님을 역주행 하면서 한번에 도착 지점으로 이동 시키면 가장 효율적 이게 된다. 방법은 아는데 구현을 어떻게 해야 될지 모르겠어, HashMap 과 HashSet을 그냥 남발하듯이 사용했다. 또한 내가 특정 지점에 도착 했는데, 역주행을 앞으로 내 위치 전으로 안해도 되는 상황이라는 것을 특정 하는 것이 어려웠다. BaekJoon/수상 택시.java at main · Hy3ons/BaekJoon (github.com) 후에 다시 개념을 정리하고 풀면서, 스위핑에 대한 이해를 높일 수 있었다. 그림을 보면 뒤로 가야 하는 상황에 대해, 겹치는 선분을 하나로 만들어서 2배하여 더해야 한다. 그럼 뒤로 가는 경우에 대해 선분을 다 만들고, 스위핑 기법을 활용 하면 끝난다. 이렇게 하면 HashMap 과 HashSet을 이용하지 않고, 효율적으로 문제를 풀 수 있다. 공유 소스 보기 (acmicpc.net) 남은 시간에는 오일러 피 함수를 알게 된 김에 폴라드로 알고리즘을 이용하여 푸는 문제를 풀어봤다. 13926번: gcd(n, k) = 1 (acmicpc.net) BaekJoon/gcd（n， k） ＝ 1.py at main · Hy3ons/BaekJoon (github.com) 순간적으로 63 비트를 넘기 때문에, python으로 구현하였다.

제 6회 (4주차)  - 스위핑 알고리즘의 이론적 학습과 구현, 및 백준 응용 문제 풀기 2170번: 선 긋기 (acmicpc.net) 스위핑 알고리즘의 이론적 학습, 및 이해 그리고 응용을 도모한다.

5회차 (3주차) - 트리에서의 다이나믹 프로그래밍 문제 풀어보기 15681번: 트리와 쿼리 (acmicpc.net) BaekJoon/트리.java at main · Hy3ons/BaekJoon (github.com) 생각보다 그리 어렵지 않았다. 남은 시간에는 이분 매칭을 복습하여 풀었다. 11493번: 동전 교환 (acmicpc.net) 흐르고있는 유량의 감소와 증가 유무를 정확하게 판별하고, 최소거리로 흘려버리면 된다. BaekJoon/동전 교환.java at main · Hy3ons/BaekJoon (github.com)

4회차 ( 3주차)  - 트리에서의 다이나믹 프로그래밍 문제 풀어보기      15681번: 트리와 쿼리 (acmicpc.net) 트리에서의 다이나믹을 풀고 접근 방법과, 개념을 학습한다.

4회차  (3주차)  -  그리디 문제 풀어보기  (수정) 최소 버택스 커버에 대해 공부, 응용 문제 풀기 1867번: 돌멩이 제거 (acmicpc.net) 최소 버택스 커버...?     최소 버택스 커버란 그래프와 간선이 있을 때, 간선의 양쪽 노드 중 한개는 적어도 S집합에 있어야 할 때, S집합에 포함 해야 하는 노드를 최소한으로 정하는 것이다.     이 최소 버택스 커버를 찾기 위해서는 최대유량으로 접근하여야 한다. 해당 내용은 쾨닉의 정리에 해당하는데, 아직 이해하지 못했다.          그래프에서 최소 버택스 커버를 찾을려면 일반적인 그래프에서는 다항 시간내에 문제를 해결 할 수 없다. 하지만 이분그래프의 경우라면, 최대 유량 알고리즘을 이용하여, 다항 시간내에 문제를 해결 할 수 있다.     최소 버택스의 개수는 최대 매칭의 개수랑 동일 하다. 이것 또한 쾨닉의 정리의 일부이다. 최소 버택스를 역추적 하여 발견하기 위해서는 증명을 이해해야 하는데, 아직 이해하지 못했다.     위 백준 문제는 단순히 매칭의 개수를 세어보면 되는 간단한 문제였다.      BaekJoon/돌멩이 제거.java at main · Hy3ons/BaekJoon (github.com)           2051번: 최소 버텍스 커버 (acmicpc.net)     최소 버텍스 커버를 구한다... 내가 이해한 최소 버텍스 커버를 구하는 방법이다.      BaekJoon/최소 버텍스 커버.java at main · Hy3ons/BaekJoon (github.com)                 해당 그래프는 최소 벌...

  4회차  (3주차)  -  그리디 문제 풀어보기  (수정) 최소 버택스 커버에 대해 공부, 응용 문제 풀기 1867번: 돌멩이 제거 (acmicpc.net) 최소 버택스 커버 이론에 대해 공부 후, 해당 이론을 응용하는 문제를 풀어 볼 예정이다.

     3주차  (3회차)  - 최소 스패닝 트리에 대한 이론 및, 백준 응용 문제 풀기       1197번: 최소 스패닝 트리 (acmicpc.net) 최소 스패닝 트리란? (최소 신장 트리) 간선에 가중치가 있는 무방향성 그래프가 주어졌을때, 이 그래프에서 가장 적은 가중치로 모든 노드를 가지는 트리를 만드는 문제였다. 처음에는 문제를 이해하지 못해서 고생했다. 하지만 문제를 이해하고 난뒤에는 수월하게 풀렸다. 해당 문제를 푸는 것은 그리디한 방법으로 접근하면 쉽게 풀린다. 간선의 가중치가 적은 것 부터 노드를 이어주는 것이다. 그리고 나중에 가중치가 더 큰 간선으로 이을 려는 두개의 노드가 이미 이어져 있다면, 이을 필요가 없다. 이 과정은 유니온 파인드로 쉽게 할 수 있다. BaekJoon/최소 스패닝 트리.java at main · Hy3ons/BaekJoon (github.com) 이런 최소 스패닝 트리는 가중치를 가장 적게, 혹은 가장 크게 그래프에서 트리를 구성해야 한다는 특징만 안다면 쉽게 응용 할 수 있다. 이번 모각코에서 푼 응용문제들이다. 1922번: 네트워크 연결 (acmicpc.net) BaekJoon/백준/Gold/1922. 네트워크 연결 at main · Hy3ons/BaekJoon (github.com) 1647번: 도시 분할 계획 (acmicpc.net) BaekJoon/도시 분할 계획.java at main · Hy3ons/BaekJoon (github.com) 4386번: 별자리 만들기 (acmicpc.net) BaekJoon/별자리 만들기.java at main · Hy3ons/BaekJoon (github.com) 2887번: 행성 터널 (acmicpc.net) BaekJoon/행성 터널.java at main · Hy3ons/BaekJoon (github.com) p.s 후에 공부를 더하고 알았는데, 내가 한 방법은 크루코살 알고리즘이라고...

  3주차  (3회차)  - 최소 스패닝 트리에 대한 이론 및, 백준 응용 문제 풀기  1197번: 최소 스패닝 트리 (acmicpc.net) 이론의 학습과 더불어, 백준에서 해당 알고리즘을 풀어 볼 예정이다.

2주차 (2회차) - 트리에 대한 학습 및 문제 풀기 4803번: 트리 (acmicpc.net) 트리에 대한 이론적 학습과 더불어 해당 문제를 풀어 볼 예정이다. 해당 문제 풀이에 다른 이론적 학습이 필요하다면, 더불어 공부하며 해결하는 것이 목표이다.

2주차 (2회차) - 트리에 대한 학습 및 문제 풀기 4803번: 트리 (acmicpc.net) 트리란?     그래프에서 사이클이 존재하지 않고, 각 노드의 개수가 N일 때, 간선의 개수가 N-1인 그래프를 말한다.     이런 트리의 특징으로는 계층을 표현 할 수 있고, 앞서 말한 것과 같이 DAG그래프의 한 종류이다.     앞서 모각코 2회차를 진행하기전 포인터를 이용하여, 간단하게 트리를 앞서 구현하였다.      BaekJoon/이진 검색 트리.java at main · Hy3ons/BaekJoon (github.com)      BaekJoon/백준/Silver/11725. 트리의 부모 찾기 at main · Hy3ons/BaekJoon (github.com)      BaekJoon/백준/Silver/1991. 트리 순회 at main · Hy3ons/BaekJoon (github.com)     이제 목표한 위 트리 문제를 풀어 볼 텐데, 앞선 3 문제와는 다르게 처음 구현하는 거라 꽤 힘들었다. 이제 문제를 풀이하기 위한 과정을 나열 하겠다.     1. 해당 문제의 간선은 무 방향성이다. STL 배열로 간선을 표현 할 건데, 쌍방으로 간선을 표현해주어야 한다.     2. 해당 문제를 풀다가, 하나의 노드가 소속된 그래프를 표현하고 싶어 찾다가, UNION-FIND 알고리즘을 발견하여, 공부하였다.     3. 임의의 노드에서 출발하여 BFS탐색을 시도하는데, BFS탐색이 역으로 탐색하는것을 막기 위해, 무슨 노드에서 출발했는지 값을 남겨, 역 탐색을 막도록 하였다. 이때, 이미 방문한 노드에 방문할 경우, 이 그래프를 0 과 UNION하였다.     4. 부모 노드가 0 이 아닌 모든 그래프를 찾아 COUNT후 출력하였다...

1주차 (1회차) - 데이크스트라에 대한 이론 학습 및 코드 구현, 그리고 백준 응용 문제풀기 1504번: 특정한 최단 경로 (acmicpc.net) 데이크 스트라란?     한 노드에서 다른 노드에 가중치가 있을 때, 그 가중치의 합이 가장 적은 길을 찾는 알고리즘 이다. 이런 데이크 스트라는 다이나믹 프로그래밍의 일종인데, 한 노드에서 탐색을 시작하여,  다른 노드로 갈 때, 현재의 최단 거리 값에서 다른 노드로 이동하는 거리의 합이 이전에 그 노드를 방문하여 얻은 최단 거리보다 짧은 경우 업데이트를 하여, 지속적으로 업데이트, 탐색하는 알고리즘이다.          해당 특정한 최단 경로 문제는 데이크 스트라를 돌렸을 때, dp배열의 값, 최단 거리가 무엇을 의미하는지 정확하게 묻는 문제라고 할 수 있다.     해당 문제는 양방향 간선이다. 즉, 특정한 노드에서 다른 노드로 가는 최단 거리는 그 반대여도 값이 같다는 것이다. 그리고 또한 모든 노드는 다른 노드로 가는 간선이 존재한다.     문제는 1에서 N 으로 가는 최단 거리는 우리가 거쳐가야 하는 두개의 노드가 포함 되어 있지 않을 수도 있다는 것이다.     그럼 어떻게 해결 해야 할까?     간단히 축약하여 그린 그림이다.     우리 시작 지점 1번노드 에서 거쳐야 하는 두개의 노드까지의 최단 거리를 구할  수 있다. 그리고 거쳐야 하는 두개의 노드를 시작점으로 다익스트라를 돌리게 되면,  해당 노드에서의 다른 노드까지의 모든 최단거리가 나오게 된다. 그러면 우리는 총 5개의 최단거리로 이루어진 간선을 얻게 되고 사용 할 수 있다.      우린 시작점에서 거쳐야 하는 노드 중 하나를 최단 거리를 이용하여 도착했을 때, 다른 거쳐야 하는 노드까지 현재 노드에서 최단거리를 이용하여 그 노드에...