분류 전체보기

[Algorithm][Union Find] 백준 1717 - 집합의 표현

알고리즘 분류 Union Find 시간 복잡도 \( O(N) \) 문제 링크 https://www.acmicpc.net/problem/1717 이번 문제의 알고리즘 종류는 Union Find입니다. 많은 수가 있을 때 특정 수들이 같은 집합인가?라는 물음에 대해 효율적으로 사용할 수 있는 알고리즘입니다. Union Find의 핵심은 "같은 집합이면 같은 루트"입니다. 처음에는 모든 수들이 자기 자신을 루트로 가지고 있도록 초기화를 시켜놓습니다. 하지만 두 수를 merge 한다면 각 수의 루트 값들이 부모, 자식의 관계를 가지게 됩니다. ( 아래 예시를 보면 이해가 가능합니다. ) 그리고 서로 같은 집합임을 알고싶다면 각 숫자들의 최상단 부모, 즉 루트 값을 비교할 수 있습니다. 하지만 이렇게 계속 진행하..

[Algorithm][투 포인터] 백준 1806 - 부분합

알고리즘 분류 투 포인터 시간 복잡도 \( O(N) \) 문제 링크 https://www.acmicpc.net/problem/1806 이번 문제의 알고리즘 종류는 투 포인터입니다. 주어진 배열에서 조건을 만족하는 연속된 수들 중 가장 짧은 길이를 알아야 합니다. 문제의 제목은 부분합이지만 실제로 이 문제를 푸는데 지난번에 다뤘던 부분합 알고리즘이 사용되진 않습니다. 왜냐하면 부분합 알고리즘은 각 지점마다 누적된 합을 구해놓고 특정 구간의 합만 구하면 되지만 이번 문제는 조건을 만족하는 모든 구간을 알아봐야하기 때문입니다. 투 포인터의 핵심은 "배열이 끝날 때까지 크면 줄이고 작으면 늘린다"입니다. 투 포인터는 배열을 처음부터 탐색하게 되는데 특정 구간의 시작점을 나타내는 S와 끝 지점을 나타내는 E가 있..

[Algorithm][BFS] 백준 13549 - 숨바꼭질 3

알고리즘 분류 BFS (너비 우선 탐색) 시간 복잡도 \( O(V + E) \) 문제 링크 https://www.acmicpc.net/problem/13549 해당 문제는 대표적인 BFS 문제입니다. 현재 위치 N에서 목적지 K까지 가는데 가장 최소 시간을 구해야 합니다. 이처럼 탐색을 하는 데 있어 최소 시간을 구하는 문제는 DFS보다는 BFS를 이용해야 시간 초과가 나지 않습니다. BFS의 핵심은 "해당 지점에서 갈 수 있는 곳을 다시 Queue에 넣는다" 입니다. 이때 중복되는 지점을 계속해서 탐색을 한다면 시간 초과가 발생하기 때문에 꼭 잘 체크해서 Queue에 넣어줘야 합니다. BFS 문제는 많이 풀다 보면 비슷한 템플릿이 있다는 것을 알게 됩니다. 템플릿은 보통 아래와 같습니다. 입력 변수들 ..

[Algorithm][부분 합] 백준 11659 - 구간 합 구하기 4

알고리즘 분류 부분 합 시간 복잡도 \( O(n) \) 문제 링크 https://www.acmicpc.net/problem/11659 해당 문제는 부분 합 알고리즘의 가장 기본적인 문제입니다. 부분 합 알고리즘의 핵심은 "처음부터 \( i \)번째까지 원소의 합을 미리 구해놓자"입니다. 그래서 특정 구간의 합을 \( O(1) \)의 시간으로 알아낼 수 있습니다. 단순하게 for문을 이용하여 특정 구간의 합을 구하는 시간은 \( O(n) \)이지만 구간의 합들 중 가장 크거나 작은 값을 알려면 모든 구간의 합을 알아야 합니다. 그래서 결국 시간 복잡도는 \( O(n^2) \)가 됩니다. 이런 문제의 경우 \( N \)의 값은 10만 이상의 값이므로 \( O(n^2) \)의 시간 복잡도에서는 당연히 시간 초..

[Algorithm][위상 정렬] 백준 2252 - 줄 세우기

알고리즘 분류 위상 정렬 시간 복잡도 \( O(V + E) \) 문제 링크 https://www.acmicpc.net/problem/2252 선행되어야 할 인덱스들이 주어지면서 가능한 순서를 답으로 제출하는 위상 정렬의 문제입니다. 입력으로써 특정 인덱스 2개가 주어지면 첫 번째 숫자와 두 번째 숫자는 꼭 지켜야 할 순서입니다. 테스트 케이스 2번을 예시로 든다면 아래 그림처럼 4가 2를 가리키고 3이 1을 기리 키는 구조가 됩니다. 이 두 관계를 제외하고는 각 숫자들은 서로 연관되지 않습니다. 위상 정렬의 핵심은 "간선이 없는 노드를 처리하자" 입니다. 여기서 간선이 없는 노드의 뜻은 "가리킴을 당하지 않는 노드"입니다. 그래서 저의 풀이는 Queue를 사용했고 처리하는 과정에서 간선이 없는 노드가 생..

[Spark] 스파크 완벽 가이드 Chapter 2 - Spark의 동작 방식

이전에 Spark에 대한 내용을 포스팅 했습니다. 하지만 Spark에 대해서 좀 더 깊게 공부하기 위해 최근에 "스파크 완벽 가이드"라는 책을 구매했습니다. 앞으로 이 책의 내용을 공부하면서 요약한 내용을 글로 포스팅 하겠습니다. 해당 게시물은 "스파크 완벽 가이드" 책을 참고하여 저의 지식과 함께 작성하는 글입니다. Spark Application과 다양한 언어 지원 Spark Application은 Driver와 다수의 Executor로 구성됩니다. Driver는 Application의 수행해야하는 Task들의 스케쥴링 및 전반적인 Application의 정보를 관리하기 때문에 핵심 프로스세입니다. Executor는 Driver의 스케쥴링으로 나온 Task들을 실제로 수행하는 프로세스입니다. 그래서 ..

[OS] Process #1 - Program, Process, Thread의 개념 및 차이점

Program 실행 가능한 파일 Process 실행중인 Program Thread Process 내에서 실제로 작업을 수행하는 주체 Computer Science 지식에 대해 공부를 하면서 블로그에서는 처음으로 OS 주제를 다루겠습니다. OS에 대한 CS는 상당히 많지만 그 중 가장 기본적인 Process에 대해 공부하도록 하겠습니다. 우리들은 컴퓨터를 사용하거나 프로그래밍을 공부햐면서 Program, Process, Thread라는 용어를 상당히 많이 접하게 됩니다. 하지만 제대로 공부하지 않는다면 각각에 대한 개념과 차이점을 모른채 무분별하게 사용하게 됩니다. 가장 먼저 각 정의와 개념에 대해 알아보도록 하겠습니다. Program이란? Program을 쉽게 말하자면 "실행 가능한 파일"입니다. 즉 개..

[Spark] Spark structured streaming으로 Kafka topic 받기 #3 - pyspark로 HDFS에 topic data 저장하기

Docker 내가 원하는 환경의 서버를 container라는 개념으로 쉽게 생성 및 삭제할 수 있는 플랫폼. Kafka Publish, Subscribe 모델 구조로 이루어진 분산 메세징 시스템 Spark Streaming Spark API 중 batch와 실시간 streaming이 가능한 Spark API 이전 글에서는 console 창에서 입력하는 값을 topic에 produce 했었습니다. 이번에는 csv 파일을 이용하여 실시간으로 데이터를 전송하는 것처럼 producer를 구현하도록 하겠습니다. 글에서 실습할 전체적인 과정은 아래 이미지와 같습니다. Kafka-1 container가 Producer의 역할로 test1이라는 Kafka topic에 데이터를 보내고 test1 topic에 담겨있는 내..