백준14 백준 1162 도로포장 javascript 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 일반적인 dijkstra에 도로포장 유무를 추가하면 된다. dp 배열을 원래 1차 배열로 했으나 도로 포장 K개 이므로 dp[N][K] 를 생성한다. // 도로를 포장하지 않을 경우 if (totalW < dp[arrV][pqPavedRoad]) { dp[arrV][pqPavedRoad] = totalW; pq.add([totalW, arrV, pqPavedRoad]); } // 도로를 포장 할 경우 if (pqPavedRoa.. 2022. 9. 9. 백준 구간 합 구하기 2042번 javascript 세그먼트 트리를 쓰면 해결할 수 있는 문제이다. javascript 풀고 실행해보니 5%에서 에러가 뿜뿜 나는데 정신이 혼미해졌다. 반례 예시 찾아보니 1. 세그먼트 트리 범위 // N * 4로 많이 사용 const segmentTree = new Array(N * 4).fill(0); 2. 세그먼트 트리 업데이트 할 때 기존 배열에 값을 넣어줘야지 다음 업데이트 때 두 수의 차이를 반영할 수 있다 const diff = BigInt(c) - arr[b - 1]; // 아래 부분 추가 arr[b - 1] = BigInt(c); 반례 찾아보고 돌려봤는데도 이상이 없어서 python으로 돌려봤는데 정답! 다시보니 정수 크기가 좀 컸다. 그래서 숫자들을 BigInt로 바꿔서 계산하니 정답이 되었다. 세그먼트 .. 2022. 8. 15. 위상 정렬 *** 위상정렬은 방향이 정해져있는 그래프에서 사용할 수 있다. (양방향 X) *** 1. 진입 차수가 0인 정점을 찾아 Queue에 넣는다. 2. Queue에서 정점 하나를 뺀후, 해당 정점에 연결된 간선을 제거한다. 3. 2번을 통해 간선이 제거된 정점이 진입차수가 0이라면 Queue에 추가한다. 4. 1번으로 다시 간다. V = 정점 E = 간선 시간 복잡도는 O(V+E) 만약 사이클이 있는 경우는 아래 그림과 같다 N = 6 일 경우 결과 배열에 총 6개가 아닌 [1, 6] 단 2개만 들어있을 것이다. 나머지는 진입 차수가 1보다 크기 때문에다. 아래는 배운 위상정렬로 풀 수 있는 문제이다. 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주.. 2022. 8. 5. 백준 임계경로 1948번 javascript 위상정렬을 사용하여 풀 수 있는 문제입니다. 다만 역발상이 필요합니다. 아래 그림과 같이 위상정렬 + 위상 정렬 반대가 경로 최대값(12) 이라면 해당 정점들 사이의 간선은 1분도 쉬지 않고 달려야 하는 간선입니다. const fs = require("fs"); const stdin = ( process.platform === "linux" ? fs.readFileSync("/dev/stdin").toString() : `7 9 1 2 4 1 3 2 1 4 3 2 6 3 2 7 5 3 5 1 4 6 4 5 6 2 6 7 5 1 7` ).split("\n"); const input = (() => { let line = 0; return () => stdin[line++]; })(); const N = +.. 2022. 8. 5. 백준 후위 표기식 1918번 javascript 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 문제의 예제는 통과했었지만 아래 반례처럼 b+c*d 의 경우 틀려서 찾느라 고생했다. 원리는 1. for문을 돌며 하나씩 stack 에 넣으며, 2. stack에서 소괄호가 완성되면 3. 해당 부분을 change 함수에 넣어 계산 후 4. 다시 stack에 넣어주는 방식이다. // https://www.acmicpc.net/problem/1918 const fs = require("fs"); const stdin = ( process.platform === .. 2022. 7. 19. 백준 교환 1039 javascript 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net bfs로풀라는데 dfs로 풀 수 있는문제였다. 다음은 dfs 풀이입니다. const fs = require("fs"); const stdin = ( process.platform === "linux" ? fs.readFileSync("/dev/stdin").toString() : `100 1` ).split("\n"); const input = (() => { let line = 0; return () => stdin[line++]; })(); let data = input().trim().split(" "); const [N, K.. 2022. 7. 14. 백준 테트로미노 14500 javascript 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 풀고 찾아보니 하드코딩 느낌으로 푼 사람도 많았다. 하드코딩이 시간 단축이 더 된거보면 하드코딩이 더 나을때도 있더라 전형적인 브루트포스 문제이다. 자세한건 코드보면서!! const fs = require("fs"); const stdin = ( process.platform === "linux" ? fs.readFileSync("/dev/stdin").toString() : `4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5` ).s.. 2022. 7. 14. 백준 카드 섞기 1091번 javacript 1091번: 카드 섞기 지민이는 카지노의 딜러이고, 지금 3명의 플레이어(0, 1, 2)가 있다. 이 게임은 N개의 카드를 이용한다. (0 ~ N-1번) 일단 지민이는 카드를 몇 번 섞은 다음에, 그것을 플레이어들에게 나누어 준다. 0 www.acmicpc.net 1. 첫 번째 줄에 카드 개수 N 을 입력받는다. 2. 두 번째 줄에 현재 카드들의 상태 P 를 입력받는다. 3. 세 번째 줄에 카드를 섞는 방법 S를 입력받는다. 문제 이해하는 데 시간이 오래 걸렸다. 그 외에는 시간제한도 없고, 어려운 함정도 없어 편하게 풀었던 문제였다. 사이클의 경우 어차피 카드 섞는 법은 똑같기 때문에 첫번째와 같은 숫자가 나오면 사이클이 된다고 할 수 있다. const fs = require("fs"); const s.. 2022. 7. 4. 백준 오목 2072번 python 바둑돌을 놓는 위치 기준으로 bfs를 돌렸습니다. 방향 4개 1. 북서,남동 2. 북,남 3. 북동,남서 4. 동,서 import collections import sys input = sys.stdin.readline N = int(input()) board = [[0 for _ in range(20)] for _ in range(20)] visited = [] def isValid(x, y): return 0 2022. 7. 1. 백준 1253번 좋다 python 현재 선택한 값을 만들 수 있는 두 수를 배열에서 찾아야한다. 만약 없다면 -1 있으면 배열에서 있는 개수만큼 찾아서 반환 투 포인터로 해결 가능한 문제이다. leftIndex(배열 왼쪽 끝, 0), rightIndex(오른쪽 끝, len(arr)-1 ) 을 초기값으로 두고 특정 조건에 따라 leftIndex를 +1 오른쪽, rightIndex를 -1 한다. 조건에따라 현재 선택한 값을 만들 수 있는 두 수를 찾으면 count+=1 시간복잡도는 입력 배열 전체를 체크해야하므로 O(N) 입력값 하나당 left~right 까지 체크 O(N) O(N^2) import sys input = sys.stdin.readline N = int(input()) arr = list(map(int, input().stri.. 2022. 7. 1. 백준 도서관 1461 python 1461번: 도서관 세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책 www.acmicpc.net 1. 배열(arr)에 곱하기 2 (책 위치까지 갔다가 돌아와야하기에) 2. 배열(arr) 정렬 3. 배열(arr) 이진탐색으로 0 위치 찾기 4. 배열(arr)에서 0 위치 기준으로 좌 우 나누기(arrMin, arrMax) 5. for문 / 배열(arrMin) 0 ~ 배열(arrMin) 길이까지 돌면서, M(한번에 들 수 있는 책) 씩 건너뛰며 얻은 값들을 abs로 감싸준 후 최종결과값(result)에 더한다. 6. 배열(arrMax)도 5번처럼 돌린다. 7. 마지.. 2022. 6. 30. 백준 최소비용 구하기 성공 1916 javascript 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 처음에는 O(N)인 우선순위 큐를 만들어 돌렸으나 시간초과가 났다.. class priorityQueue { constructor() { this.queue = []; } enQueue(elements) { let queueChange = false; for (let i = 0; i elements[0]) { this.queue.splic.. 2022. 6. 30. 이전 1 2 다음
