분류 전체보기(69)
-
[알고리즘] 다이아몬드 만들기
2차원 배열에서 다이아몬드 형태로 데이터가 들어가는 것을 말합니다. 이러한 2차원 배열은 특징이 있는데요. 센터값을 기준으로 대칭이 일어나는 규칙을 갖고 있습니다. 형태는 다이아몬드뿐만 아니라 다양할 수 있는데요. 아래의 다이아몬드 형태의 예시에서는 행이 고정된 상태에서 열이 변화하면서 데이터가 들어가는 걸 알 수 있습니다. 행마다 데이터가 들어간 자리는 이와 같습니다. 보면 일정한 규칙이 있는데요. 행이 증가하면서 열의 시작값은 -1, 끝값은 +1씩 변화하다 가운데를 기준으로 반대부터는 시작값이 +1, 끝값은 -1씩 변화하는 걸 알 수 있습니다. 이를 활용한 알고리즘 문제의 순서도를 알아보겠습니다. 5행 5열의 2차원 배열에 다음과 같은 순서로 값이 저장될 때의 순서도입니다. 행에서의 반복 1, 5, ..
2021.10.07 -
[알고리즘] ㄹ자 채우기
ㄹ자 채우기 2차원 배열에 ㄹ자 방향으로 데이터가 들어가는 방식입니다. 행이 고정된 상태에서 열이 변화하면서 데이터가 들어간 형태로 방향은 아래와 같습니다. 첫 행은 1열부터 5열까지 1씩 증가하는 형태, 다음 행은 5열 부터 1열까지 1씩 감소하는 형태가 반복됩니다. 이 때 열의 시작값, 끝값, 증가값이 바뀌기 때문에 상수 처리를 할 수 없어 변수로 처리를 해야 합니다. 변화하는 값을 확인해보니 일정한 패턴이 보이는데요. 첫 행의 시작값은 다음 행의 끝값으로, 첫 행의 끝값은 다음 행의 시작값으로, 첫 행의 증가값에서 -1을 곱한 값이 다음 행의 증가값으로 반복되는 걸 알 수 있습니다. 교환로직 일반적으로 A, B라는 두 저장공간이 있을 때 A값과 B값을 서로 바꿀 때 A값을 B값으로 옮기면 기존의 B..
2021.10.06 -
[알고리즘] 최대공약수, 최소공배수, 유클리드 호제법
최대공약수(GCD) ex) 8와 12의 최대공약수 더 이상 나누어 떨어지는 값이 없는 서로소 상태일 때 종료되고 나눈 값을 모두 곱하면 최대공약수가 나옵니다. 최소공배수(LCM) ex) 8와 12의 최소공배수 구하려는 두 수를 곱한 값에서 최대공약수를 나누면 최소공배수가 나옵니다. 유클리드 호제법 최대공약수를 구하는 방법으로 구하려는 두 수를 비교해서 큰 수에서 작은 수를 0이 나올 때까지 빼나갑니다. ex) 8과 12의 최대공약수
2021.10.04 -
[알고리즘] 약수, 완전수, 부족수, 과잉수
약수 어떤 수로 정수가 나누어 떨어지는 수 ex) 8의 약수는 1, 2, 4, 8 완전수 자신을 제외한 약수의 합 = 자신 ex) 6의 약수는 1, 2, 3, 6 6을 제외한 수를 더하면 (1+2+3=6) 6으로 자신과 값이 같음 부족수 자신을 제외한 약수의 합 자신 ex) 20의 약수는 1, 2, 4, 5, 10, 20 20을 제외한 수를 더하면 (1+2+4+5+10=22) 22로 자신보다 값이 큼
2021.10.01 -
[알고리즘] 이진 검색(Binary Search)
이진 검색 찾을 데이터를 반씩 나눠가면서 원하는 데이터를 찾는 방식입니다. 아래는 1번지부터 10번지까지 데이터가 저장되어 있는 일차원 배열입니다. 만약 변수 key에 5를 받았다면 배열 안에 저장된 데이터에 5가 있는지 찾고 그 주소를 출력하는 것입니다. 원하는 데이터가 배열 안의 몇 번지에 위치하는지 찾는 방식인데요. 이진 검색은 처음에 말했다시피 찾을 데이터를 반씩 나눠가는데요. 전제조건으로 데이터가 오름차순이나 내림차순으로 정렬되어 있어야 이진 검색을 사용할 수 있습니다. 검색 방법은 먼저 배열 중 가운데 값을 찾습니다. 위의 배열에서는 (5) 번지가 되겠네요. 이 (5) 번지의 데이터 7 과 찾을 key 값을 비교합니다. 값을 비교해보니 찾을 값이 (5) 번지의 데이터 보다 작습니다. 그렇다면 ..
2021.09.30 -
[알고리즘] 대각선 채우기
대각선 채우기 5행 5열의 배열이 존재할 때 아래와 같은 형식으로 데이터가 들어가는 것을 말합니다. 데이터가 들어가는 순서는 대각선 방향이며 총 9회전 되는 형식인데요. 이렇게 2차원 배열이 나오게 되면 데이터가 들어가는 순서의 규칙을 찾아야 하는데 규칙을 찿기 위해서 데이터의 주소값을 살펴보겠습니다. 여기서 규칙을 찾을 수 있는데요. 회전 마다 주소값의 행과 열을 더한 값이 같은 걸 볼 수 있습니다. 여기서 또 하나 알 수 있는 건 만약 행이 변수처리 되어 있다면 역으로 더한 값에서 행을 빼는 방식으로 열을 구할 수 있다는 겁니다.
2021.09.29