while (1): study();

문제 한울이가 사는 나라에는 N개의 여행지가 있으며, 각 여행지는 1 ~ N번까지의 번호로 구분됩니다. 또한 임의의 두 여행지 사이에는 두 여행지를 연결하는 도로가 존재할 수 있습니다. 이때, 여행지가 도로로 연결되어 있다면 양방향으로 이동이 가능하다는 의미입니다. 한울이는 하나의 여행 계획을 세운 뒤에 이 여행 계획이 가능한지의 여부를 판단하고자 합니다. 예를 들어 N = 5이고, 다음과 같이 도로의 정보가 주어졌다고 가정합시다. 1번 여행지 - 2번 여행지 1번 여행지 - 4번 여행지 1번 여행지 - 5번 여행지 2번 여행지 - 3번 여행지 2번 여행지 - 4번 여행지 만약 한울이의 여행 계획이 2번 → 3번 → 4번 → 3번이라고 해봅시다. 이 경우 2번 → 3번 → 2번 → 4번 → 2번 → 3번..

위상 정렬 알고리즘은 방향 그래프의 모든 노드들을 방향성에 거스르지 않도록 순서대로 나열하는 정렬 기법을 의미합니다. 기존의 서로소 집합 알고리즘이나, 이를 기반으로 한 크루스칼 알고리즘은 무향 그래프에 대해서 동작했던 것을 생각하면 차이가 있습니다. 예를 들어 '선수과목을 고려한 학습 순서 설정 문제' 등에서 대표적으로 사용될 수 있습니다. 1. 각 노드의 진입차수(indegree)를 저장합니다. 2. 진입차수가 0인 노드부터 시작하여 연결된 노드에 대해 진입차수를 1씩 뺍니다. 3. 다른 노드도 진입차수가 0이 될 경우 2의 동작을 반복합니다. 큐를 사용하여 구현할 경우 위상정렬의 시간복잡도는 O(V+E)입니다. 전체 소스코드는 다음과 같습니다. input1 = '''7 8 1 2 1 5 2 3 2 ..

크루스칼 알고리즘에 대해 이해하기 위해서는 먼저 신장 트리(Spanning Tree)에 대해 이해할 필요가 있습니다. 신장 트리(Spanning Tree) 신장 트리는 하나의 그래프가 있을 때 모든 노드를 포함하는 부분 그래프를 의미합니다. 위의 그림이 직관적으로 신장 트리를 이해하는 데 도움이 되는 것 같습니다. 실제 그래프 관계는 훨씬 복잡하지만, 굵은 실선만 이어도 모든 노드에 대해서 연결할 수 있다는 것이 특징입니다. 크루스칼 알고리즘(Kruskal Algorithm) 크루스칼 알고리즘은 가능한 최소 비용의 신장 트리를 찾아주는 알고리즘입니다. 다음과 같은 순서로 처리됩니다. 1. 모든 간선에 대해 비용순으로 정렬을 수행합니다. 2. 거리가 짧은 간선부터 집합에 포함시킵니다. 3. 단, 사이클이 ..

서로소 집합 알고리즘 서로소 집합이란 공통 원소가 없는 두 집합을 말합니다. 따라서 어떤 그래프가 주어졌을 때 서로소 집합으로 분리하는 일련의 과정을 통해서 집합 간 관계를 파악할 수 있습니다. 이를 수행하는 알고리즘을 서로소 집합 알고리즘이라고 합니다. 서로소 집합 알고리즘은 다음과 같은 순서로 처리됩니다. 1. Union 연산을 통해 서로 연결된 두 A,B를 체크한다. 2. 모든 Union 연산을 처리할 때까지 1번 연산을 반복한다. 3. 루트를 찾기 위해서는 재귀적으로 부모를 거슬러 올라가야 한다. 위와 같이 Union연산과 확인하는 Find연산으로 구성되어 있기 때문에, Union-Find 연산이라고도 합니다. 기본적으로는 다음과 같이 코드로 구현할 수 있습니다. input1 = '''6 4 1 ..

1절. 정규화 1. 제1정규형 더보기 모든 속성은 반드시 하나의 값을 가져야 한다. (다중값, 중복 배제) 2. 제2정규형 더보기 엔터티의 일반속성은 주식별자 전체에 종속적이어야 한다. (부분 종속(Partial Dependency)이 발생해서는 안 된다) * 함수적 종속성(Functional Dependency): 결정자(Determinant)를 기준으로 종속자(Dependent)가 종속됨 3. 제3정규형 더보기 엔터티의 일반속성 간에는 서로 종속적이지 않다. (이행적 종속(Transitive Dependency)가 발생해서는 안 된다) 4. 반정규화와 성능 - 반정규화: 성능을 위해 데이터 중복을 허용 더보기 - 반정규화를 통해 성능이 향상되는 경우: 조인 제거 - 반정규화를 통해 성능이 저하되는 경..

출처: https://arxiv.org/abs/1608.05859 Using the Output Embedding to Improve Language Models We study the topmost weight matrix of neural network language models. We show that this matrix constitutes a valid word embedding. When training language models, we recommend tying the input embedding and this output embedding. We analyze the resulting upd arxiv.org * 하단 포스팅의 후속 포스팅입니다. https://jcy1996.tis..

문제 동빈이는 숨바꼭질을 하면서 술래로부터 잡히지 않도록 숨을 곳을 찾고 있습니다. 동빈이는 1 ~ N번까지의 헛간 중에서 하나를 골라 숨을 수 있으며, 술래는 항상 1번 헛간에서 출발합니다. 전체 맵에는 총 M개의 양방향 통로가 존재하며, 하나의 통로는 서로 다른 두 헛간을 연결합니다. 또한 전체 맵은 항상 어떤 헛간에서 다른 어떤 헛간으로 도달이 가능한 형태로 주어집니다. 동빈이는 1번 헛간으로부터 최단 거리가 가장 먼 헛간이 가장 안전하다고 판단하고 있습니다. 이때 최단 거리의 의미는 지나야 하는 길의 최소 개수를 의미합니다. 동빈이가 숨을 헛간의 번호를 출력하는 프로그램을 작성하세요. 입력 조건 - 첫째 줄에는 N과 M이 주어지며, 공백으로 구분합니다. (2 max_dist: max_dist = ..

1절. 데이터 모델의 이해 1. 모델링의 이해 - 정의 더보기 다양한 현상 → 일정한 표기 - 특징 더보기 추상화, 단순화, 명확화 - 관점 더보기 1) 데이터: What 2) 프로세스: How 3) 상관 2. 데이터 모델의 기본 개념 - 효과 더보기 1) 업무 내용 분석 2) 실제 DB 개발 및 관리 - 기능 더보기 (가명 구문을 다양한 관점에서 표현) 가시화, 명세화, 구조화, 문서화, 다양한 관점, 상세 수준의 표현 방법 3. 데이터 모델링의 중요성 더보기 1) 파급 효과 (Leverage) 데이터 구조 변경은 일종의 위험 요소 2) 복잡한 정보 요구사항의 간결한 표현 (Conciseness) 많은 관계자들이 활용할 수 있도록 정확하고 간결하게 표현 3) 데이터 품질 (Quality) 1) 중복 2..

플로이드-워셜 알고리즘이 전체 노드에 대한 최소거리를 구하는 데 사용된다면, 다익스트라 알고리즘은 특정 노드에 대한 최소거리를 구하는 것에 특화되어 있습니다. 구체적으로는 다음과 같은 과정을 거칩니다. 1. 출발 노드 설정 2. 최단 거리 테이블 초기화 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신 5. 위 과정에서 3~4 반복 수행 아래는 기본적인 방법론을 따라 구현한 소스코드입니다. # n :노드 개수, m : 간선 개수 # start = 시작 노드 INF = int(1e9) graph = [[] for i in range(n + 1)] visited = [False] * (n + 1) distan..

문제 당신은 화성 탐사 기계를 개발하는 프로그래머입니다. 그런데 화성은 에너지 공급원을 찾기가 힘듭니다. 그래서 에너지를 효율적으로 사용하고자 화성 탐사 기계가 출발 지점에서 목표 지점까지 이동할 때 항상 최적의 경로를 찾도록 개발해야 합니다. 화성 탐사 기계가 존재하는 공간은 N x N 크기의 2차원 공간이며, 각각의 칸을 지나기 위한 비용(에너지 소모량)이 존재합니다. 가장 왼쪽 위 칸인 [0][0] 위치에서 가장 오른쪽 아래 칸인 [N - 1][N - 1] 위치로 이동하는 최소 비용을 출력하는 프로그램을 작성하세요. 화성 탐사 기계는 특정한 위치에서 상하좌우 인접한 곳으로 1칸씩 이동할 수 있습니다. 입력 조건 - 첫째 줄에 테스트 케이스의 수 T(1