이누의 개발성장기

다이나믹 프로그래밍 다이나믹 프로그래밍이란 어떤 문제를 해결하는 것에 있어, 중복적인 계산을 최대한 피하는 방법이다. (2*5) + (2*6)의 문제를 해결할 때를 생각해보자. (2*5)만 알면 (2*6)은 (2*5 + 2)로 해결할 수 있다. 따로 (2*5)를 또 계산할 필요가 없이 미리 해결한 (2*5)의 결과값을 이용한 것이다. 이것이 다이나믹 프로그램의 핵심이다. 문제가 더더욱 복잡하고 중복되는 계산이 많은 상황에서는 여러 계산과정을 생략할 수 있어 유용할 것이다. 좀 더 자세히 살펴보자. 다이내믹 프로그래밍의 조건 1. 최적 부분 구조 : 부분 문제의 최적의 답을 통해 상위문제(기존문제)의 최적의 답을 구할 수 있다. ex. 피보나치 수, fib(n) = fib(n -1) + fib(n - 2)..

특정 리스트를 정렬하는 방법에는 여러 가지가 있다. 그중에서도 대표적으로 분할 정복을 활용하여 리스트를 정렬하는 것이 합병 정렬, 퀵 정렬이다. 그 중 퀵정렬에 대해 알아보자 퀵 정렬 합병 정렬의 combine단계에서는 크기를 비교해가며 새로운 리스트를 생성했다. 즉, 합병 정렬은 combine단계에서 많은 과정을 수행한다. 하지만 퀵 정렬은 이와 다르게 divide에서 많은 과정을 수행한다. 퀵 정렬의 과정 퀵 정렬은 주로 기준점으로 삼을 임의의 성분을 필요로 한다. 주로 대상 리스트의 제일 마지막 성분을 사용한다. 이를 pivot이라고 부른다. 이 pivot을 기준으로 더 작은 성분은 모두 왼쪽으로, 더 큰 성분은 모두 오른쪽으로 이동한다. (divide) 그리고 왼쪽의 리스트와 오른쪽의 리스트를 각..

분할정복 (Divide and Conquer) 이는 재귀함수에 대한 명확한 이해가 필요한 파트이다. 재귀함수가 부족하다고 생각하면 좀 더 공부를 해놓고 학습을 하는 것이 좋겠다. 분할정복은 이름 그대로 문제를 분할하여 해결하는 것이다. 이는 총 3단계로 구성된다. 1. Divide : 문제를 나눈다. 2. Conquer : 나눠진 문제를 각각 해결한다. 3. Combine : 각각 해결한 두 문제의 답을 결합한다. 여기서 생각해야 될 것은 분명 우리는 어떤 문제를 해결하기 위해 분할정복을 시작했다. 그런데 여기서 2번단계를 보면 '나눠진 문제를 각각 해결한다' 라고 한다. 이 말은 결국 무엇이겠는가? 이 2번 단계에서 나눠진 문제에도 각각 분할정복을 적용할 수 있다는 뜻이다. 그리고 당연하게도 그렇게 2..

그래프에서 어떤 노드에서 어떤 노드로 가는 경로 중 가장 짧은 경로를 찾는 알고리즘은 여러 조건에 따라 방법이 다양하다. 그 중 BFS를 이용하는 방법과 Dijkstra에 대해 알아보자. BFS를 이용한 최단 경로 알고리즘 BFS에서 각 노드에 멤버변수로 predecessor를 추가한다. 해당 멤버변수에는 해당 노드가 어떤 노드로부터 왔는지 기록된다. 즉, Root노드를 제외한 모든 노드들은 BFS를 할 때 특정 노드에서부터 탐색되어져 나온 것이므로, 이를 기록하는 것이다. 이 결과로 특정 노드에서 predecessor를 따라 거꾸로 올라감으로서 특정 노드로 가는 최단의 경로를 알 수 있다. 이를 특별히 backtracking이라고 부르기도 한다. 단, 이는 주로 root노드를 출발점으로 보았을 때 사용..

그래프란 연결 관계를 가지는 자료구조이다. (연결구조의 예 : 지하철역들 사이의 연결여부, 거리수치) 링크드 리스트와 같이 노드를 성분으로 가진다. 그래프 기본 노드들 끼리 직접 연결되어 있을 경우 이 연결관계선을 '엣지'라고 한다. 예를 들어 A와 B사이에 연결관계가 존재하면 이는 'A와 B사이의 엣지'이며, (A,B) 혹은 (B,A)로 표기한다. 직접 연결된 두 노드는 '인접'했다고 한다. 한 노드에 연결된 노드의 개수를 '차수'라고 한다. 어떤 노드에서 어떤 노드까지 가는데에 필요한 엣지들을 '경로'라고 한다. 경로는 충분히 여러개일수 있는데, 그 중 제일 짧은 경로를 '최단 경로'라고 한다. (cf. 경로는 아예 존재하지 않을 수도 있다.) 방향 그래프 앞서 설명한 그래프에서 '엣지'는 방향이 존..

https://flatuicolors.com/ Flat UI Colors 2 - 14 Color Palettes, 280 colors 🎨 280 handpicked colors ready for COPY & PASTE flatuicolors.com 많은 컬러코드를 한눈에 확인하고 복사할 수 있도록 만들어진 사이트이다. 재미있는 점은, 색감별로 Palette를 나눠놨다는 점이다. Palette를 고르고 원하는 색을 고르면 바로 컬러코드가 복사된다.

https://developer.mozilla.org/ko/docs/Web/Events 이벤트 참조 DOM 이벤트는 발생한 흥미로운 것을 코드에 알리기 위해 전달됩니다. 각 이벤트는 Event 인터페이스를 기반으로한 객체에 의해 표현되며 발생한 것에 대한 부가적인 정보를 얻는데 사용되는 추가적인 커스텀 필드 또는 함수를 가질수도 있습니다. 이벤트는 렌더링 모델에서 기본적인 사용자 인터렉션부터 발생한 것에대한 자동 알림까지 모든 것을 나타낼 수 있습니다. developer.mozilla.org 마우스 이벤트뿐만 아니라, 그 외에도 다양한 이벤트가 저장되어 있다. 웹사이트를 제작할 때 유용하게 사용할 수 있을 것같다.

이진 탐색 트리 왼쪽 트리에는 자신보다 작은 크기의 데이터를 가지는 노드들만, 오른쪽 트리에는 자신보다 큰 크기의 데이터를 가지는 노드들만 저장하는 이진트리이다. 따라서 데이터를 찾을 때 데이터가 현재 노드의 데이터보다 작다면 왼쪽으로, 크다면 오른쪽으로 향하면 된다. 완전 이진트리는 아닐 수도 있기 때문에 배열이나 리스트를 활용할 수는 없다. 따라서 노드 정보를 가질 수 있는 node 클래스를 만들어서 사용한다. 이 클래스는 데이터정보,부모노드정보,좌측자식노드정보,우측좌식노드정보를 가져야 한다. 그리고 좀 더 쉬운 관리를 위해 root노드 정보를 가지고 있는 tree클래스도 만들어준다. 이전에 배운 in-order순회대로 이진 탐색트리를 출력하면 데이터의 크기 순서대로 데이터가 출력될 것임을 짐작할 수..

힙 힙은 트리의 일종이다. 단, 힙은 완전 이진트리여야만 한다.(형태 속성, 모든 노드가 2개의 자식을 갖고, 마지막 레벨에서만 왼쪽에서 오른쪽으로 노드가 순차적으로 채워져 있음) 따라서 노드의 개수가 n일 때힙의 높이는lg(n)이고, 리스트로 트리를 표현할 수 있다. 그리고 모든 노드의 데이터는 자식 노드의 데이터보다 크거나 같아야 한다. (힙 속성) 힙정렬 이러한 힙을 사용해서 데이터를 정렬할 수도 있는데, 이를 '힙정렬' 이라고 부른다. 힙은 일종의 완전 이진트리이므로, 리스트로 표현이 가능하다.(트리파트 참고) 이 말은 즉, 리스트를 힙으로 표현할 수도 있다는 것이다. 다만 힙은 부모노드의 데이터가 자식 노드의 데이터보다 커야 하므로, 이 조건을 만족시켜야 한다. 그렇지 않은 리스트를 힙 조건에 ..

git 프로젝트에서 소스코드만 추출하고 싶을 때 사용한다. git bash를 열고 [git archive --format=zip master -o Master.zip]이라고 입력하면 폴더내에 Master.zip 파일이 생성된 것을 확인할 수 있다. (저는 연습용으로 현재 제가 진행중인 파이썬 기초 100제 깃을 사용했습니다.) 파일 내부를 확인해보면 git에 관련된 파일을 제외하고 소스코드 관련파일만 잘 압축되어 있다.