Ikjo's Technology blog

유클리드 호제법이란? 유클리드 호제법은 알고리즘 기초 문제 중 하나인 최대공약수 구하기를 해결하기 위한 방법 중 하나로 적은 연산으로도 최대공약수를 구할 수 있다. 여기서 호제법이란 두 수가 서로를 나누어 원하는 수를 얻는 알고리즘을 나타낸다. 이때 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 예를 들어, 99와 57의 최대공약수를 유클리드 호제법을 이용하여 구한다면, 다음과 같다. 99 % 57 = 42 → 나머지(42) != 0 57 % 42 = 15 → 나머지(15) != 0 42 % 15 = 12 → 나머지(12) != 0 15 % 12 = 3 → 나머지(3) != 0 12 % 3 = 0 → 나머지(0)..

알고리즘의 시간 복잡도란? 알고리즘의 시간 복잡도는 특정 입력(n)에 대해 알고리즘이 얼마나 오래 걸리는지를 의미한다. 즉, 해당 알고리즘으로 어떤 기능을 수행하는데, 필요한 연산의 횟수로 볼 수 있다. 따라서 동일한 기능을 수행하며 동일한 메모리를 소요하는 알고리즘이 두 개가 있을 때 시간 복잡도가 더 낮은 알고리즘이 '더 나은' 알고리즘이라고 볼 수 있다. 이때 메모리를 더 많이 사용함으로써 시간을 줄이는 메모이제이션(Memoization) 기법도 존재한다. 빅오 표기법 이러한 알고리즘의 시간복잡도를 표현할 때는 빅오(Big-O) 표기법을 사용한다. (이때 O는 on the order of, "~만큼의 정도로 커지는"의 약자이다.) 빅오는 알고리즘 실행 시간의 상한(최악의 경우)을 나타낸다. 소프트웨..

문제 설명 [기초-배열연습] 2차원 배열 달팽이 채우기 4-1 다음과 같은 n*m 배열 구조를 출력해보자. 입력이 3 4인 경우 다음과 같이 출력한다. 1 2 3 4 10 11 12 5 9 8 7 6 입력이 4 5인 경우는 다음과 같이 출력한다. 1 2 3 4 5 14 15 16 17 6 13 20 19 18 7 12 11 10 9 8 입력이 www.codeup.kr 접근 방법 해당 문제는 행렬(2차원 배열) 상 첫번째 위치(인덱스 0, 0)에서 중심 부근까지 시계방향으로 회전하면서 각각의 행렬 값을 1씩 증가시키는데, 이를 4개의 방향에 대한 규칙성을 정의함으로써 해결할 수 있었다. 이때 행렬을 채우는 각각의 숫자는 N(행의 개수) X M(열의 개수) 행렬을 기준으로 1부터 N+M까지이므로 1~N+M의..

문제 설명 기억력 테스트 2 첫째줄에 N이 입력된다. (1

문제 설명 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) www.acmicpc.net 접근 방법 수학적으로 공식을 세워 푼 문제로 다소 직관적이진 않지만 한번의 연산으로 아주 빠른 시간 내 정답을 도출할 수 있는 방식을 도출했습니다. (많은 문제들을 이런 식으로 공식을 세워 풀고 싶지만 이런 공식은 바로바로 세워지지 않네요.. 😅) 우선 공식을 세우기 위한 규칙성을 찾기 위해 A와 B 값은 그대로 두고 V값을 1씩 증가시켜보았습니다. A = 5, B = 1, V = 5인 경우입니다. A B V Day 5 1 5 1 5 1 6 2 5 1 7 2 5 1 8 2 5 1 9 2 5 1 10 3 위 표..