Algorithm & Data Structure

[JAVA] baekjoon 1271

https://www.acmicpc.net/problem/1271 1271번: 엄청난 부자2 첫째 줄에는 최백준 조교가 가진 돈 n과 돈을 받으러 온 생명체의 수 m이 주어진다. (1 ≤ m ≤ n ≤ 101000, m과 n은 10진수 정수) www.acmicpc.net 브론즈 5 문제이다. BigInteger int(약 -+20억, -2,147,483,648 ~ 2,147,483,647)와 long(-9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807)보다 더 큰 범위의 타입 무한의 정수가 들어갈 수 있는 가능성이 있다면 BigInteger이라는 클래스를 활용하는 것이 좋음 알고리즘 문제에서 최악의 경우를 대비하고자 사용하기도 함 BigInteger을 초기화..

[Concept] 재귀 용법

재귀 용법 함수 안에서 동일한 함수를 호출하는 형태 여러 (고급정렬 포함한) 알고리즘 작성시 사용되므로, 익숙해져야 합니다. 스택의 구조와 똑같이 동작이 이루어집니다. 파이썬에서 재귀 함수는 깊이가(한번에 호출되는...) 1000회 이하가 되어야 합니다. 함수를 하나 만든다. 함수(n) 은 n > 1 이면 return n X 함수(n - 1) 함수(n) 은 n = 1 이면 return n 예시 2! 1. 함수(2) 이면, 2>1 이므로, 2 X 함수(1) 2. 함수(1)은 1이므로, return 2 X 1 = 2 3! 1. 함수(3)이면, 3>1이므로, 3 X 함수(2) 2. 함수(2)이면, 2>1이므로, 3 X 2 X 함수(1) 3. 함수(1)은 1이므로, return 3 X 2 X 1 = 6 psud..

삽입 정렬

삽입정렬은 정렬 범위를 1칸씩 확장해나가면서 새롭게 정렬 범위에 들어온 값을 기존 값들과 비교하여 알맞은 자리에 꼽아주는 알고리즘입니다. 예제와 함께 보는 정렬 방식 맨 처음 두개의 값을 정렬범위로 시작합니다. 1. 1을 앞에 있는 2와 비교. (맨 첫번째 값이니 끝) => [2, 1, 5, 4, 3] 더 큰 값이네? 1과 swap => [1, 2, 5, 4, 3] 2. 한 칸을 더 확장하여 그 값을 정렬된 배열과 비교. 5를 앞에있는 2와 비교. => [1, 2, 5, 4, 3] 바꿀 필요 없으니 교환하지 않고 끝. 3. 한 칸을 더 확장하여 4를 앞에있는 5와 비교. => [1, 2, 5, 4, 3] 더 큰 값이네? 5와 swap => [1, 2, 4, 5, 3] 2와 바꿀 수 없으니 비교 종료. 4..

선택 정렬

가장 최소인 값을 맨 앞 값이랑 바꿔주는 "선택" 정렬 패턴 파악 데이터 3개 (턴 2번, 1. 최솟값과 비교 2번 2. 최솟값과 비교 1번) 1. 턴 한번 5 4 2 2 4 5 데이터 4개 (턴 3번, 1. 최솟값과 비교 3번 2. 최솟값과 비교 2번 3. 최솟값과 비교 1번) 5 4 3 1 1 4 3 5 1 3 4 5 파악되는 중요 패턴은 다음과 같다. 1. 매 턴마다 앞 자리가 정해지면서 반복 횟수가 줄어든다. 2. (매 반복에서) 맨 앞 인덱스의 값과 최솟값을 바꾼다. psudo 코드 for i in range( len(data) -1 ): min = i for j in range( i+1, len(data) ) : if data[min] > data[j]: min = j swap(data[min..

버블 정렬

앞에서부터 2개씩 크기를 비교하여 정렬하는 "버블" 정렬 패턴 파악 데이터 2개 (턴 한번, 비교 1번) 1. 턴 한번 5 2 2 5 데이터 3개 (턴 두번, 비교 2번) 1. 턴 한번 5 4 2 4 5 2 2. 턴 두번 4 2 5 2 4 5 데이터 4개까지 해보면 패턴이 보일 것이다. 1. 한 턴에서 비교 횟수 : [데이터 길이 -1]번 진행 2. 턴 횟수 : [데이터 길이 -1]번 진행 3. 한 턴이 마무리되면 가장 큰 값은 맨 뒤에 위치하게 된다. -> 매 턴마다 비교 횟수를 줄여도 된다. psudo 코드 for index in 데이터 길이 -1 만큼 반복: for 데이터 길이 -1 -index 만큼 조건 체크: if 앞데이터 > 뒤데이터: swap(앞, 뒤) * 스왑이 일어났는지 체크해서, 이미 ..

[Concept] 해쉬 테이블 (Hash Table)

대표적인 데이터구조로 해쉬 테이블이 있습니다. Hash Table 키(key)에 데이터(Value)를 저장하는 데이터 구조 예) 파이썬 딕셔너리 타입 보통은 배열로 미리 Hash Table의 사이즈만큼 생성 후에 사용하지만 파이썬은 그럴 필요 X 용어 해쉬(Hash) : 임의 값을 고정 길이로 변환하는 것 해쉬 테이블 : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 (데이터를 저장할 공간 :Slot) 해싱 함수 : Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수 key가 입력, 해쉬 주소(해쉬 값)가 출력 해쉬 값 or 해쉬 주소 : Key를 해싱함수로 연산해서, 해쉬 값을 알아내고, 이를 기반으로 해쉬 테이블에서 해당 Key에 대한 데이터 위치를 쉽게 찾을 수 있습니다. 저..