본문 바로가기
Algorithm29
백준 임계경로 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.
콘센트 23843 python 23843번: 콘센트 광재는 전자기기 대여사업을 시작했다. 퇴근하기 전에 다음날 손님들에게 빌려줄 N개의 전자기기를 충전하려 한다. 사용 가능한 콘센트는 M개가 있고, 성능은 모두 동일하다. 전자기기들은 한 www.acmicpc.net 두가지 방식으로 풀었다. # 예제 입력 # N M 5 2 # arr 1 4 4 8 1 # 예제 출력 # 9 5 2 1 4 4 8 1 count : 1 before => arr : [1, 1, 4, 4, 8] / taskList : [] after => arr : [1, 1, 4] / taskList : [3, 7] count : 2 before => arr : [1, 1, 4] / taskList : [3, 7] after => arr : [1, 1, 4] / taskLi.. 2022. 6. 29.
특정한 최단 경로 1504 javascript 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 다익스트라로 푸는 문제 다만 자바스크립트로 풀려면 우선순위 큐를 직접 구현해야한다. const fs = require("fs"); const stdin = ( process.platform === "linux" ? fs.readFileSync("/dev/stdin").toString() : `4 6 1 2 3 2 3 3 3 4 1 1 3 5 2 4 5 1 4 4 2 3` ).split("\n"); const input.. 2022. 6. 29.
Puyo Puyo 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net bfs에 조건이 조금 들어간 문제이다. `같은 색상으로 연결된 구슬 4개이상 동시에 터지는게 한 사이클` 이라는것을 생각하고 풀면 어렵지 않게 풀 수 있다. const fs = require("fs"); const stdin = ( process.platform === "linux" ? fs.readFileSync("/dev/stdin").toString() : `...... ...... ...... ...... ...... ...... .. 2022. 6. 22.

티스토리툴바