본문 바로가기

자료구조

[자료구조] 배열과 리스트 배열(Array)이란? 메모리의 연속 공간에 값이 채워져있는 형태의 자료구조이다. 배열의 값은 인덱스를 통해 접근할 수 있고, 선언한 자료형의 값만 저장할 수 있다. 배열 생성·이용하기 int[] nums = {1,2,3,4}; int[] arr = new int[4]; 첫 줄처럼 배열 생성 시 배열에 값을 넣어 생성해 줄 수 있고, 두 번째 줄처럼 배열의 길이를 설정해 생성할 수도 있다. 두 번째 줄과 같이 생성한 경우에는 값을 나중에 대입해준다. 배열 생성 시에는 int, String 등 배열이 어떤 자료형인지를 선언해줘야 한다. 배열의 값을 넣어주는 방법은 특정 인덱스에 해당하는 값을 직접 넣어주거나 반복문을 이용해 넣어주면 된다. for문을 이용해 arr에 {1, 2, 3, 4}를 대입하는 방법은.. 더보기
[자료구조와 함께 배우는 알고리즘 입문] 6.정렬 알고리즘(2) 3. 단순 선택 정렬 3-1. 단순 선택 정렬 알아보기 가장 작은 요소는 맨 앞으로, 두 번째로 작은 요소는 맨 앞에서 두 번째로 이동하고 그 다음으로 작은요소, 또 그 다음으로 작은요소를 옮겨주면서 정렬해주는 알고리즘이다. 쉽게 표현하면 아래와 같은 과정을 통해 정렬을 시키는 것이다. 3-2. 단순 선택 정렬 적용 static void swap(int[] a, int idx1, int idx2){ int temporay = a[idx1]; a[idx1] = a[idx2]; a[idx2] = temporay; //idx1의 데이터 값을 임시 변수에 저장하고 //idx1과 idx2데이터 교환 } static void selectionSort(int[]a, int n){ for (int i = 0; i < .. 더보기
[자료구조와 함께 배우는 알고리즘 입문] 6. 정렬 알고리즘 (1) 1. 정렬 알고리즘이란? 1-1. 정렬이란? 정렬은 다들 알고 있는 것처럼 데이터를 순서에 따라 나열하는 것이다. 정렬 알고리즘을 이용해 데이터를 정렬하면 데이터 검색이 조금 더 쉬워지게 된다. 1-2. 정렬 알고리즘의 안정성 정렬 알고리즘은 안정된 알고리즘 / 안정되지 않은 알고리즘으로 나눌 수 있다. 안정된 정렬은 키값이 같은 요소의 순서가 정렬 전후에도 유지되는 것이다. 1-3. 내부 정렬과 외부 정렬 내부 정렬은 정렬할 모든 데이터를 하나의 배열에 저장할 수 있을 때 사용하는 알고리즘이다. 외부 정렬은 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없을 때 사용하는 알고리즘이다. 외부 정렬의 경우 알고리즘이 복잡해지고 별도의 팔일 등이 요구된다. 1-4. 정렬 알고리즘의 핵심요소 : 교환,.. 더보기
[자료구조와 함께 배우는 알고리즘 입문] 5. 재귀 알고리즘 (2) 3. 하노이의 탑 이런 식으로 원반 위에 원반이 쌓여있는 탑을 맨 끝에 있는 기둥으로 옮기는 문제가 하노이의 탑이다. 맨위의 원반을 1, 가운데를 2, 마지막을 3이라고 가정하고 위의 과정을 조금 축소시켜서 말해보면 1) (1,2)를 Pole2로 옮긴다 2) (3)을 Pole3으로 옮긴다. 3) (1,2)를 Pole3으로 옮긴다. 고 생각할 수 있다. 원반이 몇 개가 쌓여있는 같은 과정으로 처리하면 된다. 이걸 재귀로 해결할 수 있는데, 코드로 표현해보면 아래와 같이 작성할 수 있다. static void move(int no, int x, int y){ //no = 원반 개수, x = 시작하는 기둥 번호, y = 맨 마지막 기둥 번호 if(no>1){ move(no-1,x,6-x-y); //no = 3.. 더보기
[자료구조와 함께 배우는 알고리즘 입문] 5. 재귀 알고리즘 (1) 1. 재귀 알고리즘의 기본 1-1. 재귀란? 어떤 사건이 자기 자신을 포함하고 있거나 자기 자신을 사용해 정의하고 있을 때 재귀적이라고 한다. 1-2. 팩토리얼 구하기 팩토리얼(n!)은 1부터 n까지의 수를 모두 곱한 값을 구하는 것이다. 만약 5!을 한다면 5*4*3*2*1 = 120의 결과값이 나와야한다. 재귀를 이용해 팩토리얼을 구하는 함수는 다음과 같다. static int factorial(int n){ if(n==1){ return 1; } return n*(factorial(n-1)); } 만약 n이 1과 같으면 1을 반환시키고, 그렇지 않을 경우에는 n*을 factorial(n-1)과 계속 곱해주어 팩토리얼의 결과값을 반환시킬 수 있게 한다. 1-3. 유클리드 호제법 두 정수의 최대공약수를.. 더보기
[자료구조와 함께 배우는 알고리즘 입문] 4. 스택과 큐 스택, 큐는 이전에 간단하게 정리해둔 필기가 있어서 기본적인 건 그걸로 대체하고 추가로 내가 모르는 부분만 작성하기루 절대 귀찮은거 아님!!!!!!! 1. 스택 2. 큐 2-1. 배열로 큐 만들기 2-2. 링 버퍼로 큐 만들기 배열 요소를 앞쪽으로 옮기지 않는 큐를 구현하기 위해 사용하는 자료구조가 링버퍼이다. 약간 초등학생때 짜던 방학 계획표처럼 동그라미 안에서 첫 값과 마지막 값이 연결되어있는 구조라고 생각하면 된다. 맨 첫값과 끝 값을 논리적으로 구분하기 위해 사용하는 것이 프론트, 리어이다. 링 버퍼를 통한 큐의 인큐, 디큐는 시간복잡도 O(1)이 된다. 링버퍼를 사용해 큐를 구현하면 아래와 같이 구현할 수 있다. public class IntQueue { private int[] queue; /.. 더보기
[자료구조와 함께 배우는 알고리즘 입문] 3. 검색 알고리즘(2) 3. 이진 검색 3-1. 이진 검색 알아보기 이진검색은 배열이 오름차순이나 내림차순으로 정렬되어있을 때 데이터를 찾기 위해 사용하는 알고리즘이다. 배열이 오름차순으로 정렬되어있는 경우에는 다음과 같이 데이터를 찾으면 된다. 1) 배열의 중앙값과 찾고자 하는 데이터 비교 2) 중앙값보다 데이터가 작으면 중앙값 이전 부분에서 검색 수행 3) 중앙값보다 데이터가 크면 중앙값 이후 부분에서 검색 수행 배열이 내림차순일 경우에는 중앙값과 비교하는 부분은 동일하게 수행하고, 남은 두 단계는 반대로 수행해주면 된다. 기존 검색 알고리즘보다 검색 수행 속도가 절반으로 줄기 때문에 시간복잡도는 O(logN)이 된다. 오름차순으로 정렬된 배열을 이진검색하는 코드를 작성하면 아래와 같다. static int binSearc.. 더보기
[자료구조와 함께 배우는 알고리즘 입문] 3. 검색 알고리즘(1) 1. 검색 알고리즘이란? 1-1. 검색과 키 살펴보기 - 키값을 지정하는 방법 1. 키값과 일치하도록 지정 2. 키값의 구간을 지정 3. 키값과 비슷하도록 지정 4. 조건은 N개 이상으로 지정 가능 1-2 배열에서 검색하기 배열 내에서 찾고자 하는 데이터를 검색한다. 관련 알고리즘은 아래와 같다. 1. 선형 검색 : 무작위로 늘어있는 배열에서 검색 2. 이진 검색 : 일정한 규칙으로 늘어있는 배열에서 빠르게 검색 수행 3. 해시법 : 추가, 삭제가 자주 일어나는 배열에서 빠르게 검색/ 수행 2. 선형 검색 2-1. 선형 검색 알아보기 위에서 말한 것 처럼 선형검색은 무작위로 늘어있는 배열에서 찾고자 하는 데이터를 검색하는 것이다. 좀 더 이해하기 쉽게 표현하면 아래와 같다. 요걸 코드로 표현하면 아래와 .. 더보기
728x90

티스토리툴바