jundyu 님의 블로그

들어가며누적합(Prefix Sum) 알고리즘에서 더 나아가 구간을 빠르게 업데이트하는 IMOS 기법에 대해 설명하는 글입니다. 누적합 알고리즘에 대해 모르는 경우 아래의 글을 먼저 읽고 오시길 바랍니다. [Algorithm] 누적합(Prefix Sum) 알고리즘 with Java들어가며길이가 100만인 배열에서 특정 구간의 합을 구하는 것은 for문을 사용해서 쉽게 구할 수 있습니다. 하지만 구해야하는 특정 구간이 한 번이 아니라 10만 번인 경우엔 어떻게 구할까요? 이jundyu.tistory.com이번 글에선 차분 배열 자료구조와 누적합 알고리즘을 합친 imos 방법에 대해 설명하겠습니다. 차분 배열(Difference Array)1. 의미차분 배열이란 배열의 특정 구간에 값을 더하거나 뺄 때,..

들어가며최근 대학수학을 복습하면서, 기하 알고리즘 문제를 풀 때 반복적으로 등장하는 개념과 공식을 정리할 필요성을 느꼈습니다.이번 글에서는 기하 알고리즘 문제 해결에 자주 사용되는 핵심 개념들을, 기초적인 내용부터 대학수학 수준까지 정리해보려고 합니다.증명은 생략하고, 수학적 설명과 자바(Java) 코드를 중심으로 설명할 예정입니다.새롭게 공부하며 추가된 내용은 글 하단에 이어서 정리하고, 분량이 많거나 난이도가 높은 주제는 별도의 글로 분리해서 링크를 적어놓겠습니다. 피타고라스 정리(Pythagorean theorem)1. 의미직각삼각형에서 빗변과 나머지 두 변에 대한 관계를 나타낸 식입니다.서로 직각을 이루는 두 변의 길이가 a, b이고 빗변의 길이가 c일 때 아래의 관계를 가집니다.$$a^2+..

들어가며볼록 껍질을 구하는 그레이엄 스캔 알고리즘을 알기 위해선 CCW 알고리즘을 먼저 배워야합니다. CCW 알고리즘에 대해 자세히 설명해둔 글이 있으니 아래 링크 참고해주세요. [Algorithm] CCW 알고리즘 with JAVA들어가며최근에 기하와 관련된 문제를 풀며 점들이 이루는 방향성을 판별하는 알고리즘을 배우게 되었습니다. CCW 알고리즘은 세 점이 이루는 방향을 간단한 연산으로 확인할 수 있는 핵심 알고jundyu.tistory.com 볼록 껍질: Convex Hull1. 볼록한 다각형(Convex Polygon) 왼쪽 도형을 바깥에서 바라봤을 때 기준으로 모든 꼭짓점들이 볼록합니다. 하지만 오른쪽 도형은 빨간색으로 표시된 하나의 꼭짓점이 오목한 것을 볼 수 있습니다. 이렇게 모든 꼭짓점..

들어가며우리가 일상적으로 사용하는 수식은 대부분 중위 표기법(Infix Notation)입니다. 그러나 수식을 표현하는 방법에는 전위 표기법(Prefix Notation), 후위 표기법(Postfix Notation)도 존재합니다. 이번 글에서는 각각의 표기법에 대해 간단히 알아본 뒤 후위 표기법을 왜 사용해야하는 지와 중위 표기법을 후위 표기법으로 어떻게 변환하는 지에 대해 다뤄보겠습니다. 글의 마지막에 표기법끼리 변환하는 방법도 있으니 참고해주세요. 수식 표기법우선 수식 표기법에 대해 간단히 알아보고 지나가겠습니다. 수식 표기법은 총 3가지로 분류됩니다.전위 표기법 : Prefix Notaion(PN = Polish Notation)중위 표기법 : Infix Notaion후위 표기법 : Postfi..

들어가며길이가 100만인 배열에서 특정 구간의 합을 구하는 것은 for문을 사용해서 쉽게 구할 수 있습니다. 하지만 구해야하는 특정 구간이 한 번이 아니라 10만 번인 경우엔 어떻게 구할까요? 이번 글에서 알아볼 알고리즘은 누적합이라는 알고리즘입니다. 누적합: Prefix Sum1. 개요배열에서 특정 구간의 합을 반복적으로 구해야 하는 문제가 코딩 테스트에서 자주 등장합니다. 단순하게 매번 특정 구간을 순회하면 시간이 너무 오래걸리기 때문에 이를 개선하기 위해 누적합 기법이 고안되었습니다.누적합은 한 번의 배열 전체 순회를 통해 배열의 합 정보를 저장해두고, 이후 각각의 구간합 요청에 대해 빠르게 응답할 수 있습니다. 2. 시간복잡도원본 배열의 길이가 N일 때, 인덱스 0부터 N-1까지 한번씩의 연산이..

들어가며처음으로 수학과 관련된 알고리즘을 다뤄보게 되었습니다. 사실 정확히 말하자면 오일러 피 함수는 알고리즘이라기보단 정수론에서 배우는 수학 개념입니다. 의미는 단순하지만 증명은 어렵고 복잡하기 때문에 함수를 외운 뒤 구현하는 법만 이해하면 충분합니다. 오일러 피 함수 : Euler Phi Function1. 정의오일러 피 함수는 자연수 n이 주어졌을 때 n 이하의 자연수 중에 n과 서로소인 수의 개수를 구하는 데 사용됩니다. 2. 표기$$\Large \phi(n)$$함수의 표기는 위와 같고 피(phi)라고 읽습니다. $\phi(6)$이라면 6 이하의 자연수 중 6과 서로소인 자연수는 1, 5가 있으므로 2를 값으로 가집니다. 3. 수식$$\large\phi(x)=n\prod_{p|n}(1-\frac..

들어가며이번 글은 최소 신장 트리를 구하는 알고리즘 중 하나인 Prim에 대해 설명하는 글입니다. 글을 읽기 전에 아래의 링크에서 그래프 이론 및 그래프 탐색 글을 읽어보는 것을 추천합니다. [Algorithm] 그래프 이론 및 그래프 탐색들어가며그래프는 제가 가장 좋아하는 알고리즘 분류입니다! 그래프 이론을 배우고 나면 단순한 자료 구조를 넘어서, 너비 우선 탐색, 깊이 우선 탐색, 최단 경로 탐색, 교착상태 판별 등 다양한jundyu.tistory.com Prim 알고리즘을 설명하기 전에 최소 신장 트리에 대해 간략하게 설명하면서 시작하겠습니다. 최소 신장 트리 (MST : Minimum Spanning Tree)1. 정의우선 트리(Tree)의 사전적 정의는 사이클이 없고, 모든 정점이 연결된 무방..

들어가며제목에서 알 수 있듯이 이번 글은 위상 정렬을 위한 Kahn's 알고리즘에 대한 글입니다. 그래프와 관련된 알고리즘이므로 아래의 그래프 이론과 해당 글에 연계된 그래프 탐색 알고리즘 글들을 먼저 읽어보면 이해하기 쉽습니다. [Algorithm] 그래프 이론 및 그래프 탐색들어가며그래프는 제가 가장 좋아하는 알고리즘 분류입니다! 그래프 이론을 배우고 나면 단순한 자료 구조를 넘어서, 너비 우선 탐색, 깊이 우선 탐색, 최단 경로 탐색, 교착상태 판별 등 다양한jundyu.tistory.com 위상 정렬 : Topological Sort1. 개념위상 정렬이란 유향 그래프의 정점들을 변의 방향을 거스르지 않도록 나열하는 것입니다. 사전적 의미로는 어려울 수 있는데, 쉽게 말하면 해야할 일의 순서를..

들어가며이번 글은 벨만 포드 알고리즘에 관한 포스팅입니다. 만약 그래프 이론이나 다른 그래프 탐색 알고리즘들을 모른다면 먼저 읽어보고 오는 것을 추천합니다. 아래의 링크에 그래프 이론 및 탐색에 관한 내용이 잘 나와있습니다. [Algorithm] 그래프 이론 및 그래프 탐색들어가며그래프는 제가 가장 좋아하는 알고리즘 분류입니다! 그래프 이론을 배우고 나면 단순한 자료 구조를 넘어서, 너비 우선 탐색, 깊이 우선 탐색, 최단 경로 탐색, 교착상태 판별 등 다양한jundyu.tistory.com Bellman-Ford : 벨만 포드1. 알고리즘 명칭Bellman-Ford라는 알고리즘의 명칭은 "Richard Bellman"와 "Lester Ford Jr."이라는 수학자의 이름에서 유래되었습니다. 벨만 포..

들어가며이번 글은 그래프 탐색에 관한 글로 읽기 전에 아래의 링크에서 그래프 이론을 숙지하고, 너비 우선 탐색 및 데이크스트라 알고리즘을 먼저 익히고 나면 정말 쉽게 배울 수 있습니다. [Algorithm] 그래프 이론 및 그래프 탐색들어가며그래프는 제가 가장 좋아하는 알고리즘 분류입니다! 그래프 이론을 배우고 나면 단순한 자료 구조를 넘어서, 너비 우선 탐색, 깊이 우선 탐색, 최단 경로 탐색, 교착상태 판별 등 다양한jundyu.tistory.com [Algorithm] BFS 알고리즘 with JAVA들어가며BFS 알고리즘을 공부하기에 앞서 그래프 이론을 먼저 공부하면 이 글을 이해하는 데 더 도움이 될 것 같습니다! 아래의 링크에 그래프 이론에 관한 개념이 잘 정리되어 있습니다. [Algorith..