BFS 문제를 풀다가 JS에는 큐가 구현되어 있지 않다는 것을 알게 되었다 ^__^ 코딩테스트에서 큐가 필요한 상황이 오면 어떻게 해야 할까? 1. 시간복잡도 O(N) 시간제한이 널널할 때는 Array.shift() 를 사용하자. 큐의 pop과 동일한 기능을 한다. 하지만 배열의 원소를 하나씩 당기기 때문에 시간복잡도가 O(N)이다. 2. 시간복잡도 O(1) pop할 원소의 인덱스를 변수를 만들어 저장하자. let front = 0; while (front < queue.length) { const [x, y, z] = queue[top]; front += 1; /* ... */ } 인덱스를 옮김으로써 가장 앞의 원소가 어떤 것인지 판별할 수 있게 되었다. 실제 원소가 삭제되지는 않지만 FIFO 흉내내..
문제 https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 자바스크립트(node.js)로 풀이했습니다. 풀이과정 1차 시도 실패 이유 - 메모리 초과 갈 수 있는 모든 땅에 대해 bfs()를 다 돌림 -> visited는 bfs()를 호출할때마다 계속해서 할당 -> 메모리 초과 이뿐만 아니라 최단거리는 직전 땅의 거리 정보를 이용해 구할 수 있으므로 각 땅이 아니라 전체를 bfs() 돌리는게 맞다 for ..
문제 https://www.acmicpc.net/problem/18111 18111번: 마인크래프트 팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 www.acmicpc.net 자바스크립트(node.js)로 풀이했습니다. 최종코드 const fs = require('fs'); const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt'; const input = fs.readFileSync(filePath).toString().trim().split('\n'); const [n, m, b..
(a * b) % c = (a % c * b % c) % c (a + b) % c = (a % c + b % c) % c (a - b) % c = (a % c - b % c + c) % c 코테에서 흔히 나오는 나머지 연산 -> 마지막에만 때리면 거의 무조건 오버플로우 난다..! 제발 그만 까먹자.
JS 코딩테스트에서 상황별로 유리한 반복문과 함수에 대한 내용을 다룹니다. 시간복잡도 O(n)으로 동일하다. for for (let i = 0; i < 배열.length; i++) { /* ... */ } 반복 시작점, 끝점, 증분 커스텀 가능 return제어 O for ... of for (const item of 배열) { /* ... */ } 배열에서 값만 취할 때 사용 return제어 O forEach와 다르게 iterable 객체면 다 순회가능 cf. for...in 은 객체를 순회 or 인덱스값이 필요할 때 용이 (배열도 객체이긴 하지만, key인 index값만 가져올 수 있기 때문에 배열에서는 for...of가 유리하다) map const arr = ['1', '2', '3']; const ..
1️⃣ 매개변수로는 그래프와 시작점 받기 def bfs(graph, start): 2️⃣ deque() 활용하여 queue 생성 queue = deque() 3️⃣ 시작점 방문하고 큐에 시작 인덱스 추가 visited[start] = True queue.append(start) 4️⃣ queue가 빌때까지 반복 큐에서 가장 먼저 들어갔던 인덱스 꺼내서, 해당 인덱스와 연결된 노드 순회 while queue: cur = queue.popleft() for node in graph[cur]: 5️⃣ 만약 노드를 방문하지 않았다면, 방문하고 큐에 해당 노드 인덱스 추가 if not visited[node]: visited[node] = True queue.append(node)
1️⃣ left right 설정하기 2️⃣ while True 반복, mid 설정 while True: mid = (left+right)//2 3️⃣ mid 값을 이용하여 주어진 조건에 만족하는지 체크하기 위한 값 구하기 count = 0 for line in lines: count += line//mid 4️⃣ left > right 면 반복 끝내고 값 출력 if left > right: print(mid) break 5️⃣ 주어진 조건 만족에 따라 left와 right 값을 조절한다 if count < n: right = mid - 1 else: left = mid + 1 예시 문제 BOJ 1654
0. 이항계수란 - n개 중 k개를 뽑는 조합의 수 - 이항계수의 성질 1. n개 중에 k개를 뽑는 것과 n개 중에 n-k개를 뽑는 경우의 수는 같다 (뽑지 않을 것을 정하는 것과 뽑을 것을 정하는 것은 같다) 2. n-1개 중에 k개를 뽑는 경우의 수와(1개 포함X) n-1개 중에 k-1개를 뽑는 경우의 수(1개 포함O)를 더하면 n개 중에 k개를 뽑는 경우의 수이다 3. nC0부터 nCn까지의 합은 2^n 이다 1. 분할정복을 이용한 이항계수 구하기 1.1 알고리즘 진행과정 0️⃣ nC0 혹은 nCn 은 항상 1이다 1️⃣ 나머지 경우는 이항계수의 2번 성질을 활용하여 구현 시간복잡도가 O(n!)이라서 엄청나게 비효율적.. 1.2 코드 def bino(n, k): if k == 0 or n == k:..
