본문 바로가기

프로그래밍/자료구조/알고리즘

반복되지 않는 첫 번째 문자찾기 문자열에서 처음으로 반복되지 않는 문자를 찾아내는 알고리즘을 포스팅 해보고자 합니다. "akanea" 에서 반복되지 않는 문자는 무엇일까요? k, n, e 입니다. 여기서, 처음으로 반복되지 않은 문자는 k 입니다. 우선, 알고리즘을 구현하기 위해 생각해 볼 사항이 있습니다. '어떻게 문자를 찾을까?' 여기서 우리가 생각해보면 아주 간단합니다. '해당 문자마다 중복되면 하나씩 카운팅해서 가장 첫번째 있는 문자 카운팅이 1 인 경우' 즉, akanea 가 있을때 각 문자별로 카운팅을 한다고 가정해봅시다. a 는 3, k 는 1, n 은 1, e 는 1 여기서 첫번째 중복되지 않는 문자 k 는 카운팅이 1이므로 정답은 k 가 됩니다. 이 알고리즘을 실제 적용해보도록 하겠습니다. 우선, 어떤 문자가 반복되는지.. 더보기
2개의 스택(Stack) 을 이용하여 큐(Queue) 만들기 2개의 스택을 이용하여 큐를 구현하는 방법을 포스팅 해보겠습니다. 생각보다 아주 간단합니다. 2개의 스택을 사용한 큐를 구현 하는 원리 알고리즘 내용 1. inBox 에 데이터를 push(삽입)한다. - A,B 2. inBox 에 있는 데이터를 pop(추출) 하여 outBox 에 push(삽입) 한다. - B,A 3. outBox 에 있는 데이터를 pop(추출) 한다. - A,B 순으로 출력됨 즉 inBox 스택에 A,B 순으로 데이터를 삽입하면 위에 처럼 inBox 스택에 위와 같은 순서로 쌓입니다. 그리고 inBox 스택에 있는 데이터를 pop 해서 outBox로 옮깁니다. 그렇게 되면 outBox 에는 B, A 순으로 쌓입니다. 그리고 다시 outBox 스택에 있는 데이터를 pop 하는경우 A,B .. 더보기
자바로 문자열 정수를 int 형 정수로 변경하는 알고리즘 이번 포스팅에서는 String 형 정수를 int 형 정수로 변경하는 방법을 배워보겠습니다. C언어서는 atoi 라는 함수를 통해 char[] 문자열을 정수로 바꿀 수 있고, 자바는 Integer 클래스에 parseInt 메서드를 통해 String 을 int 로 바꿀 수 있었습니다. 자 그럼 직접 parseInt 를 구현해보도록 하겠습니다. 우선 parseInt 를 직접 구현하기 앞서 아스키코드 와 String 이 어떻게 데이터를 내부적으로 저장하는지에 대해 선행 지식이 필요합니다. (이미 포스팅을 해두었으니 참고 바랍니다.) ※ 참고 : http://globalbiz.tistory.com/81 (String 클래스 깊숙히 이해하기) ex) String str = "12"; str 객체 에 담긴 12 문자.. 더보기
자바로 구현하는 큐 (Queue) 큐(Queue) ? 큐(queue)는 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다. 프린터의 출력 처리나 윈도 시스템의 메시지 처리기, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용된다. Queue 의 과정 큐의 데이터 삽입, 추출 과정 큐에서 front 는 가장 먼저 큐에 들어온 첫번째 원소 이고, rear 는 큐에 가장 늦게 들어온 마지막 원소가 된다. 공.. 더보기
자바로 구현하는 스택 (Stack) - 1차 수정 스택 (Stack) ? 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 자료구조(FILO - First In Last Out) 입니다. 스택(Stack) 스택은 데이터가 들어오는대로 맨 아래로 부터 순서대로 차곡차곡 데이터가 쌓입니다. 그리고, 데이터를 추출한다면 가장 상위 마지막에 들어온 데이터가 먼저 나가게 됩니다. 데이터를 밀어 넣는 행위 를 'Push' 라 하고, 데이터를 빼는 행위 를 'Pop' 이라고 합니다. 그리고 스택의 위치를 'Top' 이라 합니다. (가장 최근 데이터를 가르키는 위치) 스택의 응용분야는 정말 무수히 많습니다. 우리가 간단히 생각하는 브라우져의 뒤로가기 역시 스택이라고 보시면 됩니다. 브라우져에서 다양한 웹사이트를 타고 들어가다가 뒤로가기 버튼을 누르면 가장 처음 .. 더보기
트리 (Tree) 트리(Tree) 이번 포스팅에서는 트리 (Tree) 에 대해 알아 보고자 합니다. 트리는 스택, 큐와 달리 비 선형 자료구조 로서, 자료들간 계층 관계를 가지는 계층형 자료구조 입니다. 트리가 사용되는 범위는 매우 다양합니다. (파일 디렉토리 구조 등) 이번 포스팅의 목적은 트리가 무엇인지, 트리에서 지칭되는 단어가 무엇인지 알아보겠습니다. 트리는 나무 모양 형태로 가지가 뻗어가는 자료구조 입니다. 먼저 트리를 구성하는 지칭 단어를 살펴 보겠습니다. ----------------------------------------------------------------------------------------------------- Node - 트리를 구성하는 원소 (ex. 길동, 홍이, 영민, 사호...).. 더보기
자바로 구현하는 이진탐색 (BinarySearch) 알고리즘 이진탐색 (binary Search) 이진 검색 알고리즘(binary search algorithm)은 정렬된 리스트에서 특정한 값을 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값을 찾고자 하는 값과 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최고값이 되며, 작으면 그 값은 새로운 최하값이 된다. 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 된다. 이진 검색은 분할 정복 알고리즘의 한 예이다. (자바에서는 java.util.Arrays 클래스에 자바 1.2 부터 binarySearch 관련 메소드를 제공하고 있습니다.) 진행 순서 ex) 1,2,3,4,5,6 순서의 배열 중 5를 찾는다는 가정 1. 중간값을 임의.. 더보기
자바로 구현하는 퀵정렬 (Quick Sort) 알고리즘 퀵 정렬(QuickSort) 이란? 분할 작업을 순환적으로 반복하면서 피봇의 왼쪽 왼쪽 부분 집합과 오른쪽 부분집합을 정렬 하는 방법 1. 전체원소 가운데 하나의 원소를 중심(Pivot)으로 2개의 부분 집합으로 분할 한다. 2. 기준값(Pivot) 보다 작은 원소는 왼쪽 부분집합으로, 기준값(Pivot) 보다 큰 원소들은 오른쪽 부분 집합으로 정렬한다. 3. 분할된 부분집합의 크기가 0이나 1이 될 때 까지 순환 호출을 이용하여 다시 분할 한다. 위 과정을 반복하는 것이 퀵정렬 입니다. 출처 - http://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC C로 배우는 쉬운 자료구조 (한빛미디어) 서적의 수도코드 (pseudo code) 를 참고 하였으며, 서적.. 더보기
자바로 구현하는 선택정렬 (Selection Sort) 알고리즘 선택정렬이란? 제자리 정렬 알고리즘의 하나로, 전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식 1. 주어진 원소중 최소값을 찾는다. 2. 그 값을 첫 번째 원소와 교환 한다. 3. 그 다음 작은 원소를 찾아 다음 위치의 원소와 비교하여 교환한다. 위 과정을 반복하는 것이 선택정렬 입니다. 출처 - http://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC 수도코드 예를들어, {80, 6, 2, 3, 1} 원소를 정렬하고자 하는 경우, (기준위치 를 빨간색, 최소값 위치 파란색으로 표시) 1단계 80 6 2 3 1 정렬후 : 1 6 2 3 80 2단계 1 6 2 3 80 정렬후 : 1 2 6 3 80 3단계 1 2 6 .. 더보기
자바로 구현하는 버블소트 (Bubble sort) 알고리즘 거품 정렬(Bubble sort)이란 ? - 두 인접한 원소를 검사하여 정렬하는 방법 시간 복합도가 로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다. 출처: http://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC 여기서 잠깐! 자바에선 편리하게도 배열, 리스트 형태의 데이터를 정렬해주는 클래스가 존재한다. Arrays 클래스의 Sort 메서드를 통해 byte, int, short 배열 등 각 타입배열에 따른 정렬을 제공해주고, Collections 클래스의 sort, reverse 메서드를 통해 List 타입의 자료를 정렬해준다. 두 방식 모두 순.. 더보기

티스토리툴바