주어진 2차원 배열을 다양한 형태로 사용하는 것을 연습해보자. 기본 배열연습에서 사용할 배열의 기본 형태는 아래와 같이 [4*5]의 char 배열이다.[A, B, C, D, E][F, G, H, I, J][K, L, M, N, O][P, Q, R, S, T]  배열 탐색 행우선 탐색기대출력결과: ABCDEFGHIJKLMNOPQRST 열우선 탐색기대출력결과: AFKPBGLQCHMRDINSEJOT 지그재그탐색기대출력결과: ABCDEJIHGFKLMNOTSRQP 달팽이탐색기대출력결과: ABCDEJOTSRQPKFGHINML  방향 탐색 자음의 주변을 + 로 탐색하고 요소의 합을 출력하시오. ('A'=0, 'B'=1, ...)기대출력결과: 498 모음의 주변을 X로 탐색하고 요소의 합을 출력하시오. ('A'=0, ..

페르마는.. 무려 변호사에 취미 삼아 수학을 했다고 한다. ㅎㄷㄷ피에르 드 페르마 - 위키백과, 우리 모두의 백과사전 (wikipedia.org) 피에르 드 페르마 - 위키백과, 우리 모두의 백과사전피에르 드 페르마(프랑스어: Pierre de Fermat, 프랑스어 발음: ​[pjɛːʁ də fɛʁma], 1607년 ~ 1665년 1월 12일)는 프랑스의 변호사이자 수학자이다. 페르마는 미적분학에서 이용되는 여러 방법을 창안하ko.wikipedia.org이번 포스트에서는 나머지연산의 순환 특성과 연관된 "페르마의 소정리"라는 것을 알아보고 왜 중요한지 고민해보는 시간을 가져보자. 나머지의 순환 나머지 연산누구나 알듯이 나머지 연산은 아래와 같이 정의해 볼 수 있다.n=ax+b에서 n%a = b (단 0..

APS과정에서 연산의 결과가 long을 넘는 아주 큰 수에 대한 사칙 연산이 필요한 경우가 있다. 당연히 overflow가 발생하기 때문에 결과 처리가 상당히 어렵다.long a = Long.MAX_VALUE -1;long b = Long.MAX_VALUE -1;System.out.println(a + b); // -4 그래서 특정 수로 나눈  나머지를 구하라는 문제가 자주 등장한다.// 합을 1007로 나눈 나머지를 출력하시오.System.out.println((a + b) / 1007) ? 하지만 위와 같은 경우도 a+b가 연산되는 과정에서 이미 overflowr가 발생하므로 원하는 답을 얻기 어렵다. 이런 경우 나머지 연산자의 분배 법칙을 이용해야 한다. 각각 %를 취한 후 다시 전체적으로 ..

이번 포스트에서는 비트 연산자에 대해 알아보자. 비트연산자(bitwise operator) 비트연산자란?비트 연산자는 말 그대로 0, 1로 구성된 비트를 피 연산자로 하는 연산자로 &, |, ~, ^, >, >>> 7가지가 있다.이중 >, >>>를 이동 연산자(shift operator)라고 하고 나머지 &, |, ~, ^를 논리연산자라고 한다.&, |, !의 경우  피연산자가 boolean 타입을 가질 수 있는데 이들은 단지 true/false만을 판단하며 비트 연산자와 성격이 다르다.true & false, !true 등 이동연산자(shift operator)쉬프트 연산자는 >가 있으며 각각 전체 비트를 왼쪽 또는 오른쪽으로 이동시킨다. 이때 밀리는 칸은 없어지고 추가되는 칸은 0으로 채워진다.각 비..

이번 포스트에서는 재귀의 동작 과정에서 발생할 수 있는 엄청난 중복 호출과 이를 극복하기 위한 메모이제이션에 대해서 살펴보자. 피보나치! 피보나치 수열 구하기 피보나치 수 - 위키백과, 우리 모두의 백과사전위키백과, 우리 모두의 백과사전. 피보나치 수를 이용한 사각형 채우기 수학에서 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다.ko.wikipedia.org 피보나치 수는 첫째항과 둘째 항이 1이고 그 뒤의 항은 바로 앞 두 항의 합인 수열이다. 1, 1, 2, 3, 5, 8, ... 이렇게 전개된다. 알고리즘 계에서는 달나라 토끼에서부터 건물 페인트 칠하기, 계단 오르기 등 정말 다양한 가면을 쓰면서 등장하는 녀석이..

앞선 포스트에서 기본적인 재귀의 특성과 재귀가 반드시 정복해야할 산임을 배웠다. 하지만 재귀 함수의 동작을 이해하더라도 재귀 함수를 작성하기가 쉽지는 않다. 이번 포스트에서는 어떻게 재귀 함수를 디자인 해야할지 살펴보고 연습해보자. 재귀 함수 디자인 재귀 함수 디자인 절차재귀함수는 수학적 귀납법을 이용한 점화식을 찾아서 문제를 해결한다. 수학적 귀납법은 크게 다음의 두 가지 사실을 증명하는 것이다.n=1일 때, 명제 p(n)이 성립한다.n=k일 때, 명제 p(n)이 성립한다고 가정하면 n=k+1일 때도 명제 p(n)이 성립한다. 재귀함수를 작성할 때도 수학적 귀납법에 의거해서 작성해주는데 먼저 구하려는 내용을 수학적 귀납법으로 풀고 점화식을 찾아야 한다.풀이 결과 1번 항목이 base part가 되고 2..

동일한 로직을 여러 번 적용하기 위해서는 반복문을 적용할 수 있는데 이 반복문은 재귀의 형태로 변경이 가능하다. 그런데 일반적으로 사람들은 반복문에 상대적으로 익숙하기 때문에 굳이 당장 손이 가지않는 재귀를 사용하려 하지 않는다. 하지만 알고리즘에서 재귀는 선택이 아닌 필수이다.!이번 포스트에서는 반복문과 재귀를 비교해보고 최종적으로 왜 재귀를 써야하는지 살펴보자. 반복문 vs 재귀 반복문과 재귀 함수의 비교일반적으로 반복문과 재귀 함수는 다음과 같이 비교할 수 있다. 재귀 함수반복문종료 조건기본 파트에서 return반복문 종료 조건수행 시간메서드 호출 비용으로 상대적으로 느림상대적으로 빠름메모리stack 메모리 점유로 상대적으로 많이 사용상대적으로 적게 사용작성 난이도이해하면 사람의 표현기계적 반복제어..

이번 포스트에서는 재귀 함수가 어떻게 호출되면서 동작하는지 살펴보자. 재귀함수 동작이 처음에 와닿지 않는 경우가 많은데 재귀를 이해하기 위해서는 메모리에서 함수들이 어떻게 동작하는지 손으로 스택을 직접 그려가면서 공부하는 방법이 제일 좋다. 함수의 호출과 메모리 함수들을 호출되면서 stack 영역에 해당 함수만을 위한 메모리 공간을 확보하고 함수의 동작을 처리한다. 함수에서 또 다른 함수를 호출하는 경우 기존 함수의 메모리 공간 위에 새로운 함수를 위한 메모리 공간을 쌓게(stack)된다. 이때 기존의 메모리는 동작을 일시 정지하는 pending 상태가 되고 맨 위의 메모리 공간만 활성화 상태가 된다.  그리고 메서드가 return 되면 점유하고 있던 메모리 공간을 반환하고 기존에 pending 되어있던..