기록

문제 보기 BFS + 우선순위 큐를 활용하여 구현하였다. 맵이 주어졌을 대, 최단 경로를 구하는 것이 최종 목표이다. 벽을 부술 수 없으면 간단한 BFS 구현 문제이지만 벽을 1개 부술 수 있다는 것이 핵심이었다. (0, 0)에서 중간 지점(4, 4)에 도달하는 방법이 2가지가 있을 때(벽을 부수고 왔을 때, 벽을 부수지 않고 왔을 때) 이 2가지 방법을 동일하게 생각하면 안 된다. 이후에 또 벽을 만나는 경우에 결괏값이 다르기 때문이다. 따라서 벽에 따른 방문 체크를 따로 관리하였다. 우선순위 큐는 거리가 제일 짧은 경로들을 계속적으로 업데이트하여 목표 지점에 도달하기 위해서 사용하였다. 알고리즘 설계는 아래와 같다. 1. (1, 0, 0, 0)를 우선순위 큐에 삽입한다. (거리, 좌표, 벽 플래그) ..

문제 보기 이 문제는 플로이드-워셜 문제이다. 여행이 가능한 지 확인하기 위해서는 모든 경로에 대한 정보가 필요하다. 플로이드-워셜을 사용하면 모든 도시 사이의 거리를 구할 수 있다. 플로이드-워셜 알고리즘은 3중 for문을 통해 쉽게 구현할 수 있다. 플로이드-워셜을 통해서 모든 도시 사이의 거리를 구한 후 여행을 하면서 만약 해당 지점에 도착할 수 없으면 NO를 출력하였다. * 자기 자신에게 여행을 가는 경우도 있다! 코드 if __name__ == "__main__": n = int(input()) # 총 도시의 수 m = int(input()) # 여행 계획에 속한 도시들의 수 graph = [list(map(int, input().split())) for _ in range(n)] move = ..

정의 - 두 집단 간의 평균을 비교하는 통계적 검정 방법입니다. - 단순히 차이의 존재 여부를 떠나 그 정도의 통계적 유의미성까지 검정하는 방법입니다. - 모집단의 평균 등 실제 정보를 모를 때 현재의 데이터만으로 두 집단의 차이에 대해 검정할 수 있는 방법입니다. - 두 집단의 데이터 개수가 비슷하면서 두 데이터가 정규 분포를 보이는 경우에 신뢰도가 높은 검정 방식입니다. T-test 정의를 보고 궁금한 점이 너무 많았습니다. '왜 평균을 비교할까? 통계적 유의미성은 무슨 뜻일까? 현재의 데이터만으로 의미 있는 결과를 도출할 수 있을까? 정규 분포를 보이면 왜 신뢰도가 높을까?' 궁금한 점을 하나씩 해결해 보록 하겠습니다. 왜 평균을 비교할까? 평균을 비교하는 이유는 단순했습니다. 평균은 한 집단을 대..

정의 연속 변수로 측정된 두 변수 간의 선형적 관계를 상관 계수로 표현하는 것입니다. 두 변수 간의 연관된 정도를 나타낼 뿐 인과관계를 설명하는 것은 아닙니다. 순서 선형 관계를 갖는지 파악합니다. 선형 관계를 갖는다면 방향성을 파악합니다. 관계의 크기를 파악합니다. 1. 선형 관계 파악 선형 관계는 산점도를 통해 쉽게 파악할 수 있으며 아래는 iris 데이터의 산점도 그래프입니다. import matplotlib.pyplot as plt import seaborn as sns plt.rcParams['figure.figsize'] = [10, 8] iris = sns.load_dataset('iris') plt.plot('petal_length', 'petal_width', data=iris, line..

문제 보기 이 문제는 그리디(다익스트라) 문제이다. 주유소에서 멈추는 횟수를 최소화하는 문제이다. 현재 위치에서 갈 수 있는 곳 중 연료의 양이 가장 많은 곳을 방문하면 된다. 즉 그리디 방식으로 풀면 된다. 그리디 방식으로 정답을 구하는 것 자체는 어렵지 않았지만 제한 시간을 고려하면서 구현하기는 어려웠다. 시간제한을 해결하기 위해 현재 위치에서 갈 수 있는 곳은 우선순위 큐에 (-비용, 거리) 형태로 우선순위 큐에 삽입하였고, 갈 수 없는 곳은 (거리, -비용) 형태로 삽입하였다. 즉 갈 수 있는 곳은 비용 내림차순으로 정렬된 우선순위 큐이며, 갈 수 없는 곳은 거리 오름차순으로 정렬된 우선순위 큐 형태이다. 갈 수 없는 곳을 (-비용, 거리) 순으로 삽입하면 비용이 높은 곳부터 탐색하지만 (거리, ..

문제 보기 이 문제는 최소 신장 트리(Minimum Spanning Tree) 문제이다. 두 마을로 분리하기 위해서 먼저 최소 신장 트리를 구현하고, 최소 신장 트리를 구성하는 간선 중에 비용이 가장 높은 간선을 제거하였다. 위 과정을 구현하기 위해서 크루스칼 알고리즘을 사용하였다. 1. 입력 받은 간선을 비용을 기준으로 내림차순 정렬을 한다. 2. 비용이 낮은 간선부터 사이클 여부를 확인하고 사이클이 발생하지 않으면 삽입한다. 3. 모든 간선에 대해서 위 과정을 수행한 후 제일 마지막에 삽입한 간선을 제거하였다. 코드 def find_parent(x): if parent[x] != x: parent[x] = find_parent(parent[x]) return parent[x] def union_par..

문제 보기 이 문제는 이진 탐색 혹은 우선순위 큐 문제이다. 수빈이가 외치는 수가 주어졌을 때, 현재까지 입력받은 숫자의 중간값을 계속해서 출력하면 된다. 중간값을 출력하기 위해서는 정렬이 필요하다고 생각하였다. 하지만 숫자를 입력받을 때마다 정렬하면 시간 초과가 발생할 것 같았다. 따라서 수빈이가 외치는 수가 들어오면 이진 탐색을 통해 해당 숫자가 삽입될 위치를 찾고 삽입하는 방식으로 시간을 단축하였다. 알고리즘 동작은 아래와 같다. 1. 숫자를 입력받는다. 2. 이진 탐색을 활용하여 해당 숫자가 삽입될 위치를 찾는다. 3. 숫자를 삽입한다. 4. 현재까지 입력된 숫자의 개수가 짝수인지 홀수인지 파악하고 올바른 위치의 값을 출력한다. 코드 from bisect import bisect_left if _..

문제 보기 이 문제는 구현, 시뮬레이션 문제이다. 구현 문제는 아이디어가 가장 중요하다고 생각한다. 드래곤 커브 문제도 아이디어가 중요했는데 처음에는 잘 보이지 않았다. 하지만 주어진 예제를 직접 그려보면 바로 규칙이 보인다. 아래 값은 주어진 예제를 직접 그려보면서 세대 별로 방향 값을 나타낸 것이다. 0세대: 0 1세대: 0, 1 2세대: 0, 1, 2, 1 3세대: 0, 1, 2, 1, 2, 3, 2, 1 4세대: 0, 1, 2, 1, 2, 3, 2, 1, 2, 3, 0, 3, 2, 3, 2, 1 진하게 표현된 값이 추가된 값인데 특별한 규칙이 있는 것을 발견할 수 있다. 바로 이전 세대 방향 정보를 리버스 순서로 가져와서 1을 더하고 추가하면 된다. 만약 +1 한 값이 4라면 0 값을 추가한다. ..

문제 보기 이 문제는 스택 문제이다. 문자열 압축, 괄호 문제는 대부분 스택 문제라고 생각한다. 이번 문제 또한 스택으로 풀렸다. 문제에서 올바른 출력을 구하는 것은 어렵지 않았으나, 메모리 초과를 해결하는 게 어려웠다. 알고리즘 구현 과정은 아래와 같다. 1. 빈 덱을 선언한다. 2. 입력받은 문자열을 하나씩 읽으면서 '(' 값이 아니면 덱에 삽입한다. 3. 입력받은 값이 '('이라면 덱의 끝부터 하나씩 읽으면서 '('를 찾을 때까지 문자 수를 센다. - 값이 10보다 크면 10을 뺀 값을 더하고, 아니면 1을 더한다. - 문자 수와 '(' 문자 앞에 있는 값을 곱하고 + 10 한 값을 다시 덱에 삽입한다. 4. 최종 길이를 구한다. - 덱에 있는 값을 순차적으로 읽으면서 값이 10보다 크면 10을 뺀..

문제 보기 이 문제는 BFS 문제이다. 어른 상어 문제는 아기 상어, 청소년 상어 문제를 풀었다면 쉽게 구현할 수 있다고 생각한다. 문제의 핵심은 우선순위이다. 만약 다른 두 상어가 동일한 위치에 이동을 하고자 하면 우선순위가 높은 상어만 위치할 수 있다. 상어의 이동을 우선순위가 높은(번호가 낮을수록) 상어부터 시작하였다. 만약 상어가 이동하고자 하는 곳에 이미 다른 상어가 위치해있다면 우선순위가 더 높은 상어가 이미 선점한 상황이므로 이동하고자 하는 상어를 제거하였다. 알고리즘 구현 과정은 아래와 같다. 1. 상어들은 현재 위치에 냄새를 뿌린다. 2. 상어들을 이동시킨다. - 이동하는 과정에서 상어의 삭제가 진행된다. 3. 상어가 지나간 곳 들의 냄새를 1 감소시킨다. - 냄새의 값이 0이 되면 해당..