Algorithm/BaeKJoon

    [JS][백준]2636_치즈
    Algorithm/BaeKJoon

    [JS][백준]2636_치즈

    문제 번호 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 알고리즘 분류 구현 그래프 이론 그래프 탐색 너비 우선 탐색 시뮬레이션 문제 풀이 BFS를 사용하면 간단하게 풀 수 있는 문제이다. 문제에서 가장자리의 'X'에는 치즈를 놓지 않는다고 했다. 그러므로 (0,0)은 항상 'X' 이며, 항상 치즈가 없다. 때문에 BFS를 (0,0)에서 시작하여 '상,하,좌,우'로 탐색하면서 다음칸이 '공기'일때와 '치즈'일때를 나누어서 구현하면 된다. 다음칸이 '공기'일때는 Queue에 넣어주고 보통의 BFS처럼 진행하고 '치즈'일때는 Qu..

    [JS][백준]17216_가장 큰 감소 부분 수열
    Algorithm/BaeKJoon

    [JS][백준]17216_가장 큰 감소 부분 수열

    문제 번호 17216번: 가장 큰 감소 부분 수열 수열 A가 주어졌을 때, 그 수열의 감소 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 8, 7, 3, 6, 5} 인 경우에 합이 가장 큰 감소 부분 수열 www.acmicpc.net 알고리즘 분류 다이나믹 프로그래밍 문제 풀이 많이 등장하는 DP 알고리즘 문제이다. 가장 큰 증가, 감소, 이어지는, 가장 긴 등등 여러가지 형태로 바뀌어서 많이 나오는걸 봤었다. 문제에서 주어지는 수열을 내용을 모두 검사한다. DP[i]는 i 번째 인덱스를 마지막으로 하는 감소하는 부분수열중 합이 가장 클때의 값이다. DP[3] = 89라면 인덱스 3의 내용을 마지막으로 하는 감소 부분 수열..

    [JS][백준]16943_숫자 재배치
    Algorithm/BaeKJoon

    [JS][백준]16943_숫자 재배치

    문제 번호 16943번: 숫자 재배치 두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0 www.acmicpc.net 알고리즘 분류 수학 브루트포스 알고리즘 조합론 문제 풀이 주어진 숫자 A로 만들수 있는 모든 숫자들을 만들어보고 조건에 맞는지 확인하면된다. 조건은 A를 이루는 숫자들을 모두 사용해야하고, 그 결과물이 B보다 작아야한다. 브루트포스 알고리즘을 사용해서 문제를 해결하였으나 DFS를 통하여 풀이를 진행해도 가능하다. 전체코드 let s = []; let answer = -1; function check(s, b, n){ s = Num..

    [JS][백준]16928_뱀과 사다리 게임
    Algorithm/BaeKJoon

    [JS][백준]16928_뱀과 사다리 게임

    문제 번호 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 알고리즘 분류 그래프 이론 그래프 탐색 너비 우선 탐색 문제 풀이 BFS를 사용하면 간단하게 풀 수 있는 문제이다. 뱀이나 사다리를 만나면 주사위를 굴리는 횟수를 증가시키지않고 연결된 칸으로 이동한다는점에 주의해서 문제를 풀면된다. 시작칸은 '1' 이므로 1에서부터 시작하여 1,2,3,4,5,6 을 증가시키면서 BFS를 통하여 탐색을 진행한다. board 라는 배열을 사용하여 문제에서 주어진 사다리와 뱀을 ..

    [JS][백준]1719_택배
    Algorithm/BaeKJoon

    [JS][백준]1719_택배

    문제 번호 1719번: 택배 첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경 www.acmicpc.net 알고리즘 분류 그래프 이론 다익스트라 플로이드–와샬 문제 풀이 다익스트라와 플로이드-와샬 알고리즘을 고민하다가 플로이드-와샬이 좀더 친숙해서 플로이드-와샬로 문제를 풀었다. i 에서 j 로 갈때 k를 거쳐서 가는것이 더 비용이 적게들면 arry[i][j]의 값을 수정한다는 플로이드-와샬의 내용을 살짝 응용하면 된다. city라는 2차원 배열을 생성해서 문제에서 주어진 집하장간의 경로를 입력하고 플로이드-와샬 알고리즘에 사용하여 집하장간의 최소값을..

    [JS][백준]1939_중량제한
    Algorithm/BaeKJoon

    [JS][백준]1939_중량제한

    문제 번호 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 알고리즘 분류 그래프 이론 자료 구조 그래프 탐색 이분 탐색 너비 우선 탐색 분리 집합 문제 풀이 BFS와 이분탐색을 이용하여 문제를 풀었다. 이분탐색을 통하여 한 번의 이동에서 옮길 수 있는 물품들의 중량을 찾는다. 그리고 BFS를 통하여 해당 중량으로 두 공장사이를 무사히 오갈 수 있는지 확인한다. 시간제한 때문에 이분탐색을 사용하여서 중량을 찾아야한다. 이분탐색으로 mid 값을 중량으로 ..

    [JS][백준]2239_스도쿠
    Algorithm/BaeKJoon

    [JS][백준]2239_스도쿠

    문제 번호 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 알고리즘 분류 구현 백트래킹 문제 풀이 스도쿠다. 전에 C++ 로 스도쿠문제를 풀어본적이 있는데 백준에는 스도쿠 문제가 여러개 있다. 하지만 그떄랑 푸는 방법은 크게 다르지않다. 알고리즘은 어렵지않다. 문제에서 주어지는 스도쿠 게임판을 입력받고 '0'으로 표기된 빈자리가 발견될 때 마다 해당 자리에 1부터 9까지의 수를 모두 넣어보면서 정답이 나올때 까지 찾아보면된다. 문제에서 정답이 여러개일 경우 가장 작은자리를 정답으로 처리한다 하였으니 1부..

    [JS][백준]19948_음유시인 영재
    Algorithm/BaeKJoon

    [JS][백준]19948_음유시인 영재

    문제 번호 19948번: 음유시인 영재 감수성이 뛰어난 음유시인 영재는 일상생활 중에 번뜩 시상이 떠오르곤 한다. 하지만 기억력이 좋지 못한 영재는 시상이 떠오르면 그 순간 컴퓨터로 기록해야만 안 까먹는다! 시는 대문자, 소 www.acmicpc.net 알고리즘 분류 구현 문자열 문제 풀이 정답률이 낮은 구현문제이다. 질문게시판을 참고해보니 문제를 푸시는 분들이 시의 내용만 생각하고 시의 제목은 누를 수 있는 횟수에서 차감하지 않는 실수를 많이 해서 정답률이 낮은것 같다고 한다. 문제에서 공백이 여러개 연속으로 이어지는 경우도 주어지는 지는 모르겠으나 그럴 수 도 있다고 판단되어서 정규식을 이용하여 split 함으로써 해당경우도 처리할 수 있도록 하였다. const pome = input[0].trim(..

티스토리툴바