알고리즘 썸네일형 리스트형 반복되지 않는 첫 번째 문자찾기 문자열에서 처음으로 반복되지 않는 문자를 찾아내는 알고리즘을 포스팅 해보고자 합니다. "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 .. 더보기 자바로 구현하는 큐 (Queue) 큐(Queue) ? 큐(queue)는 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out)구조로 저장하는 형식을 말한다. 영어 단어 queue는 표를 사러 일렬로 늘어선 사람들로 이루어진 줄을 말하기도 하며, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 된다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다. 프린터의 출력 처리나 윈도 시스템의 메시지 처리기, 프로세스 관리 등 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용된다. Queue 의 과정 큐의 데이터 삽입, 추출 과정 큐에서 front 는 가장 먼저 큐에 들어온 첫번째 원소 이고, rear 는 큐에 가장 늦게 들어온 마지막 원소가 된다. 공.. 더보기 자바로 구현하는 스택 (Stack) - 1차 수정 스택 (Stack) ? 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 자료구조(FILO - First In Last Out) 입니다. 스택(Stack) 스택은 데이터가 들어오는대로 맨 아래로 부터 순서대로 차곡차곡 데이터가 쌓입니다. 그리고, 데이터를 추출한다면 가장 상위 마지막에 들어온 데이터가 먼저 나가게 됩니다. 데이터를 밀어 넣는 행위 를 'Push' 라 하고, 데이터를 빼는 행위 를 'Pop' 이라고 합니다. 그리고 스택의 위치를 'Top' 이라 합니다. (가장 최근 데이터를 가르키는 위치) 스택의 응용분야는 정말 무수히 많습니다. 우리가 간단히 생각하는 브라우져의 뒤로가기 역시 스택이라고 보시면 됩니다. 브라우져에서 다양한 웹사이트를 타고 들어가다가 뒤로가기 버튼을 누르면 가장 처음 .. 더보기 자바로 구현하는 퀵정렬 (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 타입의 자료를 정렬해준다. 두 방식 모두 순.. 더보기 이전 1 다음
