티스토리

Blog-Shine
검색하기

블로그 홈

Blog-Shine

blogshine.tistory.com/m

샤아이인 님의 블로그입니다.

구독자
43
방명록 방문하기
공지 블로그 이사 완료 모두보기

주요 글 목록

  • [알고리즘] 불확실한 상황을 현명하게 사용하는 코드 이번글은 학교 알고리즘 수업 시간에 Randomized algorithm을 배우면서 느낀 점을 남기는 글입니다. 어떤 알고리즘을 설명한다기보다는, 제가 느낀 점을 남겨보는 글입니다. 1. 불확실한 상황을 이용해 볼 수 없을까? 우리가 코드를 작성할 때 모든 상황이 확실하게 결정된 상황에서만 진행하는 경우는 거의 없다, 어쩌면 이는 코드뿐만 아니라 대부분의 사람들이 하루를 살아가는 자연스러운 방법(?) 중 하나일지도 모른다. 물론 우리는 계획이라는 것을 만든다. 해당 계획을 통하여 시간이 얼마나 걸릴지 예측할 수도 있고, 얼마나 많은 리소스가 필요한지 또한 측정할 수 있다. 하지만 이는 어느 정도의 사전 정보가 있다는 가정 하에 가능할 것이며, 당장 첫 시도를 해야 하거나, 상황 자체가 너무나 불확실하다면.. 공감수 1 댓글수 2 2023. 12. 14.
  • [알고리즘] 최소 공통 조상 LCA(Lowest Common Ancestor) 1. LCA란? LCA(Lowest Common Ancestor)는 주어진 두 노드 a와 b의 최소 공통 조상을 찾는 알고리즘입니다. 예를 들어 다음 그림과 같은 트리가 있다고 했을 때, 12번과 15번 노드의 최소 공통 조상 LCA는 5번 노드가 됩니다. 우선 두 노드의 LCA를 찾는 가장 간단한 O(N)이 걸리 방법으로 2가지 정도가 있다. 2가지에 대하여 간단하게 알아본 후, 이글의 Main 목표인 O(LogN) 안에 해결하는 알고리즘에 대하여 알아보자. 2. O(N) 알고리즘 2-1) 두 Node의 Level을 통일시키는 방식 A와 B의 깊이가 다를 경우 더 깊은 정점의 부모를 따라 하나씩 올라가면서 A와 B의 깊이를 맞춘다. 위의 결과 A와 B가 같다면 A(or B)가 최소 공통조상이다. A !.. 공감수 5 댓글수 6 2023. 12. 8.
  • [알고리즘] HeapSort보다 QuickSort가 더 빠른 이유 1. 왜 HeapSort보다 QuickSort가 현실적으로 더 빠를까? HeapSort와 QuickSort는 대표적으로 O(NlogN)안에 동작하는 정렬알고리즘이다. 하지면 현실성면에서 QuickSort가 더 빠르다는것은 익히 들어 알고있을 것 이다. 왜 그런것 일까? 이에 대하여 알아보자 1-1) 알고리즘의 성능 요인 크게 정렬 알고리즘에서 성능을 미치는 원인은 크게 3가지로 볼 수 있다. 비교 및 스왑을 수행하기 위한 반복자(loop) = 반복자가 어떻게 구현되어있는가의 문제 유효 접근 시간 (지역성) 메모리 소비량 1번의 경우 대부분 시간복잡도를 측정할때 고려하는 요소라, O(NlogN)이라는 표기안에 포함되어있는 개념이다. 따라서 HeapSort와 QuickSort의 차이는 2번인 유효 접근 시간.. 공감수 1 댓글수 0 2023. 10. 13.
  • [알고리즘] 빅오(Big-O)표기법 수학적 이해 1. Big-O를 수학으로 이해하기 이번 코드스쿼드 멘토를 진행하면서, Big-O 표현식에 대한 과제가 있었다. 물론 이에 대한 직관적인 이해까지는 대부분 하게 된다. 하지만, 성장을 원하는 개발자라면 한 번쯤 수학의 관점에서 이해할 수 있어야 된다 생각한다! 그만큼 Bio-O는 중요한 내용이다! 따라서 학생들에게 이를 설명하기 위한 12분 정도의 영상을 하나 만들었는데, 좀 부족하지만... 나름 잘? 설명했다 생각하여 유튜브 영상으로 남겨두었다! https://youtu.be/OF-BsdcFJ8U (3:49, 5:59, 7:52초 에 N제곱 이라 말한 부분 N제로 입니다 ㅎㅎ) 공감수 0 댓글수 0 2022. 11. 10.
  • [알고리즘] L-트로미노 1. 트로미노란? " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 트로미노는 크기가 같은 정사각형 3개를 변끼리 붙여 만든 다각형 이다. 따라서 다음과 같은 모양이 가능하다. 2. 트로미노로 구성된 불완전 보드 증명 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 트로미노중에서 L 모양의 트로미노를 한 변의 길이가 2^n인 정사각형에 배치하는 것이 목표이다. 결론부터 말하자면, L-트로미노는 1x1 한 칸을 제외하고, 한 변의 길이가 2^n인 정사각형을 항상 채울 수 있다. 위 가정의 증명은 다음과 같이 수학적 귀납법으로 가능하다. 1) Base 단계 (n = 1일때) 만약 n = 1 이면 2x2의 불완전 보드는 트로미노 자신이며, 하나의 .. 공감수 0 댓글수 0 2022. 2. 10.
  • [알고리즘] 비트마스크 조합, 부분수열 예전부터 비트마스크 활용하는거 정리 한번 해야지... 해야지 하다 안해서... 이번에 정리해본다. 먼저 부분수열부터 문제를 통하여 알아봅시다. 1. 비트마스크를 활용하여 부분 수열 구하기 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 위 백준 문제를 통하여 설명해보겠습니다. 문제의 예시처럼 5개의 원소가 있다고 해봅시다. -7 -3 -2 5 8 각 원소 하나마다 (포함 or 미포함) 둘중 하나.. 공감수 0 댓글수 0 2022. 1. 21.
  • [알고리즘] next_permutation : 다음 순열 next_permutation (다음 순열 구하기) " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 ▶ 우선 순열의 특징을 먼저 살펴봅시다! A라는 집합의 원소가 [1, 2, 3, 4] 라고 해보자. A의 순열은 다음과 같다. 1 2 3 4 (오름차순) : 첫 순열 1 2 4 3 1 3 2 4 1 3 4 2 ... 2 1 3 4 2 1 4 3 2 3 1 4 2 3 4 1 ... 4 3 2 1 (내림차순) :마지막 순열 오름차순으로 시작했던 순열이, 최종적으로 내림차순으로 배열되어 끝나게 된다. 총 N! 개의 서로 다른 순열이 있다. 1 2 로 시작하는 순열인 1 2 ? ? 의 마지막 순열의(내림차순) 다음 순열을 어떻게 구할까? 1 2 ? ? 의 마지막 순열은 1 2 4 .. 공감수 1 댓글수 0 2022. 1. 21.
  • [알고리즘] Two Pointers Algorithm : 투포인터 알고리즘 Two Pointers Algorithm " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 투 포인터 알고리즘은 기본적으로 1차원 배열상에서 배열을 가리키는 포인터 2개를 이용하는 방법 입니다! (포인터 라고 해서 C의 그 포인터를 사용한다는 것 이 아닌, 배열의 어느 한칸을 가리키는 용도로 사용하는 것을 의미합니다) 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 대표적인 문제로 백준의 2003번이 있습니다. 이 설명을 보기전 문제를 먼.. 공감수 0 댓글수 0 2022. 1. 21.
  • [알고리즘] Sweeping Algorithm : 라인 스위핑 알고리즘 Sweeping Algorithm " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 라인 스위핑 알고리즘은 무엇일까? 사실 개념 자체는 매우 단순하다. 공간이나 직선 상에서 한쪽 시작점을 기준으로 반대편 종료지점 까지 scan하면서 지나가는데, 한 번만 전체 공간을 스캔하면서 마주치는 요소들에 대해 판단기준이 되는 기준 을 적용해 주면 정답이 구해지는 형태입니다. 이처럼 알고리즘의 구조 자체는 간단합니다. 즉, 스위핑 알고리즘 문제들은 정렬된 요소들을 한 번만 순회하며 연산하면 정답이 나오게 구현하게 해야한다. 대표적인 문제로 백준의 선 긋기 문제가 있습니다. 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에.. 공감수 3 댓글수 0 2022. 1. 21.
  • [알고리즘] Counting inversions Counting inversions " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 예를들어 배열A에 1, 2, 3, ... n 의 수가 무작위 순서로 들어있다고 해보자. 이 수들에서 2개의 무작위 수를 생각했을 때, 그 순서 대비 크기가 역전되어 있는 두 수의 쌍이 몇개가 되는지를 구해보자. 예를 들어 A {2, 3, 6, 4, 1, 7}이 있을때, 크기가 역전된 쌍은 (2, 1), (3, 1), (6, 4), (6, 1), (4, 1) 이 있다. 따라서 Inversion 된 쌍의 수는 5개 이다. 이런 Inversion된 쌍의 수를 어떻게 구해야 할까? 직관적으로 떠오르는 직접다 for문 돌면서 확인하는 방식은 O(n^2)이 걸릴것이 눈에 훤하다... 이럴때 Merge.. 공감수 0 댓글수 0 2022. 1. 21.
  • [알고리즘] lower_bound, upper_bound : C++ ⭐ 조건 : 탐색을 진행할 array, vector는 오름차순으로 정렬되어 있어야 한다. lower_bound " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 lower_bound(3)을 진행하고 싶다. 배열 arr의 첫 시작지점 부터 탐색하면서 처음으로 3이 나오는 배열의 위치(Iterator)를 반환한다. 즉, 찾으려는 key 값보다 같거나 큰 숫자가 배열 몇 번째에서 처음 등장하는지 찾기 위한 용도이다. 위치를 반환한다고 한 이유는 lower_bound의 반환형은 Iterator 이기 때문이다. 실제로 몇 번째 인덱스인지 알고 싶다면, 아래 코드와 같이 lower_bound 값에서 배열 첫 번째 주소를 가리키는 배열의 이름을 빼 주면 된다. #include #incl.. 공감수 0 댓글수 0 2022. 1. 21.
  • [알고리즘] 에라토스테네스의 체 : 소수 판별법 에라토스테네스의 체 (Sieve of Eratosthenes) " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이 방식은 지정됨 범위네에서 대량의 소수를 한번에 구할때 유용하다. 예를 들어 121 이하의 소수를 모두 구해야 한다고 해보자. 어떻게 해결해야 할까? 결론부터 말하면 121의 제곱근, 즉 11 이하의 소수 n에 대하여 n의 배수들은 전부 제외시키면 된다. n의 배수라는 말 자체가 소수가 아니다. 아직 이해가 잘 안갈 수 있다. 다시 설명해 보자. 121의 제곱근인 11이하의 수 들을 생각해보자. 일단 2는 소수니 제거하지 않는다. 2를 제외한 모든 2의 배수 4, 6, 8, 10, ..., 120 에 해당되는 수들은 전부 제거하면 된다. 이들은 소수가 아니다. .. 공감수 0 댓글수 0 2022. 1. 21.
  • [알고리즘] 트리의 지름 : Diameter of Tree 트리의 지름 이란? " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 트리의 지름은 두개의 말단노드간의 최장거리를 의미한다. 각각의 정점을 u, v 라고 한다면 이들간의 거리는 d(u, v) 라고 함수로 나타낼 수 있으며, 최장거리(지름)는 이러한 d(u, v) 값들중 최대인 Max d(u, v)라고 할 수 있다. 트리의 지름을 찾는 알고리즘 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 BFS(node) 를 통하여 node로 부터 가장 멀리있는 node를 구한다고 해보자. 이 방식은 greedy 방식에 해당된다. 1. 임의의 시작 정점 s로부터 가장 멀리있는 정점인 u를 BFS(s)로 구한다. (DFS도 가능) 2. 이렇게.. 공감수 1 댓글수 2 2022. 1. 20.
  • [알고리즘] Bipartite Graph : 이분 그래프 이분 그레프 (Bipartite Graph) 란? " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 학교에서 공부할때 필기한 내용을 먼저 보인후, 이를 내가 설명하여 보겠다. 이분 그레프란 정점의 집합을 2개의 독립적인 집합으로 나눌 수 있으며, 나눠진 집합에서는 서로다른 집합 사이에만 간선이 존재하는 그레프를 의미한다. 즉 같은 집합 내부의 정점간에는 간선이 있으면 안된다. 이를 그림으로 표현하면 다음과 같음 그레프를 의미한다. 집합이 오른쪽(V)과 왼쪽(U) 2개의 집합으로 나뉘어 졌다. 간선들의 양끝 정점(u와 v) 또한 서로다른 집합에 포함되어있다. 정점 u는 집합 U에, 정점 v는 집합 V에 포함되어야 하는 것! 추가적으로 그림에는 없지만, 한쪽 집합에 그냥 .. 공감수 0 댓글수 0 2022. 1. 20.
  • [알고리즘] Knapsack Problem Knapsack 알고리즘 이란? " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 도둑이 보석가게에 배낭을 메고 침입했다. 배낭의 최대 용량은 W이며, 이를 초과해서 보석을 담으면 배낭이 터질 것이다. 각 보석들의 무게와 가격은 알고 있다. 배낭이 찢어지지 않는 선에서 가격 합이 최대가 되도록 보석을 담는 방법은? 위와 같은 문제를 해결하는대 사용되는 알고리즘을 대표적으로 Knapsack 알고리즘 이라고 부른다. 이러한 Knapsack 문제는 동적프로그래밍(DP)의 대표적인 문제로, 대부분의 알고리즘 서적에서 확인해볼수 있는 대표 유형이라 할 수 있다. 알고리즘의 분석 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 어떤 문제를 DP로 풀기 .. 공감수 0 댓글수 0 2022. 1. 20.
  • [알고리즘] 조합 알고리즘 조합 알고리즘 같은 경우 자주 사용한다는 글로 정리해두는 것 도 좋을것 같아 글을 작성해본다. 조합이란? " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 간단하게 0, 1, 2, 3, 4, 5 가 있다고 해보자. 이중 숫자 4개를 순서에 상관없이 선택하는 경우는 몇가지가 있는지를 파악하는 것 이다. 순서가 상관없으니, (0, 1, 2, 3) 과 (0, 1, 3, 2)는 같은 경우이다. 이는 DFS를 활용하여 구하면 된다. 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 tree를 그려보면서 생각해 보자. 빨간 선만 따라서 DFS를 진행하면 (0, 1, 2, 3) 이라는 하나의 조합이 나온다. 그다음은 0, 1, 2, 4 또 그다.. 공감수 0 댓글수 0 2022. 1. 20.
  • [알고리즘] 다익스트라, 프림 알고리즘의 차이점 다익스트라 알고리즘과, 프림 알고리즘을 공부하면서 전체적인 틀이 BFS와 유사하지만, 약간의 차이점들이 있음을 느꼈다. 이를 정리겸 블로그에 글을 남겨본다. dist[] or d[] 의 의미 차이 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 통상적으로 두 알고리즘을 설명하는 책 이라면 dist[] 혹은 d[] 배열을 사용하여 알고리즘을 설명한다. 문제는 프림과 다익스트라 모두 dist 배열을 사용하기 때문에 처음 공부하는 입장에서는 같은 의미의 배열인 줄 알고 오해하는 경우가 있기 마련이다. (내가 처음 배울때 그랬다...) 참고로 다음 설명에서 나오는 집합 S는 이미 선택된 정점들의 집합을 의미한다. ▶ Prim 에서의 dist[] 프림 알고리즘에서 각 정점에 기록된.. 공감수 0 댓글수 0 2022. 1. 20.
  • [알고리즘] Union Find 알고리즘 : 경로 압축 기존에도 Union Find 알고리즘을 사용하기는 했지만, 경로 압축을 하고있지 않아 시간이 조금더 걸리는 문제가 있었다. 간단하게 경로압축을 할 수 있는 방법을 배워 글을 써본다. Union & Find " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 기본적인 Union Find 알고리즘의 구성은 다음과 같다. int Find(int num){ if(parent[num] == num) return num; return Find(parent[num]); } void Union(int a, int b){ a = Find(a); b = Find(b); if(a != b) parent[a] = b; } 맨 처음 parent 배열에서 각각은 자기 자신의 번호를 갖고 시작한다. 1.. 공감수 3 댓글수 0 2022. 1. 20.
  • [알고리즘] Red-Black Tree : 레드 블랙 트리 스스로 공부해 본 후, 다시 정리하는 내용의 글 입니다. 틀린부분과 실수가 있다면 지적해주시면 감사하겠습니다. 레드 블랙 트리 또한 binary-search tree(이진탐색트리) 의 일종이다. 기존의 이진탐색트리 같은경우 input이 이미 정렬되있다면 높이가 n이 되버리고, 따라서 시간복잡도 또한 O(n)에 도달하게 된다. 하지만 레드 블랙 트리의 경우 특정 조건을 지키면서 균형잡힌 이진트리가 되기때문에 Search, Insert, Delete 연산을 최악의 경우에도 O(logN) 시간안에 가능하도록 해준다. 이번 포스트의 순서는 다음과 같다. 1) NIL node 의 설명 2) Red-Black tree의 정의 3) Red-Black tree의 높이 4) Left and Right rotation 5.. 공감수 5 댓글수 1 2022. 1. 19.
  • 코딩테스트 효과적인 C++ 코드 작성 팁 해당 본문의 원문의 출처는 Geeks for Geeks 입니다. 이과생이 공부겸 번역한 딱딱한 어투의 글 입니다. 문제가 될시 삭제하겠습니다. Writing C/C++ code efficiently in Competitive programming - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions. www.geeksforgeeks.org 가끔 해외 유튜버들.. 공감수 13 댓글수 0 2022. 1. 19.
  • STL을 사용한 그래프의 구현 : Graph implementation using STL 해당 본문의 원문의 출처는 Geeks for Geeks 입니다. STL을 활용한 Graph 구현방식의 공부에 도움이 될거라 생각합니다. 원문 주소 Graph implementation using STL for competitive programming | Set 1 (DFS of Unweighted and Undirected) - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company intervi.. 공감수 1 댓글수 0 2022. 1. 15.
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

    티스토리는 카카오에서 사랑을 담아 만듭니다.

    © Kakao Corp.