Algorithm

Prob - Category : Coding - Score : 250 Challenge - 이 문제는 문제설명에도 적혀있다시피 base64로 encode된 x64 machine code를 11개 정도 준다. 이 machine code를 1개를 실행시키던, 전부 실행시키던, 순서를 뒤죽박죽 시키던 정상적으로 실행이 되는 순서조합의 machine code를 보내면 stage를 통과하는 그런 류의 문제이다.(실제로는 주어진 machine code를 모두 사용하는 경우밖에 보지 못한 것 같다.) Solution- 11개라고 가정했을 때, 모든 permutation을 검증을 하기에는 stage한개에 대한 최적의 실행순서를 찾는데도 오랜 시간이 걸린다. - 따라서 해당 순서에 실행이 되는 machine code가 ..

보호되어 있는 글입니다.

보호되어 있는 글입니다.

보호되어 있는 글입니다.

★내가 푼 방식우선 행렬이 어떤식으로 확장되는지 살펴보았다.4구역으로 나눈다고 가정했을때 1,3사분면은 2사분면을 복사하고, 4사분면은 2사분면의 역(0이면 1, 1이면 0)을 복사하는걸 볼수있었다.배열의 크기가 1024기때문에 1024 -> 512 -> 256 -> ~ 1이 나올때까지 재귀적으로 호출하고,1이나오면 다시 1 -> 2 -> 4 -> 8 -> 16 -> 32 ~ -> 1024까지 1,3사분면은 복사, 4사분면은 역을 복사하는 코드를 짯다. ★풀이 코드★ [출처] Matrix|작성자 튜기

★내가 푼 방식우선 어떻게 이 사각형의 수들을 구할지 생각을 했다. 사각형의 크기가 0이거나 한변의길이^2 일때 두가지 경우이외에는 사각형을 잘라야 하는 케이스임을 알아냈고 이를 코드로 짜는건 어렵지 않았다. 이문제는 분할정복법을 이용하여 풀었다.우선 행렬의 가로인덱스, 세로인덱스를 함수에 넘겨주고 그 인덱스를 기준으로 1,2,3,4사분면 을 각각 계산하여 더하였다.그리고 각각의 사분면이 같은 숫자만 포함하고 있는지 확인하고(위의 두가지경우) 모두 같은수면 1을 반환하고, 다른숫자가 포함되있으면 다시 그 사분면을 4개로 나누어 계산하도록 재귀적으로 코드를 짯다. ★풀이 코드★ [출처] Cut Paper|작성자 튜기

xor연산(^)을 이용해서 추가적인 메모리 없이 값을 서로 swap할수 있다.보통 하나의 변수를 주고하는데 이방법은 변수를 임시로 선언할 필요가 없다. 코드 결과 출처 : Dovelet[출처] xor이용해서 swap하기|작성자 튜기

★내가 푼 방식우선 어떤식으로 Output이 정해지는지 일일이 계산을 해보았다.일단 처음에 1이써지고 그다음수(A)는 이전의 수와 다른 숫자중에 가장작은수로 가정한다.그다음 이전에 써진 수들과 비교를 한다. 만약 지금 구하고있는 수가 k번째이면 비교방식은 바로앞의수와 1개씩(k와 k-1),2개씩(k,k-1와 k-3,k-2) .... 지금까지의 문자열의 길이 / 2개 만큼 비교를한다. 만약에 같은 문자열이 존재하면 가정했던수를 +1 시키고(A+1), 존재하지 않으면 다음문자(k+1번째)를 위와 같은 방법으로 구한다.같은 문자열이 계속해서 존재해서 A가 K보다 커지면 K-1번째수를 +1시키고 K-1번째부터 다시 조사한다.BackTracking느낌으로 A가 K보다 커지면 다시 뒤에수를 구하다가 처음까지 갔는데..

나머지공식을 이용해서 a와 b의 최대공약수를 구하는 코드알고리즘 풀때 한번씩 사용하는 함수 두 정수 a, b의 최대공약수를 g, 최소공배수를 l 이라고 하면 다음이 성립한다. (1) a = ga′, b = gb′ (단, a′, b′는 서로소) (2) l = ga′b′ (3) lg = ab (4) a = ga′, b = gb′ 일 때 a ± b′ = g(a′ ± b′) (5) 두 정수 a, b의 모든 공약수는 g의 약수이다. (6) 두 정수 a, b의 모든 공배수는 l의 배수이다. 위 성질을 이용해서 최소공배수도 쉽게 구할 수 있다. [출처] 최대공약수 구하기|작성자 튜기

재귀호출, 백트래킹그리디다이나믹 (Dynamic Programming)기하 알고리즘 - 내부-외부 판별 - 단순 닫힌 경로 - Convex Hull (Graham Scan 또는 Jarvis March. 전자를 추천) - 선분의 교차 - 벡터 외적 (벡터곱) - Rotating Calipers (꼭 알 필요는 없지만, 알아두면 좋습니다)문자열 & 오토마타 & 구조 - KMP (Knuth-Morris-Pratt) 스트링 매칭 - Boyer Moore 스트링 매칭 - 유한 오토마타 (Finite Automata) - Trie 구조 (이것은 꼭 알 필요는 없습니다)수학 & 정수론 부분 - 유클리드 호제법 - 에라스토테네스의 체 - 페르마 소정리 - Totient Function (오일러 함수를 말합니다) - S..

해싱함수 : 키 값을 원소의 위치로 변환하는 함수해시 테이블 : 해싱 함수에 의해 계산된 주소의 위치에 항목을 저장한 테이블┗N개의 버킷, m개의 슬롯으로 구성 -거의 사용하지 않는 키 값도 있기 때문에 키값의 수만큼 많은 버킷을 만들면 메모리 낭비이다.그래서 버킷의 수를 줄이고 같은 버킷안에 여러 개의 슬롯을 두어서 해싱함수로 만든 주소가 같으면 같은버킷에 저장한다. Collision키값이 서로 다른데 버킷주소가 같은 경우 -> 비어있는 슬롯도 없을경우 => 오버플로우 발생 , 해싱함수- 계산이 쉬워야함- 충돌이 적어야 한다.- 골고루 분포할 수 있게 만들어야함 1)중간 제곱 함수제곱한 값의 중간 비트들은 키의 모든값과 관련이 있기 때문에 서로다른 값을 갖는다.주소로 사용하는 비트수는 해시테이블의 버킷..

주어진 문제를 분할하여 해결하는 방법을 말한다. 즉, 한 번에 해결하기 어려운 문제를 작은 단위의 부문제들(subproblems)로 쪼개어 해결하는 방법이다. 일반적인 재귀적 해법과 분할정복법의 차이-문제를 한 조각과 나머지부분으로 나누는 것이 아니라, 거의 균등한 크기의 부분 문제로 나눈다는 점이다. ★분할정복 알고리즘에는 보통 다음과 같은 세 가지 과정이 있다.① 문제를 더 작은 문제(부문제)로 분할 (Divide)② 각 부문제에서 구한 답을 분할하기 전의 원래 문제에 대한 답이 되도록 합병하는 과정 (Merge)③ 더 이상 쪼갤 필요가 없거나 쪼갤 수 없는 문제에 대해 답을 구하는 과정 (Base case) ★ 분할정복법을 적용할 필요성이 있는지 알아보려면 다음의 두 가지 조건을 검사해보면 된다.①..