Adrian's Web Page

이번에는 조금 더 어려운 이야기를 해보자. 이번 시간에는 그래프에 대한 지식이 살짝 필요하니 모르시는 분들은 미리 사전 학습을 해보시는 걸 추천합니다.(그래프 위키 백과 : https://ko.wikipedia.org/wiki/%EA%B7%B8%EB%9E%98%ED%94%84) 임의의 그래프에서 최단거리를 구하는 방법을 알아 보자. 최단거리 문제를 푸는 대표적인 2가지 방법은 다익스트라 알고리즘과, 워셜-플로이드 알고리즘이 존재한다. 1. 다익스트라 알고리즘 (Dijkstra algorithm) 다익스트라 알고리즘을 적용하기 위해선 아래의 조건을 만족하는 그래프여야한다.음의 가중치를 가지는 edge가 있어서는 안된다. 다익스트라 문제를 풀기 위해 아래와 같은 그래프를 예시로 들어 문제를 해결하자. 위 그..

프로그래밍 문제해결에서 가장 많이 쓰이는 코딩 스킬 중 하나인 "동적 계획법(Dynamic Programming)"에 대해 알아볼 시간이다. 이름에서 알 수 있듯이 알고리즘이 아는 프로그래밍 방법이라고 생각하면 좋다. 하지만, 알고리즘 시간에 소개하는 이유는 워낙 많이 쓰이기도 하고, 앞서 배웠던 Conquer 알고리즘의 응용 버전이기 때문이기도 해서 이번 시간에 소개를 할 생각이다. 우리 모두 피보나치 수열이 무엇인지는 알고 있을 것이다. 피보나치 문제를 푸는 가장 좋은 방법은 반복해서 풀어낸다. 코드로 작성하기도 매우 쉽고 직관적으로도 이해가 잘 된다. 피보나치 수열을 recursive 하게 풀어낸다면 아래와 같은 코드를 작성하게 될 것이다. 12345678910111213141516171819202..

앞서 배운 Space-time trade off 알고리즘의 응용해여 장문에서 특정 문자열을 찾는 프로그램을 구현해보자. 보기가 되는 텍스트를 보고 내가 찾고자 하는 단어가 몇번째에 행에 나오는지 찾는 과정이다. An automaton is a self-operating machine or a machine or control mechanism designed to automatically follow a predetermined sequence of operations, or respond to predetermined instructions. 위 문장은 영문 위키백과에 나온 오토마타(자동기계)에 관한 정의이다. 위 텍스트에서 우리가 찾고자 하는 단어는 sequence이다. 이 단어를 아래 알고리즘들이 ..

앞선 시간에 리스트 안에 있는 데이터의 개수를 구하는 방법에 대한 알고리즘을 배워보았다. Brute Force 방식을 이용해 O(n^2) 시간 복잡도를 가지는 알고리즘을 배웠고, Transform & Conquer를 이용하여 미리 정렬을 수행한 다음 차례대로 그 숫자를 읽는 방법에 대해 배웠다. 두가지 방법보다 더욱 쉽게 데이터 안에 있는 숫자들의 개수를 구하는 방법이 있다. A = {5, 2, 7, 5, 4, 1, 2, 3} 다음과 같이 총 8개의 자료가 존재한다고 하고 리스트 안에 있는 최소값과 최대값이 1과 7이라는 사실을 알고 있다고 가정하자. 그렇다면 공간 7개를 가지는 별도의 리스트를 만든다. (Ex. B[7]의 리스트 생성) 그리고 인덱스 0부터 7까지 있는 해당 배열에 A를 탐색하며 해당 ..

1부터 100까지의 숫자 중 특정한 숫자 하나를 찾는 방법은 무엇이 있을까? 가장 간단하고 정확한 방법은 찾으려는 1부터 100까지 숫자를 각각 비교해나가는 방법이다. 조금 무식하고 오래 걸리는 방법이긴 하지만 더 정확한 방법은 없다. 특히 숫자가 배열 구조로 저장되어 있다면 이런 방법을 사용할 수 밖에 없다. 이 구조를 이진 트리 구조로 바꿔보자. 최상위 노드에 중앙 값인 50을 넣고 그 아래는 각 서브트리에 해당하는 중앙 값은 25와 75를 차례대로 기록한다. 이런 방식으로 1부터 100에 대한 숫자를 이진 트리로 바꿔 저장되어 있다고 생각해보자. 찾으려는 숫자를 50과 비교하여 크다면 75서브트리로, 50보다 작다면 25서브트리로 내려간다. 이런 방식으로 숫자를 찾게 된다면 단 7번의 비교로도 원하..

독일의 천재 수학자 가우스는 초등학교 시간에 1부터 100까지의 숫자를 모두 더하라는 선생님의 질문에 계산을 순식간에 끝냈다고 한다. 1부터 100의 숫자는 등차수열로 연속된다. 따라서 1과 100, 2와 99, 3과 98이 서로 짝지어져 있고, 이 계산이 총 50번 반복되는 구조를 갖는다. 따라서 101 * 50이라는 단 한번의 연산으로 1부터 100까지의 모든 합계를 구해냈다. 이 공식은 나중에 등차수열의 합계를 구하는 기본 공식이된다. 이 처럼 1부터 100까지 더하는 문제를 두개씩 짝지어 풀어야 되는 부분은 50개로 나눈다면 쉽게 풀어낼 수 있다. 이처럼 일정한 문제를 동일한 크기의 n개로 나누어 푸는 방식을 분할 정복 알고리즘 (Divide and Conquer)라고 한다. 분할 정복 알고리즘은..

대학교 M.T나 술자리에서 '베스킨라빈스 31'게임을 많이 해본적이 있는가? 여러명이 둘러 앉은 다음 숫자 1부터 차례대로 1개부터 3개씩 숫자를 말하다가 31을 말하게 되는 사람이 패배하게되는 게임이다. 해당 게임의 필승 전략이 있을까? 2명이서 이 게임을 즐기고 있다고 가정해보자. 31을 말하면 안되므로, 당신이 30을 말하게 된다면 이길 것이다. 그렇다면 30을 말하게 될려면 상대방의 숫자가 27,28,29 도록 말해야 자신이 30을 말할 수 있다. 그러면 27,28,29를 말하게 할려면 어떻게 해야할까? 이런식으로 문제를 풀어 나갈 수 있다. 우리의 최종 목표인 31을 말하지 않기 위해 그 범위를 줄여나가면서 푸는 알고리즘을 부분 정복 알고리즘 (Decrease and Conquer)라고 한다. ..

알고리즘은 어려운 문제를 얼마나 빠르고 정확하게 풀 수 있느냐가 중요하다. 그래서 알고리즘이 있다면 해당 알고리즘이 얼마나 빠른지 측정할 수 있는 객관적인 지표가 필요하다. 어느 알고리즘이든 이를 적용할 수 있는 표준적인 방법이 필요할 것이다. 이것이 바로 시간복잡도이다. 1. 시간 복잡도 알고리즘의 실행 시간은 컴퓨터의 성능, 사용한 프로그래밍 언어, 컴파일러의 종류에 따라 결정된다. 그리고 알고리즘 자체가 가진 실행 속도도 매우 중요하다. 알고리즘의 실행 시간은 2가지 부분으로 나누어서 생각 할 수 있다. 첫번째는 입력 값이다. 같은 알고리즘을 사용한다고 가정했을 때, 1부터 100까지 더한 결과를 구하는 것과 1부터 1억까지 더하는 것의 시간 차이는 크다. 입력값이 클수록 알고리즘을 푸는데 더 오랜..

도둑이 0~9까지 숫자로 되어있는 다섯자리 비밀번호를 풀어야 한다고 가정해보자. 그리고, 도둑은 그 비밀번호에 대한 사전 정보가 전혀 없다고 가정하다. 이때, 선택할 수 있는 방법은 무엇일까? 바로 모든 다섯자리 숫자인 10만개를 순서대로 하나 쳐보는 것이다. 1. Brute Force란? Brute Force 알고리즘은 가능한 경우의 수를 모두 입력하는 것이다. 이게 무슨 알고리즘이냐고 할 수 있겠지만, Brute Force 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답을 출력해낸다. 앞에서 말한 예시대로 도둑이 10만번에 번호를 누르게 된다면 언젠가는 분명히 열린다. 00000~99999까지 계속 입력하다보면 비밀번호를 알아낼 수 있다. 사전 정보가 없을 때라면 무조건 선택 할 수 밖에 없..

이번 시간에는 파일을 통한 입출력 방법에 대해 알아보자. 우리는 Java 프로그램을 통해 다양한 파일에서 데이터를 읽어 들이기도 하고, 파일을 생산해내기도한다. 이번 주제 역시 기초적인 Java 프로그래밍 지식은 반드시 필요하다. 1. 파일 입력 객체지향 언어인 Java에서 파일 입출력 역시 클래스를 통해 진행된다. 기본 매커니즘은 파일 입출력을 담당하는 클래스의 객체를 선언하고, 읽고자 하는 파일을 파라미터로 선언해야 한다. 그 이후, 해당 객체의 메소드를 통하여 파일을 읽어 들으면 된다. 아래에서 파일 입출력에 대해 자세히 알아보자. 다음과 같은 간단한 구조의 텍스트 파일을 읽어 들이는 방법에 대해 알아보자. Java에서 파일을 읽는 클래스는 'FileInputStream'이다. 해당 클래스를 선언에..