본문 바로가기
분류 전체보기86
백준 구간 합 구하기 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.
리눅스 백그라운드 실행 github action 의 runners를 추가할 때 ./run .sh 실행 후 유지해야한다. putty에서 실행하고 putty창을 닫으면 실행이 중단됨으로 백그라운드로 프로세스를 실행하는 것이 좋다. 백그라운드로 프로세스 실행하기 [ec2-user]$ nohup ./run.sh & > /dev/null 로그가 계속 쌓이므로 위와 같이 /dev/null 로 보내서 없애준다. 백그라운드 프로세스 종료 1. ps 명령어로 실행중이 프로세스를 찾는다. 2. kill 명령어로 해당 프로세스를 종료한다. [ec2-user]$ ps -ef | grep run ec2-user 5445 3273 0 11:37 pts/0 00:00:00 /bin/bash ./run.sh ec2-user 5450 5445 0 11:37.. 2022. 7. 12.
docker.sock 권한 오류 github action으로 ci/cd 재구성 해야해서 하는 도중 docker.sock 권한 오류를 만났다. 두 번째 겪는 일이기에 다시 찾는 일 없도록 기록해둔다. Got permission denied while trying to connect to the Docker daemon socket sudo chmod 666 /var/run/docker.sock Got permission denied while trying to connect to the Docker daemon socket at unix:///var/run/docker.sock: Get http://%2Fvar%2Frun%2Fdocker.sock/v1.40/containers/json: dial unix /var/run/docker.so.. 2022. 7. 12.
백준 카드 섞기 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.

티스토리툴바