BFS를 사용하되, 매 루프마다 한 칸씩 이동하는 대신, 갈 수 있는 만큼 최대한 한 방향으로 이동한다. 또 visited 칸을 저장하는 대신, 한 번 지나간 칸에 대해 해당 칸으로 가기 까지 필요한 거울의 갯수(count)를 기록한다. 즉 count != 0 이라면 한 번 이상 방문한 칸인 셈이다. BFS를 사용하기 때문에, 어느 칸에 처음 방문했을때 그 칸까지 가는 최단거리(여기서는 최소한으로 사용되는 거울 갯수)를 바로 알 수 있으며, 이러한 성질을 활용해 거울의 갯수를 축적시켜 최종적으로 목적지에 도달할때까지 길을 찾는 방식이다. (굉장히 다양한 풀이가 존재하지만 이 풀이가 가장 깔끔하고 직관적인 풀이법이라고 생각한다.) #include #include using namespace std; cha..
문제에서 찾아내기 어려운 부분들: 1. 매일매일 마다 백조를 시작지점부터 BFS를 돌려 길을 찾는 것은 낭비이다. 백조가 충돌한 얼음은 다음 날 녹는다. 때문에 이를 기록해두었다가 다음날 시작지점으로 사용하면 된다. 2. 얼음을 녹일 때는 "얼음을 기준으로 주변을 살피기" 가 아니라 "물을 기준으로 주변을 살피기"가 훨씬 효율적이다. 어차피 물과 닿아있어야 녹기 때문이다. 때문에 얼음의 위치를 기록하기보다는 물의 위치를 기록하는 편이 더 좋다. 참고: 인풋을 텍스트 형태로 받기 때문에 2d 그리드를 제작할 때 2d 벡터 대신 벡터 내에 string객체를 저장하는 방식을 사용한다. #include #include #include #include #include using namespace std; int ..
C^n을 구할 때 이를 O(N)으로 구하는 방법은 굉장히 간단하다. for 문을 돌리며 결과값에 C를 n번 곱해주면 된다. 그러나 C^n은 O(log n)의 시간복잡도로도 구할 수 있는데, 바로 분할 정복법을 사용한 풀이이다. #include using namespace std; int pow(int a, int k) { //a^k, k>0 if (k == 0) { return 1; } else if (k == 1) { return a; } else if (k == 2) { return a * a; } else { if (k % 2) { return pow(a, (k - 1) / 2) * pow(a, (k - 1) / 2) * a; } else { return pow(a, k / 2) * pow(a, k..
우선 nCk를 구하는 방법은 굉장히 다양하다. Brute force n! / k! * (n - k)!의 성질을 이용해 구하는 방법이 대표적인데, 이는 for문을 두번 돌리고 그 두 값을 서로 나눠주는 것으로 구현이 가능하다. ex. 6C2 = (6 * 5) / (2 * 1) 재귀와 DP 그러나 숫자가 커지면 팩토리얼값이 long long에도 저장하기 어려울 만큼 커질 수 있다. 이를 방지하기 위한 두번째 방법이 파스칼의 삼각형을 이용한 방법이다. 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 파스칼의 삼각형을 C라는 2차원 그리드라고 생각하면, C(a, b)는 C(a-1, b-1) + C(a-1, b)임을 알 수 있다. 즉 바로 윗칸 + 왼쪽 윗칸을 더한 값이 해당 칸의 값인 셈이다. (빈칸은 0..
백준 12865 #include #include using namespace std; int arr[101][100001] = { 0 }; int weights[101]; int values[101]; int main() { int n, k; cin >> n >> k; for (int i = 1; i > weights[i] >> values[i]; // 맨 윗줄은 0으로 채워두고 시작. } for (int i = 1; i = weights[i]) { arr[i][j] = values[i] + arr[i - 1][j - weights..
분할 정복법 분할 -> 정복(풀이) -> 조합의 과정을 통해 하나의 큰 문제를 여러 개의 작은 문제로 분할하고 풀이한 후 재조합하는 접근방식. 분할 정복법을 사용하는 알고리즘으로 병합 정렬(merge sort)과 퀵소트(quick sort)가 있다. 재귀함수를 사용하는 특성 상 메모리 소모가 막심해질 수 있다. 분할 정복법의 사용 조건 1. 문제를 작은 여러 개의 Sub-problem들로 쪼갤 수 있어야 함. 2. Sub-problem들의 결과를 합쳐 큰 문제에 대한 답을 구할 수 있어야 함. function F(x): if F(x)가 간단 then: return F(x)를 계산한 값 else: x 를 x1, x2로 분할 // x1, x2 = G(x)처럼 값을 분할하는 함수를 별도로 제작하는 경우도 많다..
**개인 필기용 글이라 두서가 없을 수 있습니다. 선택 정렬 활용도 낮음 배열을 스캔해 가장 작은 수를 맨 앞으로 가져다 놓는다. 맨 앞칸을 제외한 나머지 배열을 스캔해 해당 배열에서 가장 작은 수(전체에서 두번째로 작은수)를 맨 앞으로 가져다 놓는다. 더 스캔할 배열이 없을 때까지 위 과정을 반복한다. 버블 정렬 활용도 낮음 1번째 인덱스부터 정렬을 시작한다. (n = 1) 인덱스 n, n+1을 비교한다. n > n+1 이면 서로 위치를 바꾸고(swap), 아니면 n을 1 증가시킨다. 이렇게 n이 array.length() - 1 까지 도달하면 이 과정을 처음부터 다시 반복한다. 루프 한 번을 도는 동안 단 한차례도 swap이 일어나지 않았다면 정렬이 완료된 상태이다. 삽입 정렬 활용도 낮음 2번째 인..
**개인 필기용 글이라 두서가 없을 수 있습니다. 최단 경로 알고리즘 다익스트라 노드들의 cost INF로 초기화한다. 현재 노드 cost + 인접 노드와의 거리 < 인접 노드의 cost 일 경우 인접 노드의 cost를 전자의 값으로 변경한다. 인접한 모든 노드를 다 방문했다면 다음 노드로 이동한다. 이때 다음 노드를 결정하는 방법으로는 BFS, DFS도 쓸 수 있지만 그리디 알고리즘을 통해 최적화하는 것이 일반적이다. (즉 가장 cost가 낮은 노드를 다음 노드로 설정) 목적지 노드에 도착했다면 해당 노드의 cost가 최단 거리이다. (만약 최단 경로를 구하고 싶다면 각 노드마다 부모 노드를 기록한 후 목적지 노드에서 재귀함수로 경로를 역추적하면 된다.) 더보기 다익스트라는 이차원 배열로 구현할 수도 ..
=== vs == == 는 두 비교대상을 서로 비교할 수 있도록 강제 형변환을 하지만, ===는 형변환을 하지 않는다. 때문에 가급적 ===를 사용하는 것이 권장된다. (형변환이 명시적일수록 좋은 것은 다른 언어에서도 마찬가지이다) // == 1234 == '1234' // true true == 1 // true undefined == null // true 'hello' == new String('hello') // true null == false // false 'true' == true // false true == 2 // false // === 1234 === '1234' // false true === 1 // false undefined === null // false 'hello' ==..
어떤 함수 내부에서 this는 해당 함수의 호출 시점에서 그 함수를 프로퍼티(property)로 가지는 객체를 의미한다. function sayName () { console.log(this.name) } var john = { name: 'John', sayName: sayName } var eddie = { sound: 'Eddie', sayName: sayName } john.sayName() // John eddie.sayName() // Eddie 더보기 참고: medium.com/@nemo1275/this%EA%B0%80-%EB%AD%90%EC%A3%A0-81698d54c808
Arrow function은 코드를 간결하게 만들어주는 역할을 해준다. //ex1. 파라미터 2개 이상 function sum(a, b) { return a + b; } let sum2 = (a, b) => { return a + b; } let sum3 = (a, b) => a + b //ex2. 파라미터 1개 function isPositive(number) { return number >= 0; } let isPositive2 = (number) => { return number >= 0; } let isPositive3 = number => number >= 0 //ex3. 파라미터 없음 function randomNumber() { return Math.random } let randomNumb..
참고: Template literal ` (물결 문자 아래) 를 사용해 Template literal을 작성할 수 있다. 이는 일반적인 문자열과 유사하게 동작하며, 파이썬의 fstring과도 상당히 유사하다. ex. var s = 'John'; var k = 'Mary'; console.log(`Hello ${s}, this is ${k}`); 1. 생성자 (es5) 생성자 함수를 작성해 객체지향적 프로그래밍이 가능하다. 이때 생성자 함수는 다른 객체지향 언어들처럼 클래스 내의 메소드로 있는게 아니라, 그냥 함수 형태로 존재한다. function Book(title, author) { this.title = title; this.author = author; } var book = new Book('aa..
