ALGORITHMS - BASICS

코딩 테스트를 준비하기 위해 기본적인 것만 배우려고 관련 강의를 찾다가 Udemy에서 좋은 강의를 찾았다. 영어로 가르치기 떄문에 관련 영어 표현도 익히고 영어도 공부해서 더 좋다.알고리즘과 자료구조는 코딩 테스트 뿐만 아니라 성능을 최대한 잘 활용하면서 읽기 좋은 코

이번에는 문제를 이해하는 방법과 이해했으면 어떻게 해답해 다가갈것인지 설명하는 챕터이다.우선 세부사항은 빼고 핵심만 적어보려 한다. 세부사항을 확인하려면 깃헙을 확인하자.Understand the ProblemExplore ExamplesBreak it downSimp

값을 tracking할때 변수를 두가지 이상 사용하는 것을 뜻한다. 몇가지 종류의 숫자가 있는지 구하는 함수를 만들어보자i, j가 왼쪽으로 이동한다. 이동하면서 숫자가 같으면 i를 한칸 오른쪽으로 옮긴후에 j로 바꾼다. 그리고 j를 오른쪽으로 한칸 옮기고 비교를 계속한

재귀함수는 함수안에 또 자신과 같은 함수가 있는것을 말한다. 재귀 함수의 특징은 재귀를 멈추는 조건문이 있어야 하고, 재귀 함수 안에 들어갈 인자가 달라야 한다는 것이다. 맨처음엔 다소 생소하지만 언제나 그렇듯 계속 마주치면 익숙해진다.하지만, 콜스택에 계속 쌓이기 때

먼저 간단하게 팩토리얼을 구하는 함수부터 만들어 보자.if 문이 base case이고 num-1이 다른 인자를 입력하는 것이다. 좀더 복잡한 재귀함수를 살펴보자.아래는 펠린드롬 함수이다. 앞뒤 어느쪽으로 읽어도 발음이 같은 단어를 뜻한다.그 전 글에서도 설명했지만 어떤

무작위로 담겨있는 데이터를 어떤 기준에 의해서 정렬해주는 알고리즘을 말한다. bubble, selection, insertion, merge, quick 등 정말 많은 방법으로 정렬가능하다. 다 설명할 수 는 없고 내가 생각했을때 재밌고 유용하다는 알고리즘만 설명하겠다

이제 부터 본격적으로 데이터를 담는 데이터 구조에 대해서 알아보자. 데이터를 담는 방법은 정말 다양하다. 변수에 담을 수 도 있고 array 에 담을 수 도 있고 객체를 이용해서 key/value의 형태로 담을 수 도 있다.이번에는 객체를 이용해서 담아보려고 한다. 정

사실 단일 연결이랑 코드는 크게 차이 나지는 않는다. 다만 포인터가 앞으로도 , 뒤로도 연결된다는 차이가 있을뿐. 그래서 이중 연결 리스트를 만들 때 양쪽 다 연결되도록 하는것이 중요하다.Almost identical to Singly linked list, excep

stacks은 쉽게 말해 상자라고 생각하면 된다. 우리가 상자에 책을 차곡차곡 넣는다고 하자. 이때 처음에 들어갔던것은 맨 마지막에 나올 수 있다. 그리고 마지막에 들어간것은 제일 처음 나온다. 그래서 일반적으로 array처럼 활용가능하다.보통 debugging 할때

이름만 들어서는 무슨 말인지 잘 모르겠다. 이 자료구조의 경우에는 영어가 더 편한것 같다.(이하 BST)BST에 대해서 간략하게 개념을 정리해 보았다.\-- TerminologyRoot / Child / Parent / Siblings / Leaf / Edge(arro

사실 이 메소드는 강의에는 없었지만 내가 직접 만들어보기로 했다. 그리고 해냈다!! 직인다 진짜.그럼 로직을 살펴보자.BST delete pesudocode\-- accepts the value\-- use find method to remove the valueass

이번에는 TREE를 가로지르는 방법에 대해서 설명해보겠다. 기본적으로는 두가지 방법이 있다. 수평으로 가로지르는 방법이랑 수직으로 가로지르는 방법이다. 이번에 배울것은 BFS인데 형제NODE를 먼저 방문하고 나서 그 밑의 자식으로 가는 방법이다. 그럼 로직을 살펴보자.

Binary Heap(이하 BH)은 BST보다 간단하다. MAX인지 MIN인지에 따라서 부모가 자식보다 크냐 아님 작으냐로 구분하기만 하면 된다. 형제노드사이의 관계는 전혀 없다. 그냥 부모보다 작으면 된다. 그럼 영어로 설명을 적어보겠다.Binary heap\-- V

BH를 이용해서 우선순위를 정하고 가장 급한것을 먼저 처리하는 프로그램을 의미한다. 일단 상황을 정하자. 지금 우리는 응급실(ER)에 와있다. 환자별로 증상과 응급정도를 표시해서 분류한다음 가장 급한사람이 먼저 치료받도록 해야한다고 하자. 이때 응급정도의 숫자가 낮을

사실 hash table은 독립적인 섹션이라 깊게 배우지는 않고 그냥 개념만 짚고 넘어가려고 한다.What is a Hash table?Hash tables are used to store key-value pairs.They are like arrays, but th

What is it?Bunch of nodes or points connected together without hierarchy. they are all treated equally.Terminologyvertex: node.(이하 vtx)edge: connectio

tree의 DFS는 직관적으로 알겠는데 Graph의 DFS는 명확하게 다가오지 않는다. 여기서 말하는 DFS는 한 방향으로 나아가는 것을 뜻한다. 우선 이전의 만들었던 method를 이용해서 Graph를 간단하게 만들어보자.Adjacency List 로 저장되는 것을

맞다. 그 유명한 다익스트라 알고리즘이다. 최단거리를 찾아가는 과정이다. 그리디 알고리즘의 한 종류이기도 하다.다익스트라라는 네덜란드 프로그래머가 20분동안 심심풀이로 암스테르담에서 다른역까지 가는 최단거리를 계산하려고 끄적이다가 만들어낸 알고리즘인데 전세계적으로 굉장

우선 이런 복잡한 프로그램을 작성하려면 뭐부터 시작해야할지 막막하다.이때 글로 먼저 해야할 것들을 작성해보는것을 강력 추천한다. 언제나 그렇듯 pseudocode를 작성해보자.Pseudo codeSetupThis function should accept a starti

동적 프로그래밍(이하 동프) 이라는 말이 직관적이지는 않다. 동프가 도대체 뭘까? 영어 설명을 살펴보자.WTF is Dynamic programmingA method for solving complex problem by breaking it down into a co

알고리즘 문제를 여러개 풀어보고 발견한 접근법을 매우 간단하게 나름대로 정리해보았다.핵심은 전개되는 과정을 그림이나 표로 나타내기!그리고 시각화된 과정을 보고 반복되는 패턴을 찾기그 패턴을 공식화 하는 방법을 알아내기!이 링크 를 클릭하면 이 법칙을 어떤식으로 적용할지