소수를 판별하는 알고리즘 중에는 굉장히 유명한 에라토스테네스의 체라는 알고리즘이 존재한다. 소수 판별 문제는 대부분 이 알고리즘으로 풀기 때문에 잘 익혀두면 큰 도움이 된다. 오늘 풀어볼 문제인 boj 1929 번 문제다. 💡에라토스테네스의 체란? 배열을 원하는 범위만큼 생성하여 초기화한다. 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다. 이때, 자기 자신은 지우지 않고, 이미 지워진 수인 경우 건너뛴다. 지워지지 않은 테이블이 소수로 판별된 테이블이다. 위 예시는 2의 배수를 모두 지우고, 3의 배수를 지우는 과정이다. 이런 식으로 $N/2$까지 진행하고 남은 테이블을 확인한다. ❓에라토스테네스의 체의 시간복잡도 naive한 방법으로는, 일반적으로 어떤 정수의 소수를 판별할때는 2부터 판..
2023.05.17 - [PS] - [세그먼트 트리] - BOJ_14427 : 수열과 쿼리 [세그먼트 트리] - BOJ_14427 : 수열과 쿼리 ※본 포스팅은 이전 블로그에서 다시 이전해온 글로서 기존 작성일은 23.04.25 입니다. 요즘들어 PS를 하면서 느끼는게, 내가 이전에 공부하고 완전히 이해했던 자료구조 / 알고리즘들이 몇개월 지 kangmanjoo.tistory.com 지난 포스팅에 이어, 다시 한 번 세그먼트 트리로 돌아왔다. 세그먼트 트리는 특정 구간의 합, 곱, 최솟값, 최댓값을 찾을 때 일반적인 배열에서 찾을 때보다 훨씬 빠른 O(logN)의 시간복잡도를 가진다고 하였다. 그렇다면 세그 트리는 무적이고 나는 신인가? 물론 아니다. 세그트리에도 치명적인 단점이 존재하는데, 바로 값의 ..
※본 포스팅은 이전 블로그에서 다시 이전해온 글로서 기존 작성일은 23.04.25 입니다. 요즘들어 PS를 하면서 느끼는게, 내가 이전에 공부하고 완전히 이해했던 자료구조 / 알고리즘들이 몇개월 지나면 기억이 휘발되어 다시 포스팅들을 찾아보고 있는 내 모습이 너무 바보같았다. 그래서 이왕이면 내가 쓴 글을 보고 다시 떠올리자! 하는게 재습득하기도 제일 빠르고 나에게도 도움이 더 될 것같아, 이곳에 정리하기로 결정했다! 오늘 학습한 자료구조는 바로 세그먼트 트리 도대체 세그먼트 트리는 어디에서 활용이 되는 자료구조인가? 가장 대표적으로 활용이 되는 곳은, 바로 구간합을 구할때이다. INDEX 0 1 2 3 4 5 6 7 VALUE 2 1 7 8 5 4 3 1 위와 같은 테이블이 있다고 하자. 이 배열에서 ..
첫 플래티넘 3 솔브다 !! 세그먼트 트리를 활용하는 자료구조 중 재밌는게 없나 찾던 중, 머지 소트 트리라는 이름만 들어도 흥미로운 태그를 찾았다. 심지어 수열과 쿼리 '1' 이라니 안풀 수가 없잖아 ! ❓머지 소트 트리(Merge Sort Tree)란? 일반적인 세그먼트 트리구조란, 해당 구간의 특징 (구간합이든, 최솟값이든.. 등등)을 각 범위를 지칭하는 노드에 저장을 한다. 머지 소트 트리도 마찬가지로, 특정 범위의 value들의 정렬 상태인 배열을 노드에 저장을 하는 구조이다. 사실 세그먼트 트리에 익숙하다면 크게 어렵지 않게 풀 수있다. 이번 문제에서는 개념을 묻는 느낌이라 갱신을 안해서 갱신부분은 고려를 안해보았는데, 이를 다루는 문제들도 풀어보면 좋을 듯싶다. 이 문제에서 한 번 실수했던 ..
2023.05.15 - [PS] - [강한 연결 요소 SCC] - BOJ_2150 : Strongly Connected Component [강한 연결 요소 SCC] - BOJ_2150 : Strongly Connected Component 오늘은 SCC 알고리즘에 대해 공부하였다. 강한 연결요소인 SCC를 구하는 문제였다. 2-sat을 풀기전 사전 준비로 풀었는데, 어려웠다.. 💡SCC 알고리즘이란? scc란 쉽게 말하면 전체 노드 집합 속에서, kangmanjoo.tistory.com 저번 SCC 공부는 사실 이번 2-SAT 풀이를 위해서 진행했었다. 2-SAT 풀이를 보기전, SCC에 대한 기본 지식이 없다면 위 글을 먼저 읽어볼 것. 오늘 풀어볼 문제인, 백준 11280번이다. 일단 2-SAT에 대..
오늘은 SCC 알고리즘에 대해 공부하였다. 강한 연결요소인 SCC를 구하는 문제였다. 2-sat을 풀기전 사전 준비로 풀었는데, 어려웠다.. 💡SCC 알고리즘이란? scc란 쉽게 말하면 전체 노드 집합 속에서, 서로 사이클을 이루는 노드들의 집합이다. 이런 형태의 노드 집합이 있으면 전체 집합을 이렇게 3개의 scc집합 (사이클) 로 나누는 것이다. scc를 구할때는 코사라주 알고리즘과 타잔 알고리즘 두가지 종류가 있는데, 타잔알고리즘이 구현이 어려운 대신 범용성이 넓기에 타잔 알고리즘을 사용해 풀었다. 🐒타잔 알고리즘이란? 타잔 알고리즘이란 SCC를 구하는 기법중 하나로, DFS 탐색을 들어갈 때 나의 부모노드를 기록하면서 가는 것이다. 스택에 방문한 노드들을 넣으면서 DFS를 돌다가 나 자신이 부모노..
2023.05.09 - [PS] - [스프라그 그런디 정리] - BOJ_11868 : 님 게임 2 어제 푼 님 게임2에이어서 님 게임3. 님 게임 2에서는 단순히 xor로 그런디 수를 파악하여 게임의 승패만을 예측하는 것이었다면, 이 문제에서는 승리할 수 있는 경우의 수를 세는 것이 목적이다. 간단한 아이디어로 생각을 해보자. xor를 하였을때, 1이 남는 비트들이 존재할 것이다. 첫번째 예시로 생각을 해보면, $15=1111_2$ $11=1011_2$ $8 = 1000_2$ 이고, 이를 xor하면 $1100_2$ 가 된다. 이때, 1인 비트중 최상위 비트는 $2^3$ 비트에 위치한 1이다. 이 때, 님게임 2에서 증명했듯이 현재 xor을 한 후 1인 최상위 비트를 가진 그런디 수들은, 값이 변경되었을 ..
저번 포스팅에 이어, 이번에도 게임 이론에 대해 공부해보겠다. 2023.05.09 - [PS] - [게임 이론] - BOJ_11062 : 카드 게임 이번에는 boj 11868번을 풀면서 스프라그 그런디 정리에 대해 배워보자. 문제의 아이디어 자체는 길지 않다. 여러개의 돌 무더기가 있고, 두 사람은 돌 무더기중 하나를 선택해, 그 돌무더기에서 하나 이상의 돌을 제거할 수 있다. 그리고 전체 돌 더미에서 마지막 돌을 가져가는 사람이 승리하는 것이 게임 조건이다. 이 문제 역시 게임 이론을 근거로 하기에, 두 사람 모두 최적의 플레이를 한다고 가정한다. 즉, 승자가 정해져 있는것이다. 이 문제에서는 스프라그 그런디 정리라는 알고리즘을 알고 있어야한다. 💡스프라그-그런디 정리란? 게임판의 상태를 각각 하나의 ..