기록공간

해결 방법 최대공약수(gcd)는 유클리드 알고리즘을 사용하여 풀었다. 유클리드 알고리즘 (gcd, 최대공약수) 유클리드 알고리즘이란? 유클리드 알고리즘은 주어진 두 수 사이에 존재하는 최대공약수(gcd)를 구하는 알고리즘이다. 원리 유클리드 알고리즘은 다음과 같은 원리로 동작한다. 임의의 두 자연�� lipcoder.tistory.com 최소공배수(lcm)는 두 수의 배수 중에서 가장 작은 값 이므로, 두 수를 곱한 부분에 최대 공약수를 나누어 준 값이 최소공배수가 된다. 코드 구현은 다음과 같다. class Solution { private int gcd(int a, int b) { int c; while(b != 0) { c = a % b; a = b; b = c; } return a; } priva..

유클리드 알고리즘이란? 유클리드 알고리즘은 주어진 두 수 사이에 존재하는 최대공약수(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이다. ..

문제 비어있지 않은 배열 N개의 정수를 담는 A가 주어진다. 0