기록공간

유클리드 알고리즘이란? 유클리드 알고리즘은 주어진 두 수 사이에 존재하는 최대공약수(gcd)를 구하는 알고리즘이다. 원리 유클리드 알고리즘은 다음과 같은 원리로 동작한다. 임의의 두 자연수 a, b가 주어진다. (둘 중 큰 값이 b라고 가정한다.) a와 b를 나눈 나머지를 구한다. 이 결과값을 n이라고 한다. (n = a % b) n이 0일때 a가 최대공약수(gcd)가 된다. 만약 n이 0이 아닌 경우, b에 n값을(b = n), a에 b값을(a = b) 넣고 2부터 반복한다. 구현 두가지 방법으로 구현이 가능하다. 반복문을 이용한 구현 int gcd(int a, int b) { int n; // b에 큰 값을 위치시키기 위한 조건문 if(a > b) { int temp = a; a = b; b = te..

해결 방법 특별한 알고리즘을 사용하지 않고 정직하게 푸는 문제였다. 우선 문제를 간단하게 정리해보겠다. 왼쪽 손가락은 '*' 위치에서, 오른쪽 손가락은 '#' 위치에서 시작한다. 키패드를 누르기 위해 손가락은 상하좌우로 1칸씩 움직이며 이동한다. 1, 4, 7 키패드는 왼쪽 손가락이 누른다. 3, 6, 9 키패드는 오른쪽 손가락이 누른다. 2, 5, 8, 0 키패드는 왼쪽과 오른쪽 손가락 중 가장 가까운 거리의 손가락이 누른다. 만약 왼쪽 오른쪽 손가락이 키패드와의 거리가 같다면 손잡이 위치에 따라 결정된다. 우선 손가락에서 키패드까지의 거리를 알기 위해서는 각 키패드의 위치를 지정해 주어야 한다. 위치는 pair를 사용하여 각각 x축 y축으로 사용하였다. 위치를 지정해 주었다면 이제 거리를 구하는 함수..

해결 방법 우선 record에 들어있는 문자열 형태의 원소를 행위, ID, 닉네임 이 세가지로 쪼개줘야 한다. 이때 sstream을 사용하면 편하게 쪼개줄 수 있다. 닉네임은 중복이 되어도 상관없고 ID를 기준으로 구분한다. 때문에 해쉬 테이블 특성을 이용하여 key값으로 id를 사용한다. 해쉬 테이블의 value값은 구조체로 string 타입의 닉네임과 들어왔는지 나갔는지를 검사하는 bool 타입 멤버변수를 가지고 있다. (나간 id는 닉네임 변경이 불가능하기 때문에 들어왔는지 나갔는지를 검사하는 bool값이 필요하다) 찾은 id값이 Enter하는 경우 해쉬 테이블의 특성을 이용하여 그 id를 key값으로 하는 value 구조체에 닉네임을 부여하고 들어왔다는 체크를 한다. 이제 최종적인 닉네임 변경 적..

문제 사각형의 넓이 N이 주어진다. 이 넓이를 만족하는 사각형의 가로, 세로 길이 A, B 길이에서 2 * (A + B)의 값을 perimeter라고 한다. 이 perimeter중 가장 최솟값을 반환하라. 만약 N이 30인 경우 이를 만족하는 사각형의 길이 A, B는 (1, 30), (2, 15), (3, 10), (5, 6)가 있다. 이 중 perimeter가 가장 작은 값음 (5, 6)으로 2 * (5 + 6) = 22이다. 해결 방법 1부터 N까지 N을 나눌때 나누어지는 경우는 넓이를 만족하는 A, B를 구해놓는다. 이 중 perimeter가 가장 최소인 값을 구하면 된다. 하지만 이렇게 하는 경우 O(N) 시간복잡도로 타임아웃이 될것이다. 그러면 제한시간을 만족하는 방법은 무엇이 있을까? 1 ~ ..

문제와 내용은 "프로그래밍 대회에서 배우는 알고리즘 문제해결 전략" 책을 참고하였습니다. 알고리즘 문제 해결 전략 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략, 구종만 지음, 인사이트, ISBN 978-89-6626-054-6 새 소식 책 소개 은 새로운 알고리즘 책입니다. 종이에 적힌 의사코드 book.algospot.com 0번부터 차례대로 번호가 매겨진 n개의 원소 중 네 개를 고르는 모든 경우를 출력하는 코드를 작성해보자. 예를 들어 n = 7이라면 (0, 1, 2, 3), (0, 1, 2, 4), (0, 1, 2, 5), ..., (3, 4, 5, 6)의 모든 경우를 출력하는 것 말이다. 물론 다음과 같은 4중 for문을 써서 이것을 간단하게 할 수 있다. for (int i = 0; i..

한 개체가 여러 분야를 서로 커플링 없이 다룰 수 있게 한다. 플랫포머 게임을 만든다고 해보자. 슈퍼 마리오 게임을 만든다고 하자. 그러면 마리오를 대표하는 클래스를 하나 만들어서 여기에 주인공이 게임에서 하는 모든 것들을 넣는 게 당연하다. 주인공을 조장해야 하니 컨트롤러 입력 값을 읽어 행동으로 바꿔야 한다. 지형이나 발판(플랫폼) 같은 레벨과도 상호작용할 수 있도록 물리 및 충돌 처리도 필요하다. 주인공이 화면에 나와야 하니 애니메이션과 렌더링도 넣어야 한다. 당연한 소리처럼 들린다. 점점 엉망진창이 되어간다는 느낌이 든다. 분야가 다른 코드는 서로 격리해야 한다고 배웠을 것이다. 워드 프로세서를 예로 든다면 인쇄 코드가 문서를 열고 저장하는 코드에 영향을 받으면 안 된다. 게임은 사무용 소프트웨어..

문제 정수 N이 주어진다. 이 N의 약수들의 갯수를 출력하라. N = 24인 경우 24의 약수는 1, 2, 3, 4, 6, 7, 12, 24 이므로 총 8개 이므로, 답은 8이다. 해결 방법 1부터 N까지 나눠지는 값은 약수이다. 이 방법으로 카운트를 세서 출력하면 정답이다. 하지만 이 방법은 시간 복잡도 O(N)으로 만약 N이 int의 최대값(약 21억)으로 주어진다면 시간초과가 난다. 여기서 약수의 갯수를 간단하게 구하는 중요한 사실이 있다. "만약 √(N)이 정수라면 √(N)은 N의 약수이며, 나머지 약수들은 √(N)를 기준으로 앞 뒤로 짝을 이루고 있다."는 것이다. 예를 들어 100의 약수의 갯수를 구한다고 해보자. 100의 약수는 1, 2, 4, 5, 10, 20, 25, 50, 100이다. ..

여타 자료 구조들과는 다르게 파일 시스템의 자료 구조는 안전하게 저장되어야 한다. 즉, 장시간 사용 후에도 유지되어야 하며 전력 손실에도 하드 디스크나 플래시 기반 SSD 장치의 데이터는 손상 없이 유지되어야 한다. 파일 시스템이 가진 가장 큰 어려움은 전력 손실이나 시스템 크래시가 발생하는 상황에서도, 어떻게 안전하게 디스크 상의 내용을 갱신하는가에 대한 문제이다. 전력 손실이나 크래시 때문에 디스크 상의 자료 구조를 안전하게 갱신하는 것은 상당히 까다로운 작업이 된다. 파일 시스템은 크래시일관성(crash-consistency) 이라는 새롭고 흥미로운 문제에 직면하게 된다. 문제를 이해하는 것은 어렵지 않다. 어떠 특징 작업을 위해 디스크 상에서 두 개의 자료 구조 A와 B를 갱신해야 한다고 해 보자..