programmer life guidance 101

프로그래머스 힙 - 디스크컨트롤러 :programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를�� programmers.co.kr 처음 문제를 접했을 때는 가장 빠른 시간을 기준으로 정렬한 뒤 계산하는 greedy 알고리즘이 생각났다. 하지만 곧 문제유형이 Heap인 것을 보고 클래스를 정의하여 우선순위큐에 사용해야함을 인지했다. 하지만 나는 단순히 pq하나만 구현하여 그 안에서 정렬해준 뒤 계산하면 되는 줄 알았지만... 문제는 풀리지 않았고 ( 언제쯤 혼자..

> 트라이(Trie) 문자열에서의 검색을 빠르게 해주는 자료구조 래딕스 트리(radix tree) 나 접두사 트리(prefix tree)라고도 한다. 우리는 정수형 자료형에 대해서 이진검색트리를 이용하면 O(logN)의 시간만에 원하는 데이터를 검색할 수 있다. 하지만 문자열에서 이진검색트리를 사용한다면 문자열의 최대길이가 M이라면 O(MlogN)의 시간 복잡도를 가지게 될 것이다. 우리는 문자열 검색을 개선하기 위해 트라이를 이용하여 O(M)의 시간만에 원하는 문자열을 검색할 수 있다. 트라이라는 명칭은 Retrieval에서 유래한다. 트라이가 retrieve(탐색)하는데 유용한 걸 생각하면 납득ㅇ ㅣ디ㅗㄴ다. 자 그러면 트라이는 어떻게 문자열의 검색을 O(M)만에 처리할까? 아래 그림은 문자열 집합 ..

프로그래머스 2020 KAKAO BLIND RECRUITMENT 블록 이동하기 :https://programmers.co.kr/learn/courses/30/lessons/60063 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr 대표적인 BFS 구현문제 인줄 알고 쉽게 덤벼들었지만, 고려해야 할 게 많아 꽤 까다로웠다. 처음 생각은 bfs로 회전과 직선이동을 나누고 동서남북대각선 체크해주면서 벽이 아닌 곳의 최대좌표를 리턴해주며 최소시간을 구하는 것이었다. 하지만 테스트케이스를 충족하지 못하였고, 다른 블로그를 참고해서 답을 고쳤다. (..

> Sorting In Java 일반적으로 정렬은 가장 기본적인 알고리즘이기 때문에, 대부분의 프로그래밍 언어가 표준 라이브러리의 일부로 정렬을 제공한다. 따라서, 일반적인 상황에서 개발자가 직접 알고리즘을 구현할 경우는 많지 않다고 볼 수 있다. Java에서의 sorting을 알아본다. 기본 타입 데이터의 정렬 Arrays 클래스가 primitive 타입 데이터를 위한 정렬 메소드를 제공한다. int[] data = new int[capacity]; //data[0]에서 data[capacity-1]까지 데이터가 꽉 차있는 경우에는 다음과 같이 정렬한다. Arrays.sort(data); //배열이 꽉 차있지 않고 size개의 데이터만 있다면 다음과 같이 정렬한다. Arrays.sort(data, 0,..

> 우선순위 큐 Priority queue 힙의 응용 : 우선순위 큐 최대 웅선순위 큐(maximum priority queue)는 다음의 두 가지 연산을 지원하는 자료구조이다. INSERT(x) : 새로운 원소 x를 삽입 EXTRACT_MAX() : 최대값을 삭제하고 반환 최소 우선순위 큐(minimum priority queu)는 EXTRACT-MAX 대신 EXTRACT-MIN을 지원하는 자료구조 MAX HEAP을 이용하여 최대 우선순위 큐를 구현 INSERT max heap의 형태로 원소들이 저장되어 있고, 15가 insert되는 경우 아래와 같은 과정을 거친다. complete binary tree를 만족하면서, max heap property를 만족하도록 만들어 준다. pseudo code He..

> 힙 정렬 Heap Sort 최악의 경우 시간복잡도 O(nlogn) Sorts in place - 추가 배열 불필요 merge sort도 최악의 경우 O(nlogn)이었지만, 추가 배열이 필요햇음 이진 힙(binary heap) 자료 구조를 사용 O(nlogn)의 시간복잡도를 가지면서 merge sort처럼 추가적인 배열이 필요하지 않기 때문에 좋은 정렬 알고리즘 중 하나이다. Heap의 정의 Heap은 완전 이진 트리(complete binary tree)이면서 Heap property를 만족해야한다. 동일한 데이터를 가진 서로 다른 힙이 존재할 수 있다. 즉, 힙은 유일하지 않다.(같은 원소들을 가지는데 다른 위치에 가진다.) 힙은 일차원 배열로 표현가능하다. `A[1...n]1 루트 노드 : A[..

Quick Sort 정렬할 배열이 주어진다. 마지막 수를 기준(pivot)으로 삼는다. 기준(15)보다 작은 수는 기준의 왼쪽에 나머지는 기준의 오른쪽에 오도록 재배치(분할)한다. 기준의 왼쪽과 오른쪽을 각각 순환적으로 정렬한다(정렬 완료) - Algorithm 마찬가지로 quicksort도 recursion이므로 매개변수를 명시화한다. quickSort(A[], p, r) { base case; // p >= r일 때, 정렬할 데이터가 0개 또는 1개이므로 할 일 없음 if(p= x j

> 분할정복법 Divide and Conquer merge sort와 quick sort는 분할 정복 알고리즘을 사용한다 기본적으로 recursion을 사용하여 문제를 해결하는 기법이다. 아래의 세가지 단계를 거쳐서 문제를 해결한다. 분할 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할 크기는 작은 사이즈의 문제지만, 문제 자체는 전체 문제와 동일한 문제들 정복 각각의 작은 문제를 순환적으로 해결 합병 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구합 Merge Sort divide : 데이터가 저장된 배열을 절반으로 나눔 recursively sort : 각각을 순환적으로 정렬 merge : 정렬된 두 개의 배열을 합쳐 전체를 정렬 주어진 배열을 계속해서 반으로 나누다 보면 결..

> 기본 정렬 알고리즘 selection, bubble, insertion sort simple, slow Bubble sort (버블정렬) Insertion sort (삽입정렬) Selection sort (선택정렬) fast Quick sort (퀵 정렬) Merge sort (병합정렬) Heap sort (힙정렬) O(n) Redix sort Selection Sort 각 루프마다 최대 원소를 찾는다 최대 원소와 맨 오른쪽 원소를 교환한다 맨 오른쪽 원소를 제외한다. 하나의 원소만 남을 때까지 위의 루프를 반복한다. pseudo code selectionSort(A[], n){ for last input[max]) max = j; } tmp = input[i]; input[i] = input[max..

> 큐(QUEUE)란? 큐의 개념 Queue의 사전적의미는 1.(무엇을 기다리는 사람, 자동차 등의) 줄, 혹은 줄을 서서 기다리는 것을 의미한다. 따라서 일상생활에서 놀이동산에서 줄을 서서 기다리는 것, 은행에서 먼저 온 살마의 업무를 창구에서 처리하는 것과 같이 선입선출(FIFO, First in First out) 방식의 자료구조를 말한다. 큐의 특징 정해진 한 곳(top)을 통해서 삽입, 삭제가 이루어지는 스택과는 달리 큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어진다. 이 때 삭제연산만 수행되는 곳을 프론트(front), 삽입연산만 이루어지는 곳을 리어(rear)로 정하여 각각의 연산작업만 수행된다. 이 때, 큐의 리어에서 이루어지는 삽입연산을 인큐(enQueue)..

> 스택(STACK)이란? 스택의 개념 스택(stack)이란 쌓아 올린다는 것을 의미한다. 따라서 스택 자료구조라는 것은 책을 쌓는 것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다. 스택의 특징 스택은 위의 사진처럼 같은 구조와 크기의 자료를 정해진 방향으로만 쌓을 수 있고, top으로 정한 곳을 통해서만 접근할 수 있다. top에는 가장 위에있는 자료는 가장 최근에 들어온 자료를 가리키고 있으며, 삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 된다. 스택에서 자료를 삭제할 때도 top을 통해서만 가능하다. 스택에서 top을 통해 삽입하는 연산을 push, top을 통한 삭제하는 연산을 pop이라고 한다. 따라서 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 먼저..

KMP KMP알고리즘에 대해 간략히 설명 하자면, 지금까지 알려진 문자열 알고리즘 가운데 가장 최저의 시간복잡도를 가진 알고리즘이다. 일단, KMP알고리즘의 시간복잡도는 O(N+K) 여기서 N과 K는 비교할 문자열의 길이이다. 매칭을 하려면 최소한 비교대상과 타겟의 문자열을 한번씩 읽어봐야 할테니, 가장 최적의 시간복잡도이다. 알고리즘에 대한 기본적인 설명과 이해는 아래의 링크를 통해서 천천히 반복적으로 학습하는 것을 추천하고, 본인 역시 아래의 링크를 참고해서 학습한 내용에 이해에 필요한 설명을 추가하려 포스팅하려고 한다. https://m.blog.naver.com/kks227/220917078260 [ 백준 1786 ] 찾기(JAVA) 문제 링크: https://www.acmicpc.net/prob..

> 알고리즘의 분석 알고리즘의 자원(resource) 사용량을 분석 자원이란 실행시간, 메모리, 저장장치, 통신 등 여기서는 실행시간의 분석에 대해서 다룬다. 시간복잡도 실행시간은 실행환경에 따라 달라짐 하드웨어, 운영체제, 언어, 컴파일러 등 실행시간을 측정하는 대신 연산의 실행 횟수를 카운트 연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현 데이터의 크기가 같더라고 실제 데이터에 따라서 달라짐 최악의 경우 시간복잡도(worst-case analysis) 평균 시간복잡도(average-case analysis) 점근적(Asymptotic) 분석 점근적 표기법을 사용 데이터의 개수 n → ∞ 일때 수행시간이 증가하는 growth rate로 시간복잡도를 표현하는 기법 Θ-표기, Ο-표기 등을 사용..

> Recursion의 기본 개념과 예제3 Desigining Recursion 순환적 알고리즘의 설계 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 한다 모든 case는 결국 base case로 수렴해야 한다 ex - 가장 단순한 경우 if(...){ // basecase } else { // recursion } 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸어라!! 순차탐색 이 함수의 미션은 data[0]에서 data[n-1]사이에서 target을 검색하는 것이다. 하지만 검색 구간의 시작 인덱스 0은 보통 생략한다. 즉, 0은 암시적 매개변수이다. int search(int[] data, int n, int target){ for(int..

> Recursion의 기본 개념과 예제2 Recursive Thinking - 순환적 사고 Recursion은 수학함수 계산에만 유용한가? 수학함수뿐 아니라 다른 많은 문제들을 recursion으로 해결할 수 있다. 문자열의 길이 계산 순서대로 앞에서부터 하나씩 카운트 또는, 총 문자열의 길이는 첫 번째 문자를 뺀, 전체 문자열의 길이 +1(첫번째 문자)이다. if the string is empty // base case return 0; else return 1 plus the length of the string that excludes the first character; public static int length(String str){ if(str.equals("")) return 0; el..