👀 finalfrontier

01) 문제 KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가정하고, 사대의 위치 x1, x2, ..., xM은 x-좌표 값이라고 하자. 각 동물이 사는 위치는 (a1, b1), (a2, b2), ..., (aN, bN)과 같이 x,y-좌표 값으로 표시하자. 동물의 위치를 나타내는 모든 좌표 값은 양의 정수이다. 사냥꾼이 가지고 있는 총의 사정거리가 L이라고 하면, 사냥꾼은 한 사대에서 거리가 L 보다 작거나 같은 위치의 동물들을 잡을 수 있다고 한다. 단, 사대의 위치 xi와 동물의 위치 (aj, bj) 간의 거리는 |xi-aj| + bj로 계산한다. 예를..

01) 문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오. 입/출력 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표..

01) 문제 2차원 평면상에 n개의 점이 주어졌을 때, 이 점들 중 가장 가까운 두 점을 구하는 프로그램을 작성하시오. 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 있다. 예제 입/출력 4 0 0 10 10 0 10 10 0 # output is 10002) 풀이 평면을 분할한다 분할된 평면에서 최소 거리를 찾는다 서로 분할되어 있는 점들 중에서 최소 거리가 될 수 있는 점들만 탐색하여 최소 거리를 갱신한다. 이전 알고리즘 수업에서 분명히 접했던 문제인데도 바로 구현이 떠오르지 않았다. 위와 같은 흐름으로 divide/combine ..

[1629] 곱셈 1) 문제 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. 첫째 줄에 A를 B번 곱한 수를 C로 나눈 나머지를 출력한다. 예제 입/출력 10 11 12 # output is 4 2) 풀이 $\ A^(x+y) = A^x \times A^y$ 임을 이용해 분할 정복으로 풀어야겠다는 생각은 들었는데, 구체적인 구현방법이 떠오르지 않았다. 결국 풀이를 참고했고, 핵심은 모듈러 연산의 성질이라는 점을 알게 되었다. 모듈러 연산의 분배법칙 $(A \pm B), \bmod, C ..

👆 Sound of Sorting 정렬 알고리즘의 분류 Stable Sorting : 중복된 원소의 순서가 정렬된 후에도 유지됨이 보장된다. Unstable Sorting : 중복된 원소의 순서가 정렬된 후에 유지됨이 보장되지 않는다. K1, .., K2, .. 순서인 배열에서 정렬 후 K1, K2 임이 보장되면 stable, K2, K1일 수 있으면 unstable in-place: 내부 정렬, 정렬을 위해 외부 배열이 필요하지 않다. not in-place: 외부 정렬, 정렬을 위해 외부 배열이 필요하다. 🔥 핵심은 **교환/선택/삽입** 이다. 대부분의 정렬 알고리즘은 이 세 가지 개념을 응용한다. 1. O(N^2) 알고리즘 1. 교환 정렬 Exchange Sort for i in range(0, ..

3박 4일 미니프로젝트, 기획부터 완성까지 1. 기획하다 정글에 들어오기 전, 미리미리 많이 놀아두어야겠다는 안일한 마음을 가졌던 덕에 0주차 프로젝트 주제를 전날 새벽에야 급히 고민했었다. 공공데이터포털을 들여다보며 생각보다 여러 가지 데이터를 제공하는 것을 보고, 이를 받아와 대전시 공연문화정보를 모아보고 즐겨찾기하고, 기한이 되면 알림을 받을 수 있는 서비스를 구현해보자는 아이디어를 들고 갔는데, 어찌저찌 조원분들께 잘 어필이 되어(?) 이것으로 주제를 확정하게 되었다. 처음에는 너무 스코프가 좁은 주제인가 (그럴 리 없었다) 걱정했는데, 돌아보니 짧은 기간 개발하기에 적절했던 것 같다. 2. 개발하다 주요기능 세부구현 회원가입 로그인/로그아웃 JWT 인증 방식 구현 공연 조회 인기순, 이름순, 종..

지금까지 나는 마지막 학기 때, 팀 프로젝트를 하게 되었다. 역량에 비해 터무니없이 큰 범위를 잡았고, 협업에도 미숙해 모두가 같은 코드를 작성해 온 적도 있었다. 결국 목표했던 것을 구현하지 못했다는 점에서 프로젝트는 실패했다. 왜 실패했을까? 여러 이유가 있겠지만, 관통하는 문제점은 내가 무엇을 할 수 있는지 인지하지 못했다는 것이다. 내가 할 줄 아는 것을 정확히 알고 있었다면 애초에 프로젝트의 범위를 적절하게 잡았을 것이다. 나의 역량을 확신하지 못하다보니, 다음 미팅까지 뭘 해올 거냐는 팀원의 질문에 애매하게 답하기 일쑤였다. 팀원들의 입장에서는 내가 좀체 믿을 수 없는 사람으로 보였을 것이다. 나는 함께 일할 수 있는, 믿음이 가는 사람이 되고 싶었다. 마지막 학기에 이렇게 큰 오류가 났으니,..

BaekJoon 1007: 벡터 매칭 풀이 방법 집합 P는 n개의 점들의 집합이고, P의 벡터 매칭은 P의 모든 점을 한 번씩 사용하여 만든 벡터의 집합이다. 즉, $P = {(x_1, y_1), (x_2, y_2), \dots , (x_n, y_n)}$ $VM = {(x_i - x_j,\space y_i - y-j)\space|\space 1 \le i, j \le n, i \ne j }$ 따라서 벡터 매칭에 속하는 모든 벡터의 합은 다음과 같이 구할 수 있다. $v_1 = (x_2 - x_1, \space y_2 - y_1)$ $v_2 = (x_4 - x_3, \space y_4 - y_3)$ $ \dots $ $v_{n/2} = (x_n - x_{n-1}, \space y_n - y_{n-1})$ ..

BaekJoon 1005: ACM Craft 풀이 방법 위상 정렬 topological sorting 과 DP를 활용하여 문제를 해결한다. 인접 리스트를 사용해 유향 그래프를 만들고, 진입 간선의 수를 체크하기 위해 degree 배열을 만들어 준다. 정점을 모두 담을 큐도 하나 선언해 준다. from collections import deque time = [0] + list(map(int, input().split())) # time to build result = time.copy() degree = [0] * (N + 1) graph = [[] for _ in range(N+1)] queue = deque([i+1 for i in range(N)]) 먼저, 건물을 짓는 순서 X, Y 가 주어질 때마..

위상 정렬 위상 정렬이란? 위상 정렬 Topological Sorting 이란 방향이 있는 그래프의 정점들을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 즉 한 정점에 도달하기 전 먼저 거쳐야 하는 정점들의 순서가 있는 경우 사용하는 알고리즘이다. 만약 특정 수강과목에 선수과목이 있다면 그 선수과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 대 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다. 정렬의 순서는 방향이 있는 (유향의) 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 즉, 그래프가..