Ikjo's Technology blog

뱀 채우기? 2차원 배열을 채우는데에는 여러가지 방법들이 존재한다. 예를 들면 '순서대로 채우기', '지그재그 채우기', '빗금 채우기', '달팽이 채우기' 등이 있다. 이러한 2차원 배열 채우기의 다양한 방법들은 알고리즘 문제 풀이 사이트 '코드업'에서 연습해볼 수 있다. 문제집 / 기초5-3. 2차원 배열 www.codeup.kr 참고로 달팽이 채우기 문제에 대한 풀이는 다음 글을 참고해볼 수 있다. [코드업 - 1484] 2차원 배열 달팽이 채우기 4-1 - Java 문제 설명 [기초-배열연습] 2차원 배열 달팽이 채우기 4-1 다음과 같은 n*m 배열 구조를 출력해보자. 입력이 3 4인 경우 다음과 같이 출력한다. 1 2 3 4 10 11 12 5 9 8 7 6 입력이 4 5인 경우는 다음과 같이..

소수를 판별하는 방법들 때때로 알고리즘 문제를 풀다 보면 소수를 찾거나 소수의 개수를 구하는 등 특정 수가 소수인지를 판별해야하는 경우가 종종 발생한다. 여기서 소수란 1과 자기 자신으로 나누어 떨어지는 양의 수를 의미한다. 이때 1은 소수가 아니며 2와 3 그리고 5와 같이 1과 자기 자신으로 나누어 떨어지는 수는 소수이다. 이번 글에서는 특정 수가 주어졌을 때 그 수가 소수인지를 판별하는 방법들을 자바 프로그래밍을 통해 알아보고자 한다. 가장 직관적인 소수 판별 방법 public boolean isPrime(int n) { if (n < 2) { return false; } for (int i = 2; i

자료 구조란? 자료 구조는 기존의 컴퓨터 메모리를 보다 더 효율적으로 사용 및 관리하기 위해 새로 정의하는 구조체로서 컴퓨터 메모리에 정보를 각기 다른 방법으로 저장할 수 있도록 해준다. 대표적으로 배열, 리스트, 해시, 세트 등이 있다. 연결리스트란? 각 인덱스 값이 메모리상 연이어 저장되어있는 정적인(static) 자료구조의 배열과 달리 연결리스트는 동적인(dynamic) 자료구조로 각 노드(Node)들이 메모리상의 여러 군데 나뉘어 있는데, 각 노드에서 자신의 값뿐만 아니라 다음 노드 값의 주소(포인터)도 저장하고 있어 배열과 동일하게 값을 연이어 읽을 수 있다. 이때 마지막 노드는 다음 값이 없으므로 NULL을 다음 값의 주소로 저장한다. 연결리스트의 시간복잡도 크기가 변경될 경우 배열은 메모리 ..

유클리드 호제법이란? 유클리드 호제법은 알고리즘 기초 문제 중 하나인 최대공약수 구하기를 해결하기 위한 방법 중 하나로 적은 연산으로도 최대공약수를 구할 수 있다. 여기서 호제법이란 두 수가 서로를 나누어 원하는 수를 얻는 알고리즘을 나타낸다. 이때 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, "~만큼의 정도로 커지는"의 약자이다.) 빅오는 알고리즘 실행 시간의 상한(최악의 경우)을 나타낸다. 소프트웨..