컴퓨터를 공부하고자 마음먹은지 N일차

동적프로그래밍 동적 프로그래밍이란 유기적으로 연산한값이나 데이터를 저장하면서, 메모리에 할당을하며 연산 횟수를 줄이는 프로그래밍 기법이다. 한가지 예를들면 2의 n제곱을 구하는 연산에서, 2의 8제곱을 구할 때 2의 7제곱을 구했던 값이 데이터에 남아있다면, 2를 8번 곱할 필요가 없이 2의 7제곱한 값에다 * 2 라는 연산만 해주면된다. 이런식으로 2의 제곱을 불러와봤다. 총 5번의 계산을 했고, 이번엔 2의 6제곱을 구해보라고 해볼거다. 보다시피 자기는 계산 딱 한번했다고 나온다. 귀엽지않은가? 문제풀이로 dp를 많이 접할거다. 핵심은 데이터를 어떤방식으로 할당하면서 문제를 해결해나갈지 중점에 달려있다. 이름은 dynamic programing이지만 그다지 다이나믹하지않다는게 함정이다 memoziat..

힙 자료구조 힙은 우선순위 큐를 위해서 만들어진 특별한 자료구조다. 이진 탐색트리와 유사한 모양을 가지고 있는데, 힙은 중복된 값을 허용하지 않는다. 또, 힙은 완전 오름차순 형태로 정렬된게 아닌 불완전 정렬상태 이다. 우선순위 큐의 활용 사례로는, 게임엔진에서 각 액터의 우선순위를 정한다. 서버에서 많은 트래픽을 처리 할 때 우선처리해야할 트래픽을 정한다. 다른 활용도 있는데, 이건 내가 문제를 풀거나 해봐야 할것같다. 힙으로 우선순위큐를 구현하는 이유는 나중에 들어온 값이라도 우선순위를 줄 수 있기 때문이다. 힙자료구조의 중점은, 왼쪽 노드부터 삽입하고 값에 따라 부모자식 관계가 바뀌지 좌우가 바뀌지않는다. 자식노드는 부모보다 최대힙(큰거우선)일때 같거나 작으면되고, 최소힙(작은거우선)일때 크거나 같..

12345678910111213141516/* 프로그래머스 k번째 수 */function solution(array, commands) { var answer = []; //commands 배열을 순회한다. //더미를 선언하고 arr.slice(0번째인덱스값 - 1, 1번째인덱스).sort(a - b); //더미[2번째인덱스값 - 1]을 정답배열에 푸쉬한다. for(let command of commands){ let dummy = array.slice(command[0] - 1, command[1]).sort((a, b)=>a - b); answer.push(dummy[command[2] - 1]) } return answer;}/* test */console.log(solution([1, 5, 2, ..

퀵정렬 알고리즘 퀵정렬 알고리즘 또한 합병정렬과 마찬가지로 분할정복법이다. 임의의 수를 기준으로 좌 우측으로 나누는걸 반복 한다. 같은 분할정복법인 합병정렬 과 비슷해 보일 수 있다. 퀵정렬을 설명하는 수도코드는 단 두줄이다. 기준, 기준보다 큰 수는 기준의 좌측, 기준보다 큰 수는 기준의우측으로 배열을 정렬한다. 그 좌측 우측에다 재귀적으로 1번을 적용한다. 방식이 어떻게 흘러가는지 그림으로 알아보자. 요런 배열이 있다. 0번째 인덱스를 기준으로 작은수는 왼쪽 큰수는 오른쪽 으로 정리해보자. 이동하는 방법이 복잡하다. 순서가 있는데, 기준을 정한다 0번째인덱스가 국룰. 비교할 수의 인덱스는 길이 - 1 (끝인덱스) 부터 자리교체가 일어나지 않았을 때만 인덱스가 감소한다. 작으면 왼쪽에다 보낸다 이 보내..

병합정렬 알고리즘 합병정렬은 맨해튼 프로젝트에 참여했던 폰노이만이 제안한 방법이다. 시간복잡도를 최악의경우에도 O(n log n)만큼 줄이는 방법인데, 기존 정렬알고리즘보다 확연히 줄어든다. 또 간단하다 합병정렬에는 크게 두가지 역할을 수행해야된다. 좌 우를 기준으로 재귀적으로 나누기 좌 우에다가 정렬된 두 배열을 합치는 함수 적용하기 나는 이 원리가 이해됐지만 처음 배웠을 땐 도저히 배열의 길이가 짝수일 때는 어떻게 해? 라는 의문을 풀어낼 수 없었다. 그래서 썼던 방법이 있는데 그림이나 종이로 숫자카드를 그리고 정렬 해보기였다. 1. 좌 우를 기준으로 재귀적으로 나누기 아래와 같은 배열이 있다. 이걸 딱 반틈만큼 잘라줘야 하는데, 배열의길이가 보다시피 홀수이다. 나누기 2를하면 4.5이고 뒤에 소수점..

이진탐색 알고리즘 이진탐색은 간단히 구현할 수 있으면서도, 배열을 전부 순회 하지않고 원하는 값을 찾을 수 있는 강력한 알고리즘이다. 검색원리상, 정렬된 배열에서만 찾을 수 있지만, 찾는 속도가 매우 빠르다 원리 밑 그림과 같이 오름차순으로 정렬된 배열이 있다. 아래 배열에서 찾는값은 21 처음 임의의 중간값을 고른다. 14는 21보다 작으므로 고른값의 오른쪽에 찾는값이 있다는걸 알 수 있다. 그러면 찾을 범위가 4번째인덱스부터 6번인덱스로 줄어든다! WOW! 이 찾을 범위에서 가운데 임의값을 꺼내서 찾는값과 비교한다. 단 두번의 검색으로 원하는 값을 찾았다! 원리를 알았으니 코드로 구현해보자. 자바스크립트 코드 12345678910111213141516171819202122232425const bina..

거품정렬 거품정렬은 원소이름이 거품이 수면위로 올라오는것 처럼 정렬이 되어가기 때문에 붙여진 이름이다. 거품정렬을 이해하는데에는 이만한 춤영상 이 없다. javascript 코드 1234567891011121314151617181920212223242526const bubbleSort = function (arr) { // TODO: 여기에 코드를 작성합니다. // 배열이 정렬이 덜됐는지 확인해주는 boolean타입값을 true로 선언한다. // 순서대로 정렬되어 있을 때 까지 반복한다 boolean이 true일때 //boolean값을 false로 설정한다. //배열의 길이만큼 반복한다 //i번째 인덱스가 i + 1 번째 인덱스보다 크면 //자리를 바꾼다 //boolean값을 true로 설정한다. // ..

그래프 너비 우선 탐색법 너비 우선탐색은 깊이탐색과 함께 등장하는 탐색방법이다. 깊이우선탐색은 갈수있는데까지 깊이 갔다오는걸 반복한다면, 너비우선 탐색은 갈수있는 길목을 한단계씩 차례대로 가보는거다. ex)깊이우선탐색 깊이우선탐색설명 ex)너비우선탐색 보다시피 깊이우선탐색은 일단 깊이 찌르는것과 달리 갈수있는 길목을 한칸씩만 가고 다음길목으로 가서 또 갈길을 체크한다. 갈수있는 길목을 순차적으로 살피게 해줄 도구가 필요한데, 바로 큐 자료구조를 이용하는것이다. 이해를 돕기위해 숫자 순서를 섞는다. bfs도 순서를 나열하면 간단하다. 1. 현재 위치한곳에 방문기록을 표시한다. 2. 디큐한다. 3. 갈 수 있는 길목중에 방문한적이 없고 큐에 없는 노드를 인큐한다. 4. 큐에있는 노드들을 bfs(재귀)한다. ..