목록백준구현문제 (19)

개발새발 로그

[JS] 백준 9251번 : LCS - DP문제

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS 참고 https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Comm..
알고리즘/DP 2023. 7. 29. 02:43
[JS] 백준 7569번 : 토마토(3차원배열) - 구현문제

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 이전에 토마토문제에서 3차원배열을 추가한 것이다. 📋풀이방법 1. 처음에 익은토마토의 위치를 저장한다(well배열) -> 이때 좌표에 0을 추가해서 저장한다(며칠이 걸렸는지를 위해) -처음에 안익은 토마토의 갯수를 세놓는다.(none_well) -visited도 3차원 배열로 선언해줘야한다. 2. [시간초과 주의] well배열의 idx가 well의 length만큼 되었을 때..
알고리즘/구현 2023. 7. 28. 01:17
[JS] 백준 2447 : 별 찍기

https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 📋풀이방법 1. NxN의 좌표를 모두 순회하면서 별을 찍을 자리가 맞는지 확인한다, 2. 확인하는 방법은 아래와 같다. - 1. 만약 x와 y 좌표가 3으로 나눴을 때 나머지가 1이라면 빈칸이다. - if(i % 3 == 1 && j % 3 ==1) ->, (1,1), (1,4) ...이 공백을 출력해야 하는 위치인 것을 알 수 있고, 이 패턴이 반복되기 때문에 i, j..
알고리즘 2023. 7. 24. 19:27
[JS] 백준 11559 : PuyoPuyo - 구현문제

https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 📋풀이방법 1. 아래에서부터 컬러블럭이있는 곳을 찾는다 2. 컬러블럭을 찾으면 DFS를 실행한다. 3. 상하좌우로 같은 색상의 블럭이 있으면 P_cnt를 카운트해준다. 4. 그 주변의 컬러블럭을 모두 카운트해주면서 P_arr에 좌표를 넣어준다. 5. DFS가 끝나고 만약 P_cnt가 4이상이라면 P_arr에 넣어줬던 좌표를 일단 P_arr_clear에 저장한다 -연쇄는 한..
알고리즘 2023. 7. 20. 11:17
[JS] 백준 15683 : 감시

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 📋풀이방법 1. CCTV가 있는 곳의 좌표를 모두 저장한다 2. DFS를 이용해서 CCTV의 넘버에 따라 각각의 방향으로 뻗어나간다. -1번이면 4개의 방향 -> DFS 4개 - 2번이면 2개의 방향 -> DFS 2개 -3번이면 4개의 방향 -> DFS 4개 - 4번이면 4개의 방향 -> DFS 4개 - 5번이면 1개의 방향 -> DFS 1개 -각 방향으로 뻗어나가는 DFS를 모두 구해..
알고리즘 2023. 7. 8. 12:41
[JS] 백준 13460번 : 구술 탈출 2

https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 📋풀이방법 1.BFS방법을 이용 2. queue에는 [빨간공좌표, 파란공 좌표, 기울인 수, 이전에 기울였던 방향을 알려주는 숫자] 3. 4방향으로 기울이는 걸 반복함 4. 빨간 구슬을 정해진 한 방향으로 벽이있는 곳까지 움직임 -움직이는 와중에 "O"를 발견하면 구멍에 들어감을 표시해줌(redIn) -벽을 만나면 반복을 빠져나오고 움직인 좌표에서..
알고리즘 2023. 7. 4. 19:39
[JS] 백준 16234번 : 인구이동

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 📋풀이방법 1. 상하좌우 검사 L명이상 R명이하인지 2. DFS를 통해 연합배열에 삽입, visited활성화로 중복 탐색 방지 3. 연합배열안에 든 좌표끼리 연합공식으로 인구수를 나눠서 넣음 4. 다시 처음([0,0]) 나라부터 검사 -인구수가 바뀌었으니까 🤟내 제출 const fs = require("fs"); const filePath = process.platform === "..
알고리즘 2023. 7. 3. 14:00
[JS] 백준 14499번 : 주사위 굴리기

https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 📋풀이방법 1. 가로와 세로 부분, 그리고 가로와세로가 겹치는 윗 부분과 아랫부분을 각각 배열 과 상수로 변수에 저장한다. -이유는 주사위가 계속 굴러갈 때 윗 부분과 아랫부분은 어디에 속해있지않고 계속해서 바뀐다. -하지만 동쪽과 서쪽, 북쪽과 남쪽부분은 굴려도 어디에 영향을 받지 않고 윗부분의 숫자와 아랫부분의 숫자로 정해진다...
알고리즘 2023. 7. 2. 17:11
이전 Prev 1 2 3 Next 다음