본문 바로가기

전체 글

 (50)
덱 : Deque double ended queue 양쪽 끝에서 삽입 삭제가 가능한 자료구조로 스택과 큐의 특성을 모두 가지고 있다 push, pop 연산이 빈번한 경우 list보다 빠르다 동작에 따른 시간복잡도 원소의 추가/제거 O(1) 제일 앞/뒤 원소 확인 O(1) 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 구현 배열, 연결리스트로 구현 가능 구조 원소를 담을 배열 head : 가장 앞에 있는 원소 인덱스 tail: 가장 뒤에 있는 원소 인덱스 기능 add() vs offer() add : 값 추가 성공 시 true 반환 / 실패 시 IllegalStateException 에러 발생 offer : 값 추가 성공 시 true 반환 / 실패 시 false 반환 remove() vs poll() r..
Queue Queue 한 쪽 끝에서는 원소를 넣고 반대쪽 끝에서는 원소를 뺄 수 있는 자료구조 First In First Out 구조다 초기화 index 3 2 1 0 head, tail push 12 index 3 2 1 tail 0 12 head pop index 3 2 tail 1 13 0 12 head index 3 2 tail 1 13 head 0 동작에 따른 시간 복잡도 원소 추가 / 제거 O(1) 제일 앞/뒤 원소 확인 O(1) 양끝이 아닌 나머지 원소들의 확인 / 변경은 원칙적으로 불가능하다 구현 배열, 연결리스트로 구현이 가능하다 [구성] 원소들을 담을 배열 제일 앞쪽 인덱스 값 제일 뒤쪽 인덱스 값(다음 원소가 삽입될 위치) [성질] 원소가 들어 있는 위치 : data[tail - 1] ~ dat..
Stack Stack 한 쪽 끝에서만 입출력이 가능한 자료구조 Last In First Out 구조다 push x index 3 2 1 top 0 x pop index 3 2 top 1 13 0 12 index 3 2 1 top 0 12 동작에 따른 시간 복잡도 원소 추가 / 제거 O(1) 제일 상단 원소 확인 O(1) 제일 상단이 아닌 나머지 원소들의 확인 / 변경은 원칙적으로 불가능하다 구현 배열, 연결리스트로 구현이 가능하다 [구성] 원소들을 담을 배열 다음 원소가 삽입될 위치의 인덱스 값 push : 배열 사이즈를 넘어가지 않도록 유의 data[top++] = x pop : 원소가 하나도 없을 때 호출하지 않도록 한다 top-- top : pop과 마찬가지로 원소가 하나도 없을 때 호출하지 않도록 한다 da..
🌱마인드가든 재출시기🌱 마인드가든 출시 기념으로 재출시 과정 기록 개발 전 준비 19년도에 서버 만료로 마인드가든 서비스를 플레이 스토어에서 내린 이후 다시 출시하고 싶다는 마음은 쭉 있었다 그러나 동아리 -> 인턴 -> 취업으로 인해 투자할 시간이 많이 없었다 시간이 없다는 것이 핑계로 들릴 수도 있지만, 내가 생각했을 땐 이전 코드로는 도저히 이어갈 수 없어서 아키텍처부터 구상해서 많은 것들을 적용하려면 정말 꽤 많은 시간이 필요했다 그래서 작년까지는 적용하고 싶은 디자인 패턴과 기술에 대해 논의하고 스터디 하는 시간, 새로운 기획 등을 구상하는 시간이 대부분이었다 그러다 올해 3월 드디어 나에게 시간이 주어졌다 열정에 불타올라 당장 개발에 착수❤️‍🔥 했다고 하기엔 깃헙이 많이 허전하다 본격 개발은 5월부터 했다 그전까지..
최대공약수, 최소공배수 찾기 : 유클리드 호제법 최대공약수를 찾아야 하는 알고리즘 문제를 만났다 2부터 하나 하나 나눠보다간 시간초과 나올게 뻔했다 그렇다면 몰러요ㅠ 검색해보니 최대공약수를 구하는 알고리즘이 존재했다 이름도 멋져 유클리드 호제법 호제법은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘이다 유클리드씨께 최대공약수 찾는 비법 전수 받겠습니다 최대공약수(GCD) 구하기 : 유클리드 알고리즘 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 나머지가 0이 될 때까지 mod 연산을 반복하도록 구현하면 된다 O(logN)의 시간복잡도를 갖는다 반복문 구현 fun gcd(num1: Int, num2: Int): Int { var ..
연결리스트 자료구조 원소 저장 시 다음 원소가 있는 위치를 포함하여 저장하는 자료구조 특성 1. K번째 원소를 확인/변경하기 위해 O(n)이 필요함 (다음 원소가 무엇인지 하나 하나 확인 필요) 2. 임의의 위치에 원소를 추가/제거 O(1) : 연결리스트의 장점 종류 단일 연결 리스트 각 원소가 다음 원소의 주소를 가지고 있는 리스트 이중 연결 리스트 각 원소가 이전 원소와 다음 원소의 주소를 가지고 있는 리스트 (단일 연결 리스트보다 메모리를 많이 씀) 원형 연결 리스트 끝과 처음이 연결되어 있음 각 원소가 이전 원소 다음 원소의 주소를 둘다 가지거나 하나만 가져도 상관없음 연산별 시간 복잡도 임의의 위치에 있는 원소를 확인/변경 : O(n) 첫번째 원소의 주소만 알고 있기 때문에 n번째 원소를 보기 위해선 순차..
프로그램과 메모리 공간 프로그램이 실행되는 과정 1. 사용자가 실행을 요청 2. 운영체제는 프로그램의 정보를 읽어 메모리에 공간 할당 3. CPU는 프로그램의 코드 실행 메모리 구조 Text (코드영역) 코드를 실행하기 위한 정보들이 저장되는 영역으로 CPU는 이 영역에 저장된 명령어를 가져다 실행한다 제어문, 함수, 상수 등이 저장됨 Data 코드에서 선언한 전역변수, 정적 변수 등이 저장되는 공간 프로그램의 시작과 함께 할당되며, 프로그램 종료 시 소멸한다 초기화 된 변수 영역, 초기화 되지 않은 변수 영역으로 나뉜다 Heap 사용자에 의해 관리되는 동적 할당 영역 클래스 인스턴스, 클로저 같은 참조 타입이 저장된다 Java에서는 gc에 의해 자동으로 해제된다 낮은 주소에서 높은 주소 방향으로 메모리가 할당된다 Stack ..
배열 메모리 상에 원소를 연속적으로 배치한 자료구조 특성 1. O(1)에 k번째 원소를 확인/변경 가능 2. 추가적으로 소모되는 overhead가 거의 없음 연산과 시간 복잡도 1. 임의의 위치에 있는 원소를 확인/변경 O(1) 2. 원소를 끝에 추가 O(1) 3. 마지막 원소를 제거 O(1) 4. 임의의 위치에 원소를 추가 O(N) 추가하는 위치 뒤에 있는 원소들을 한칸씩 뒤로 밀어야 하기 때문에 O(N) 소모 추가하는 위치가 뒤쪽에 가까울 수록 소요되는 시간은 줄어듬 5. 임의의 위치에 원소를 제거 O(N) 지운 원소 뒤에 있는 원소들을 앞으로 한칸씩 당겨 와야하기 때문에 O(N) 소모 BOJ 문제 풀기 문제 문제집: 0x03강 - 배열 (BaaaaaaaaaaarkingDog) www.acmicpc.net..

티스토리툴바