전체 글

전체 글

    [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..

    [JS][백준]16236_아기 상어
    Algorithm/BaeKJoon

    [JS][백준]16236_아기 상어

    문제 번호 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 알고리즘 분류 구현 그래프 이론 그래프 탐색 너비 우선 탐색 시뮬레이션 문제 풀이 아기 상어는 현재 자신의 몸 크기에 따라서 먹을 수 있는 물고기가 있고 먹을 수 없는 물고기가 있다. 따라서 먹이를 먹을때 마다 아기 상어의 몸의 크기를 확인하여서 먹을 수 있는 물고기들의 위치, 거리를 계산해야한다. 이를 위해서 BFS 를 사용하였다. 왜냐하면 BFS는 간선의 가중치가 1로 같을때 최단 경로를 찾아주기 때문이다. BFS로 맵을 탐험하면서 아기 상어..

    [JS][백준]5582_공통 부분 문자열
    Algorithm/BaeKJoon

    [JS][백준]5582_공통 부분 문자열

    문제 번호 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 알고리즘 분류 DP 문제 풀이 2차원 배열을 사용해서 공통 부분 문자열을 찾는 문제이다. 공통 부분 문자열은 연속된 문자열이다. 해당 문제는 아래의 블로그에 나온 설명이 도움이 많이 되었다. 그래서 따로 설명을 쓰는것보다 링크를 추가하는것이 더 좋다고 생각된다. [알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence LCS는 주로 최장 공통 부분수열(L..

    [JS][백준]17179_케이크 자르기
    Algorithm/BaeKJoon

    [JS][백준]17179_케이크 자르기

    문제 번호 17179번: 케이크 자르기 첫 번째 줄에 자르는 횟수가 담긴 목록의 길이 N과 자를 수 있는 지점의 개수 M, 그리고 롤 케이크의 길이인 정수 L이 주어진다. (1 ≤ N ≤ M ≤ 1,000, 1 < L ≤ 4,000,000) 다음 M줄에 걸쳐 자를 수 있는 www.acmicpc.net 알고리즘 분류 이분 탐색, 그리디 문제 풀이 이분 탐색을 사용해서 '가장 작은 케이크의 길이'를 '최대'로 만드는 문제이다. 케이크를 자르면 가장 작은애가 나오게 될텐데 걔의 길이를 가능한 길게 하라는 말이다. 여기서 이분 탐색은 '가장 작은 케이크의 길이'를 찾는데 사용된다. 왜 이분 탐색을 사용하는지 생각해보면 '가장 작은 케이크의 길이'가 '최대'일때를 구하려면 케이크를 자를 때 마다 가능한 중앙에서 ..

    Algorithm/알고리즘 예제코드

    DP(동전 교환, LCS)

    동전 교환 동전 교환 관련 문제 접근 :: 마이구미 이번 글은 "동전 교환" 에 관한 알고리즘을 다뤄볼 것이다. 백준 알고리즘 사이트에서 알고리즘 분류에서 "동전 교환"을 볼 수 있다. 2293번 동전 1, 2294번 동전 2, 11047번 동전 0 문제를 통해 다룬 mygumi.tistory.com n가지 종류의 동전을 갖고 가치의 합이 k원이 되는 경우의 수. dp[0] = 1; for (int i = 0; i < n; i++) { for (int j = coin[i]; j

티스토리툴바