Algorithm/BaeKJoon

    [JS/C++][백준]16401_과자 나눠주기
    Algorithm/BaeKJoon

    [JS/C++][백준]16401_과자 나눠주기

    문제 번호 16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN www.acmicpc.net 알고리즘 분류 이분 탐색 매개 변수 탐색 문제 풀이 이분탐색을 통하여 '조카들에게 나눠줄 과자의 길이'를 찾으면 된다. 풀이에 이용되는 숫자들은 모두 int 범위에 해당된다. left를 0, right를 1000,000,000으로 두고 이분탐색을 시작하여 과자의 길이를 찾아나선다. 매번 mid를 과자의 길이로 하여서 check라는 함수를 통하여 mid라는 길이만큼 과자들을 조카..

    [JS/C++][백준]17352_여러분의 다리가 되어 드리겠습니다!
    Algorithm/BaeKJoon

    [JS/C++][백준]17352_여러분의 다리가 되어 드리겠습니다!

    문제 번호 N; int* parent = new int[N+1]; //make-set for (int i = 1; i > start; int end; cin >> end; unionParent(parent, start, end); } for (int i = 1; i

    [JS/C++][백준]19951_태상이의 훈련소 생활
    Algorithm/BaeKJoon

    [JS/C++][백준]19951_태상이의 훈련소 생활

    문제 번호 19951번: 태상이의 훈련소 생활 2020년 5월 14일 논산훈련소에 입대한 태상이는 첫 총기 훈련에서 가스 조절기를 잃어버리는 중대한 실수를 범했다. 그로 인해, 태상이는 조교들에게 눈총을 받게 되었다. 조교들은 태상이에게 연 www.acmicpc.net 알고리즘 분류 누적 합 문제 풀이 처음 접해본 누적합 문제이다. 누적합에 대한 개념은 알고있었는데 문제로 풀어본적이 없어서 다른분들의 설명을 참고하였다. 두개의 블로그는 동일한 설명을 하고있다. 아래 블로그 역시 위의 블로그의 설명을 참고하여 자신이 알아보기 쉽게 작성하셨다고 한다. 2022 KAKAO BLIND RECRUITMENT 1차 코딩테스트 카카오 코테를 보고왔다. 들리는 소문으로는 세그트리가 나온다느니 어려운 트리 DP가 나온다..

    [JS][백준]19939_박 터뜨리기
    Algorithm/BaeKJoon

    [JS][백준]19939_박 터뜨리기

    문제 번호 19939번: 박 터뜨리기 $N$개의 공을 $K$개의 바구니에 문제의 규칙을 만족하면서 나눠 담을 수 있다면, 가장 많이 담긴 바구니와 가장 적게 담긴 바구니의 공의 개수 차이를 출력한다. 나눠 담을 수 없는 경우에는 -1을 www.acmicpc.net 알고리즘 분류 수학 그리디 알고리즘 문제 풀이 문제에서 각 바구니당 최소 1개씩의 공은 사용해야하고, 바구니마다 공의 개수가 중복되면 안되며, 모든 공을 사용하라고 했다. 그래서 가장 첫번째 바구니부터 k번째 바구니까지 공의 개수를 1개씩 늘려가면서 집어넣는다고 생각했다. 그래서 1+2+...........k 까지의 합인 k*(k+1)/2 가 n 보다 작다면 문제의 조건에 맞게 바구니에 공을 넣을 수 없다. 공의 개수가 부족하지 않고 공의 개수..

    [JS][백준]1613_역사
    Algorithm/BaeKJoon

    [JS][백준]1613_역사

    문제 번호 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 알고리즘 분류 그래프 이론 플로이드–와샬 문제 풀이 Flody Warshall 24. 플로이드 와샬(Floyd Warshall) 알고리즘 지난 시간에는 다익스트라(Dijkstra) 알고리즘에 대해 학습했습니다. 다익스트라 알고리즘은 하나의 정점... blog.naver.com 플로이드 와샬 알고리즘을 처음 써봤다. 뭔지 모를때는 뭔소린가 싶었는데 위의 블로그의 동영상 한번 보고나니까 이해됐다. 플로이드은 대략 'i에서 k를 거쳐서 j로 간다' ..

    [JS][백준]17255_N으로 만들기
    Algorithm/BaeKJoon

    [JS][백준]17255_N으로 만들기

    문제 번호 17255번: N으로 만들기 음이 아닌 정수 N이 주어진다. (0 ≤ N ≤ 10,000,000) www.acmicpc.net 알고리즘 분류 자료 구조 백트래킹 트리를 사용한 집합과 맵 문제 풀이 백트래킹을 활용하여 문제를 풀었다. 문제에서 주어진 수 N을 만들때 각 자리마다 시작하는 경우를 생각해보아야 한다. 4자리 숫자라면 1의 자리, 10의 자리, 100의 자리, 1000의 자리에서 시작할때를 각각 따져보아야 한다. for (let i = 0; i < input.length; i++) { let t = ''; let tmp = '' t += input[i]; sol(i, i, t, tmp); } 그 후 숫자를 하나씩 붙여가면서 왼쪽에 숫자를 더 붙일 수 있는지 확인하고, 불가능 하다면 오..

    [JS][백준]1890_점프
    Algorithm/BaeKJoon

    [JS][백준]1890_점프

    문제 번호 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 문제 풀이 DP[i][j]는 좌표 (i,j)에 도달 할 수 있는 경우의 수 이다. 움직일 수 있는 방향은 오른쪽과 아래 2곳 뿐이다. 2차원 배열 DP를 해당칸의 숫자만큼 오른쪽, 아래로 이동가능한지 확인하고 이동 가능하다면 jump 만큼 이동한 칸에 경우의 수를 증가시켜준다. 더해지는 칸 입장에서 보면 위, 왼쪽에서 오는 경우들이 더해지는 중이다. 근데 문제에서 '경로의 개수는 263-1보다 작거나 같다...

    [JS][백준]1271_엄청난 부자2
    Algorithm/BaeKJoon

    [JS][백준]1271_엄청난 부자2

    문제 번호 1271번: 엄청난 부자2 첫째 줄에는 최백준 조교가 가진 돈 n과 돈을 받으러 온 생명체의 수 m이 주어진다. (1 ≤ m ≤ n ≤ 101000, m과 n은 10진수 정수) www.acmicpc.net 알고리즘 분류 수학 사칙연산 임의 정밀도 / 큰 수 연산 문제 풀이 문제난이도에 비해 정답률이 너무 낮아서 '어?' 하고 제출했다가 나도 틀렸다. 나누기, 나머지만 써서 풀면 되는줄 알았는데 주어지는 숫자의 범위가 최대 10^1000 이다. (난 이걸 100000 로 보고풀었다....) 그래서 큰 숫자를 다룰 수 있는 자료형이 있는지 찾아보았다.(주어진 숫자를 string 으로 받아서 나눗셈을 직접 구현해도 된다.) 찾아보니까 BigInt 타입이라는게 있다. BigInt를 사용하면 Numbe..

티스토리툴바