알고리즘

간단히 3개의 수를 받아서 최대값을 출력하는 코드를 짜 보자.3개의 수를 받는 간단한 방법은 Scanner클래스를 사용하는 방법이다. JDK1.5( 5 ) 이전 버전이라면 I/O Stream을 이용해야 할 것이나 기본적인 사용법은 생략하도록 하자.위 문장이 아래로 순서

세 값의 대소(작고 큼)관계는 총 13가지가 나오게 되는데 이 조합을 그림으로 나열한다면 나무 형태이므로 결정 트리라고 합니다. 위와 같은 구조로 작성하고 a,b,c의 값을 각각 최대한의 경우의수로 활용하면 총 13개의 경우의 수가 나오는 간단한 구조입니다. 이렇게 대

메서드 두개가 아래와 같이 있습니다.위 메서드는 분기가 3개로 같아보이지만 실제로는 method2가 분기가 4개입니다.method1은 'n이 1일 때', 'n이 2일 때', 'n이 1,2가 아닐때' 이렇게 3개이지만method2는 'n이 1일 때', 'n이 2일 때',

어떤 조건이 성립하는 동안 처리(프로그램 명령문 또는 명령어 집합)를 반복하여 실행하는 것을 반복(repetition)구조라 하며, 루프(loop)라고도 부릅니다. 이때 while문은 실행 전에 반복을 계속할지를 판단하는데, 이런 구조를 '사전판단반복'이라고 합니다.

논리연산자 "&&", "||", '!'를 사용할 때에는 단축평가와 드모르간 법칙이라는게 존재한다.위 코드를 실행했을때 System.out스트림에 결과가 어떻게 표시될까?method1 실행method2 실행true↑ 이렇게 실행될거라고 생각할 것이다. 나도 그랬었다.하지

java.util패키지에는 Random이라는 아주 큰 클래스 라이브러리가 있다. 해당 Random클래스는 자바1.0부터 지원했다. Random클래스의 인스턴스는 일련의 의사 난수(진짜 난수와 비슷한 가짜 난수)를 생성한다. 난수는 무(無)에서 생성되는 것이 아니라's

배열 요소를 역순으로 방법은 매우 많다.알고리즘과 for문을 이용해 뒤집는 메서드를 만들거나,배열 요소에 따라 comparater, comparable을 다시 구현해서 Arrays.sort메서드에 넣어 역순으로 바꾸는 방법도 있을 것이다.이번에는 알고리즘을 통해 배열을

클래스는 서로 다른 여러 데이터형을 자유로이 조합하여 만들 수 있는 자료구조이다.(객체지향적인 관점에서의 개념과는 다를 수 있다.) 클래스 다루기 신체검사가 한창 진행중인 병무청이라고 예를 들어보자. (안간 사람은 화이팅) 총 8명의 사람이 신체검사를 받고 각각 이름

데이터 집합에서 원하는 값을 가진 요소를 찾아내는 검색 알고리즘을 살펴보자. 검색과 키 살펴보기 주소록을 검색한다고 가정하자. 검색은 다음과 같이 다양한 방법으로 이루어진다. 국정이 한국인 사람을 찾는다. 나이가 21세 이상, 27세 미만인 사람을 찾는다. 찾으려는

프로그램의 실행 속도는 프로그램이 동작하는 하드웨어나 컴파일러 등의 조건에 따라 달라진다. 알고리즘의 성능을 객관적으로 평가하는 기준은 복잡도(complexity)라고 한다. 복잡도는 다음의 두 가지 요소를 가지고 있다. >시간 복잡도(time complexity):

재귀란? 어떤 사건이 자기 자신을 포함하고 있거나 또는 자기 자신을 사용하여 정의하고 있을 때 이를 재귀적(recursive)이라고 한다. 보통 예시로 이런 그림을 많이 쓴다. 이러한 재귀의 개념을 사용하면 1부터 시작하여 2,3,...과 같이 무한히 계속되 자연수

하노이의 탑이란? 작은 원반이 위에, 큰 원반이 아래에 위치하도록 쌓은 원반을 3개의 기둥 사이에서 옮기는 문제이다. 모든 원반은 크기가 다르고 처음에는 모든 원반이 이 규칙에 맞게 첫 번째 기둥에 쌓여있다. 이 상태에서 모든 원반을 세번째 기동으로 최소의 횟수로 옮기

이 문제도 하노이의 탑과 비슷하게 작은 문제로 나누어 해결하는 문제다. 8퀸 문제란? 8퀸 문제는 재귀 알고리즘을 깊이 있게 이해하기 위한 예제로 자주 등장하고 프리드리히 가우스가 잘못된 해답을 내놓은 문제로도 잘 알려져 있다. >서로 공격하여 잡을 수 없도록 8개의

정렬이란? 이름, 학번, 키 등 핵심 항목(key)의 대소관계에 따라 데이터 집합을 일정한 순서로 나열하는 작업을 말한다. 이 알고리즘을 이용해 데이터를 정렬하면 검색을 더 쉽게하는 자료형으로 바꿀수도 있다. 정렬에는 보통 오름차순(ascending order) 정렬

버블 정렬은 이웃한 두 요소의 대소 관계를 비교하고 필요에 따라 교환을 반복하는 알고리즘이다. 단순 교환 정렬(straight exchange sort)라고도 부른다.버블 정렬은 정렬시 데이터의 분포가 거품이 올라오는것 처럼 보인다고 해서 버블 정렬이다.참고로 버블 정

단순 선택 정렬이란? 가장 작은 요소를 맨 앞으로 이동시키고, 두번째 작은 요소는 맨 앞에서 두번째로 이동하는 등의 작업을 반복하는 알고리즘이다. 일단 처음부터 끝까지 한번 훑고 순서를 정해서 정렬시키는 방식으로 보면 된다.어떠한 경우에서도 n(n-1)/2에 비례하는

단순 삽입 정렬이란? 선택한 요소를 그보다 더 앞쪽의 알맞는 위치에 '삽입하는' 작업을 반복하여 정렬하는 알고리즘을 뜻한다. k번째 원소를 1부터 k-1번까지 비교하여 적절한 위치에 끼워넣는 방식이다 버블정렬, 단순 선택 정렬과 함께 대표적인 O(n^2)의 복잡도를

앞서 포스팅한 세 가지 단순 정렬(버블, 선택, 삽입)의 시간 복잡도는 모두 O(n^2)이었다. 1만개를 정렬하는데 1초가 걸렸다면 10만개를 정렬하는데 100초가 걸린다는 뜻이다. 앞으로의 포스트에서는 이들을 개선하여 사용 해 보자. 셸 정렬 셸 정렬이란? 단순

퀵 정렬이란? 퀵 정렬은 이름대로 가장 빠른 정렬 알고리즘 중 하나이다. 1959년 토니 호어(Sir Tony Hoare, 본명은 Charles Antony Richard Hoare 인데 왜 Tony인지는 모르겠다)가 제안한 정렬 방법으로 일반적이고 폭넓게 사용되는 아

병합 정렬이란? 배열을 앞부분과 뒷부분 둘로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬하는 알고리즘이다. 존 폰 노이만(오펜하이머에 나오는 그사람 맞음)이 1945년에 개발한 것으로 알려져 있다. 병합 정렬은 퀵정렬보다는 성능이 조금 뒤쳐지지고 데이터

java.util.Arrays클래스는 배열에 관련된 다양한 메서드를 제공한다.또한 Arrays의 생성자의 접근지정자는 private이며 이는 곧 모든 메서드가 static으로 이루어져 있고 인스턴스 생성이 불가능한 class라고 보면된다.Arrays.sort 메서드↓위

힙 정렬이란? 힙(heap)을 사용하여 정렬하는 알고리즘이다. 힙은 '부못값이 자식 값보다 항상 크거나 항상 작게'라는 조건을 만족하는 완전이진트리를 말한다. >트리란?? 트리는 자료형태가 나무처럼 생겼다고 해서 트리입니다. 트리의 가장 윗부분을 루트(root)라고

도수 정렬이란? 요소의 대소 관계를 판단하지 않고 빠르게 정렬할 수 있는 알고리즘이다. 다른 말로는 계수 정렬이라고도한다.영문으로는 Counting Sort로 불린다.도수 정렬은 가장 큰 데이터에 따라 효율이 달라지는 특징이 있다.도수 정렬의 시간복잡도는 O(n + k

문자열 검색이란?? 어떤 문자열 안에 특정 문자열이 들어 있는지 조사하고, 들어 있다면 그 위치를 것을 말한다.예를 들어 "STRING"이란 문자열에서 "IN"을 검색하면 검색에 성공하고, "ER"을 검색하면 검색에 실패하게 된다. 이 때, "IN", "ER"처럼 검색

KMP법 KMP법이란? 부르트-포스법의 단점인 이미 검사한 부분을 또 검사해야되는 단점을 보완하여 그때까지 검사한 결과를 효과적으로 이용하는 알고리즘이다. KMP법 알아보기 브루트-포스법은 일치하지 않는 문자를 만난 단계에서 그때까지 검사한 결과를 버리고 패턴을 텍스

보이어&무어법이란? 보이어&무어법이란? 브루트-포스법을 개선한 KMP법 보다도 효율이 더 좋기때문에 실제 문자열 검색 프로그램에서도 널리 사용하는 알고리즘이다. 보이어&무어법 알아보기 Boyer와 Moore(무어의 법칙 무어아님)가 만든 보이어&무어법은 KMP법보다

연결 리스트란? 기존의 배열을 이용한 선형 리스트의 단점을 보완한 리스트이다. 배열을 통한 리스트를 구현시, 검색은 빠르나 자료의 추가/삭제가 느린점을 보완했으나, 검색이 느린게 단점인 리스트 구현 방식이다. JAVA에서는 List인터페이스를 구현한 LinkedList

트리(tree)란? 트리라는 단어는 익숙할 것이다. 한국어로 나무라는 뜻이고, 프로그래밍에서는 자료구조의 명칭중 하나로 불린다. 우리는 프로그래밍에서의 트리를 알아볼 것이기 때문에 왜 이런 이름이 붙었는지 살펴보자.트리라는 이름이 붙은 이유는 나무같이 생겨서이다. 그래

해시(hash)법이란? 해시법이란? 검색뿐만 아니라, 데이터의 추가와 삭제도 효율적으로 수행하는 방법이다. 임의의 길이를 갖는 데이터를 고정된 길이의 데이터로 매핑(mapping)하는 단방향 함수를 일컫는다. 쉽게 말하자면 아무리 큰 수를 넣어도 정해진 크기의 숫자가

이 전의 기초 알고리즘 책을 끝내고, 좀 더 심화내용이 담겨있는 책으로 공부를 시작했다.시간 복잡도, 버블/병합정렬, 자료구조등에 대한 기본적인 지식이 있다는 가정 하에 알고리즘시리즈를 이어나가자.이 책은 '백준 온라인 저지'를 활용해서 작성된 책이기에 누구나 백준에

우리가 코드를 작성하고 실행할 때 예상치 못한 오류를 마주쳤다고 가정하자. 코드가 간단한 경우든 복잡한 경우든 우리는 해당 오류를 해결해야하고 이를 해결해야한다. 프로그램에서 발생하는 문법 오류나 논리 오류를 찾아 바로잡는 과정을 디버깅(debugging)이라한다.

프로그래밍을 하다 보면 '구간 합'과 '부분 합'에 대해 들어볼 수 있는데 이의 뜻은 각각 아래와 같다. 구간 합(Prefix Sum) : 구간 합이란 수들의 나열에서 특정 구간의 합을 의미한다. 구간 합 알고리즘은 보통 1차원 배열에서 i ~ k 인덱스 사이의 값들의

투 포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다. 알고리즘이 매우 간단하기에 어렵지는 않을것이다. 문제 연속된 자연수의 합 구하기 - 백준2018번 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤