Data Makes Our Future

.#ㅇ 대표적으로 코딩테스트에 나오는 수학.- 정수론(소수, 약수, 배수 등의 관계)- 기하(피타고라스 정리, 점 사이의 거리, 직선의 방정식, 삼각형의 넓이 등)* 기하의 CCW(Counter Clock WIse), Convex Hull, 좌표 기하는 높은 난이도로 코딩테스트보다 대회에서 자주 빈출 .정수론1. 최대공약수/최소공배수2. 에라토스테네스의 체를 사용한 소수3. 거듭제곱의 연산(C, Java 필수 알고리즘) ㅇGCD와 LCMㅇ최대공약수, GCD(Greatest Common Divider)12345678910111213141516171819# 1. 단순한 반복문def gcd_naive(a, b): for i in range(min(a,b), 0, -1): if a % i== 0 and b % ..

#. 문제 https://algospot.com/judge/problem/read/QUADTREE* 이 문제의 저작권은 Algospot에 있습니다. 대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는 여러 기법 중 쿼드 트리(quad tree)란 것이 있습니다. 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에 쿼드 트리라는 이름이 붙었는데, 이의 유명한 사용처 중 하나는 검은 색과 흰 색밖에 없는 흑백 그림을 압축해 표현하는 것입니다. 쿼드 트리는 2N × 2N 크기의 흑백 그림을 다음과 같은 과정을 거쳐 문자열로 압축합니다. - 이 그림의 모든 픽셀이 검은 색일 경우 이 그림의 쿼드 트리 압축 결과는 그림의 크기에 관계없이 b가 됩니다. - 이 그림의 모든 픽셀이 흰 색일 경우..

# Divide & Conquer ## about- 가장 유명한 알고리즘 디자인 패러다임- 분할 정복 패러다임을 차용한 알고리즘들은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산, 각 부분 문제의 답으로부터 전체 문제의 답을 계산- 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머니 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나눔- 일반 재귀 호출은 항상 문제를 한 조각과 나머지로 쪼개는 방식, 분할정복법은 항상 문제를 절반씩으로 나누는 분할 정복 알고리즘출처 : https://kugistory.net/76 ## 구성 요소- 문제를 더 작은 문제로 분할(Divide)- 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합(Merge)- 더이상..

#. 문제 https://algospot.com/judge/problem/read/CLOCKSYNC* 이 문제의 저작권은 Algospot에 있습니다. 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 바꾸고 싶다. 시계의 시간을 조작하는 유일한 방법은 모두 10개 있는 스위치들을 조작하는 것으로, 각 스위치들은 모두 적게는 3개에서 많게는 5개의 시계에 연결되어 있다. 한 스위치를 누를 때마다, 해당 스위치와 연결된 시계들의 시간은 3시간씩 앞으로 움직인다. 스위치들과 그들이 연결된 시계들의 목록은 다음과 같다. 시계들은 맨 윗줄부터, 왼쪽에서 오른쪽으로 순서대로 번호가 매겨졌..

#. 문제 https://algospot.com/judge/problem/read/BOARDCOVER* 이 문제의 저작권은 Algospot에 있습니다. H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 때 블록들은 자유롭게 회전해서 놓을 수 있지만, 서로 겹치거나, 검은 칸을 덮거나, 게임판 밖으로 나가서는 안 됩니다. 위 그림은 한 게임판과 이를 덮는 방법을 보여줍니다. 게임판이 주어질 때 이를 덮는 방법의 수를 계산하는 프로그램을 작성하세요. [ 입력 ]력의 첫 줄에는 테스트 케이스의 수 C (C

#. 문제 https://algospot.com/judge/problem/read/PICNIC#* 이 문제의 저작권은 Algospot에 있습니다. [ 문제 ]안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 합니다. 각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지어줄 수 있는 방법의 수를 계산하는 프로그램을 작성하세요. 짝이 되는 학생들이 일부만 다르더라도 다른 방법이라고 봅니다. 예를 들어 다음 두 가지 방법은 서로 다른 방법입니다..

#. 문제 https://algospot.com/judge/problem/read/BOGGLE* 이 문제의 저작권은 Algospot에 있습니다. 보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인 게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어 단어를 찾아내는 게임입니다. 펜은 상하좌우, 혹은 대각선으로 인접한 칸으로 이동할 수 있으며 글자를 건너뛸 수는 없습니다. 지나간 글자를 다시 지나가는 것은 가능하지만, 펜을 이동하지않고 같은 글자를 여러번 쓸 수는 없습니다. 예를 들어 그림의 (b), (c), (d)는 각각 (a)의 격자에서 PRETTY, GIRL, REPEAT을 찾아낸 결과를 보여줍니다. 보글 게임판과 알고 있는 단어들의..

#. 재귀 호출 ㅇ 재귀 호출(=재귀 함수) recursion(=recursive function) - 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수 - 다양한 알고리즘을 구현하는데 매우 유용하게 사용할 수 있는 도구 - 문제의 특성에 따라 재귀 호출은 코딩을 헐씬 간편하게 해 줄 수 있는 강력한 무기 - 특정 조건을 만족하는 조합을 모두 생성하는 코드를 쉽게 작성 - 완전 탐색을 구현할 때 아주 유용한 도구 ㅇ 완전 탐색으로 해결하기 위해 필요한 과정 1. 완전 탐색은 존재하는 모든 답을 하나씩 검사하므로, 걸리는 시간은 가능한 답의 수가 정확히 비례 - 최대 크기의 입력을 가정했을 때 답의 개수를 계산하고 이들을 모두..