투투

https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 접근 1번 마을에서 다른 마을로 배달을 갈 때 K시간 이하가 걸리는 마을의 개수를 구해야 한다. 따라서 하나의 노드에서 다른 모든 노드까지의 최단 거리를 구하는 다익스트라 알고리즘을 이용하여 풀었다. 먼저 마을과 마을 간의 연결 정보가 담긴 road를 통해 그래프를 그려주었다. 이후 다익스트라 알고리즘을 통해 1번 마을에서 시작해서 다른..

함수형 프로그래밍에서 if문과 for문 사용을 지양해야 한다고 책에서 읽고 공부를 하였다. 하지만 왜 그래야 하는 것인지 오랫동안 이해되지 않았고 시간이 지난 후에 다시 함수형 프로그래밍에 대해서 공부를하니 조금씩 이해가되어 정리를 하려고 한다. 10명의 사람들이 있다고 가정해보자. 여기서 각 사람들의 나이와 이름을 알고있고 10명의 사람 중에서 20살 이상인 사람들의 이름을 알아보려고한다. 이를 코드로 작성해보고 함수형 프로그래밍을 발전시키면서 if문과 for문을 왜 사용하면 안되는지 이해해보자. const personList = [ { age: 17, name: "alex" }, { age: 15, name: "paul" }, { age: 21, name: "harry" }, { age: 27, na..

자료구조 힙에 대한 개념을 알아보고 완전 이진 트리를 통해 최소힙과 최대힙을 구현해보자. 들어가기전에 먼저 힙에 대해 알아보기 전에 완전이진트리의 개념을 상기시킬 필요가 있다. 힙은 완전이진트리의 형태이기 때문이다. 아래의 그림은 포화이진트리를 나타낸 것이다. 포화이진트리는 리프 노드를 제외한 모든 노드들이 2개의 자식 노드들을 갖고있는 트리이다. 포화이진트르의 노드 개수는 높이가 h 일 때 2^(h+1) - 1이 된다. 아래의 그림은 완전이진트리를 나타낸 것이다. 위의 포화이진트리에서 가장 오른쪽에 있는 리프노드를 제거한 모습이다. 이처럼 완전이진트리는 왼쪽부터 빈틈없이 채워나간 트리를 의미한다. 아래의 그림은 완전이진트리가 아니다. 왜냐하면 왼쪽 리프노드에 빈 칸이 존재하기 때문이다. 완전이진트리는 ..

https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 접근 N이 1부터 3일 때 경우의 수를 먼저 구하였다. 각각의 크기에서 사자를 0마리, 1마리, 2마리 등을 놓을 수 있을 때로 나누어 계산을 하였다. 그 결과는 다음과 같다. N=1 -> 1 + 2 = 3 N=2 -> 1 + 4 + 2 = 7 N=3 -> 1 + 6 + 8 + 2 = 17 N=4 -> 41 여기서 규칙을 구할 수 있었다. 현재 N이 i일 때의 경우의 수를 구할 때 i-1번째 경우의 수 x 2 + i-2번째 경우의 수를 하면 i번째의 경우의 수가 나왔다. 구현 - 먼저 N이 1일 때와 2일 때의 경우의 수를 저장하..

자바스크립트의 객체를 사용할 때 언제 사용할 수 있는 객체인지 아니면 환경에 제약없이 사용할 수 있는 함수인지를 파악하고 있어야 한다. 네이티브 객체 네이티브 객체는 ECMAScript 명세에 정의된 객체를 말하며 애플리케이션의 환경과 관계없이 항상 사용할 수 있다. 아래의 객체들은 모두 네이티브 객체가 된다. Object() 생성자 함수 Function 객체 Boolean, Number, String, Array Math, Date, Error, RegExp Symbol 호스트 객체 호스트 객체는 런타임 환경에 따라 정의된 객체를 의미한다. 즉 브라우저와 Node.js 환경에서 사용되는 객체가 다르다는 것이다. 전역 객체 전역 객체는 모든 객체의 유일한 최상위 객체를 의미한다. 브라우저에서는 windo..

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 접근 각 행에는 3개의 숫자들이 적혀져있다. 이때 첫 번째 숫자는 바로 위에 있는 행 중에 첫 번째, 두 번째 숫자를 선택할 수 있다. 또한 두 번째 숫자는 모든 숫자를 선택할 수 있고, 세 번째 숫자는 두 번째 숫자와 세 번째 숫자를 선택할 수 있다. 따라서 두 번째 행부터 탐색을 진행하여 각 열이 선택할 수 있는 숫자 중에서 최댓값과 최솟값을 더해나가서 마지막 행에서 최종 해를 찾는다. 여기서 2차원 리스트..

https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 접근 정사각형에서 오른쪽 맨 아래의 지점을 기준으로 왼쪽, 위, 대각선 위에서 최솟값을 구하고 그에 대한 +1을 오른쪽 맨 아래에 저장한다. 계속해서 누적해 나갔을 때 각각의 칸에는 한 변의 길이가 저장이되고 이 중 최댓값을 찾아 넓이를 구하면된다. 구현 - 입력 예시대로 입력을 받는다. - 2차원 리스트인 memo에는 각 지점에서의 한 변의 길이가 저장된다. - answer에 가장 긴 한 변의 길이가 저장된다. N, M = map(int, input().split(..

스택과 큐의 원리를 이용하면 스택으로 큐를, 큐로 스택을 구현할 수 있다. 그 원리를 알아보고 코드로 구현해보자. 스택으로 큐 구현하기 큐는 선입선출의 구조로 데이터가 들어온 순서대로 나가게된다. 이를 스택 2개를 활용하여 구현할 수 있다. 아래의 그림을 보자. 스택 A와 B가 존재한다. 만약 큐에 PUSH하는 과정이 일어나면 스택 A에 PUSH를 한다. 이후 큐에 POP연산을 하게되면 스택 A의 모든 데이터를 스택 B로 옮긴다. 그렇게되면 스택 A의 역순으로 데이터가 저장될 것이고 스택 B를 POP하면 큐에 저장된 데이터 순서대로 출력될 것이다. 즉 스택 A는 인큐의 역할을 하게되고 스택 B는 디큐의 역할을 하게된다. PUSH를 하면 스택에는 가장 늦게 들어온 데이터가 맨 위에 쌓일 것이며 이를 다시 ..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 접근 출발지에서 도착지까지 문제에서 주어진 조건에 부합하는 경로의 개수를 구해야한다. 이를 위해 DFS를 활용하였다. 출발지에서부터 상하좌우를 탐색하여 현재 위치보다 낮은 위치로 재귀호출을 진행하였다. 이때 현재 위치가 도착지일 때는 도착지까지 올 수 있는 경우의 수를 증가하였다. 하지만 DFS만을 이용하여 풀 때는 답은 정확하게 출력될 수 있지만 이미 가봤던 경로도 계속해서 탐색을 진행하기 때문에 시..

그 동안 알고리즘 문제를 풀 때 dict를 많이 사용하였다. dict는 해시 테이블이라는 자료구조 인데 key-value 쌍으로 데이터를 저장할 수 있다. 원리는 대충 알고있었지만 정확하게 어떠한 원리를 갖고있는지 이해하고 싶어서 정리를 하게 되었다. 해싱 먼저 해싱이라는 개념을 이해할 필요가 있다. 해싱은 랜덤한 길이의 값을 해시 함수를 사용하여 고정된 크기의 값으로 변환하는 것을 의미한다. 아래의 그림과 같이 "apple", "banana", "complete"처럼 문자열의 길이가 다양한 단어가 들어왔을 때 세 자리 정수로 변환하는 작업을 해싱이라 할 수 있다. 해시 테이블과 해시 함수의 필요성 해시 테이블 해시 테이블은 해시 함수를 통해 변환된 값을 Index로 삼아 Key와 Value를 저장하는 ..