문제 설명 빙하가 깨지면서 스노우타운에 떠내려 온 죠르디는 인생 2막을 위해 주택 건축사업에 뛰어들기로 결심하였습니다. 죠르디는 기둥과 보를 이용하여 벽면 구조물을 자동으로 세우는 로봇을 개발할 계획인데, 그에 앞서 로봇의 동작을 시뮬레이션 할 수 있는 프로그램을 만들고 있습니다. 프로그램은 2차원 가상 벽면에 기둥과 보를 이용한 구조물을 설치할 수 있는데, 기둥과 보는 길이가 1인 선분으로 표현되며 다음과 같은 규칙을 가지고 있습니다. 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다. 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다. 단, 바닥은 벽면의 맨 아래 지면을 말합니다. 2차원 벽면은 n x ..

1. 위상 정렬 위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. [그림 1]을 보자. [그림 1]은 임의로 만든 마법사로 전직을 한후 배워야하는 스킬의 관계도다. 각 스킬에 대한 관계도를 정리하면 다음과 같다. 에너지 볼트는 맨 처음에 배우는 기본 마법이다. 매직클로를 배우려면 에너지볼트를 먼저 배워야한다. 메테오를 배우려면 먼저 매직클로, 텔레포트를 배워야한다. 마력 흡수를 배우려면 먼저 에너지 볼트를 배워야한다. 텔레포트를 배우려면 먼저 마력흡수, 매직클로를 배워야한다. 이러한 흐름은 조건을 걸어줘서 해석할 수 있다. 먼저 마법사로 전직하면 에너지 볼트를 찍고, 그 다음엔 마력 흡수 또는 매직클로를 찍는다. 그리고 텔레포트를 찍고 최종적으..

1. 플로이드 와샬 알고리즘 지난 번에 포스팅했던 다익스트라 알고리즘은 하나의 정점을 출발점으로해서 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 그런데 이번에 포스팅할 플로이드 와샬 알고리즘은 모든 각각의 정점을 출발점으로해서 모든 정점까지의 최단경로를 구하는 알고리즘이다. 하나의 정점을 출발하는 것이 아니라, 그래프에 있는 모든 각각의 경로에 대한 최단경로를 구하기 때문에 시간복잡도는 O(N³)이다. 또한 플로이드 와샬 알고리즘은 거쳐가는 정점을 기준으로 알고리즘을 수행한다. 이게 무슨 말인지 감이 안오더라도, 지금부터 하는 설명을 들으면 어떤 순서로 알고리즘이 수행되는지 알 수 있을 것이다. [그림 1]은 그래프의 각 정점에 대한 가중치를 순차자료구조로 변환한 것이다. 먼저 출발 정점을 A로 설..

1. typeof typeof 연산자는 피 연산자의 자료형을 나타내는 문자열을 반환하는 함수다. console.log(typeof 42); // number console.log(typeof "str"); // string console.log(typeof true); // boolean console.log(typeof false); // boolean console.log(typeof function(){}) // function console.log(typeof {}); // object console.log(typeof []); // object 참조 타입이든 원시 타입이든 자료형을 나타내는데 크게 문제가 없는 것 같다. 하지만 typeof의 문제점은 null의 자료형을 나타내는 문자열을 반환하는..

1. 문제 설명 2. 제한 조건 3. 입출력 예 4. 나의 풀이 쉽게 생각했다가 큰 코 다친 문제다. 예상치 못했던 테스트 케이스 10에서의 시간 초과는 멘붕 그 자체였다. 그런데 이 문제가 탐욕법이라는 범주안에 있는 것을 생각해보면, 이 문제는 정말 탐욕법스러운 문제라 할 수 있을 것 같다. 이제 풀이를 시작하도록 하겠다. 이 문제가 물어보는 메세지를 파악하는 것이 중요하다. 이 문제의 메세지는 어떤 숫자에서 k개의 숫자를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하라 이다. 테스트 케이스 10(시간 초과)을 해결할 수 있었던 것은 내가 짰던 코드의 방향을 아예 바꾸는 것이었다(다른 블로그(참고 자료 출처)를 참고했다). 기존에 풀던 방식은 투 포인터를 이용하는 것이었다. 방법은 다음과 같다. 입력..

1. 다이나믹 프로그래밍 다이나믹 프로그래밍이란, 하나의 문제를 단 한번만 풀도록 하는 알고리즘이다. 이전에 나는 퀵 정렬, 병합 정렬, 이진검색과 같은 자료구조를 포스팅한 적이 있다. 이 셋을 언급한 이유는 분할 기법을 이용하기 때문이다. 퀵 정렬, 병합 정렬, 이진검색은 분할 기법을 이용해서 평균 시간복잡도 O(Nlog₂N)이라는 굉장히 빠른 속도를 장점으로 가질 수 있었다. 하지만 되게 빨라보이는 분할기법도 어떤 상황에서는 단점이 존재하는데, 그것은 바로 동일한 문제를 반복해서 푼다는 것이다. 그 대표적인 예시가 피보나치 수열이다. 피보나치 수열은 제 0항, 제 1항을 1로 제쳐두고 두 번째 항부터는 앞에 두 수를 더한 값을 결과로 두는 수열을 말한다. 피보나치 수열은 보통 프로그래밍 언어에서 재귀..