전체 글

[백준] 1343번 - 폴리오미노 (nodejs)

문제 1343번: 폴리오미노 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. www.acmicpc.net 민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB 이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다. 폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 50이다. 출력 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. 풀이 검색해보면 replace를 이용해 푼 풀이가 많이 보인다. 하지만 문제의 카테고리가 그리디..

[백준] 2193번 - 이친수 (nodejs)

문제 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 풀이 1. 이친수는 0으로 시작하지 않는다. 2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 두 규칙에 의해 이친수는 반드시 10으로 시작한다. 자릿수에 따라 모든 가능한 경우를 나열해보면 N=1일 때 - 1개 1 N=2일 때 - 1개 10 N=3일 때 - 2개 100 101 N=4일 때 - 3개 1000 1001 1010 N=5일 때 - 5개 '1000'0 "100"01 '1001'0 '1010..

[백준] 1010번 - 다리놓기 (nodejs, DP)

문제 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 풀이 M개 중 N개를 선택하고 N이 배치된 순서대로 그대로 짝지어주면 다리가 교차하는 것을 신경쓰지 않아도 된다. 이 경우는 조합 (nCr)과 같다. nCr의 공식은 n(n-1)(n-2)... (r개) / r!이다. 그런데 저렇게 곱하다보면 분자는 엄청 커질 것이고 r!도 기하급수적으로 커진다. 우리가 실제로 필요한 수는 작은데 말이다. BigInt로 계산해야 하므로 속도가 느려질 것이다. 해결 방법은 바로 조합을 구하는 과정을 쪼개보는 것이다. 하나를 먼..

[백준] 1463번 - 1로 만들기 (nodejs)

문제 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 풀이 하나의 숫자 다음에 3개의 연산을 할 수 있으므로 처음에는 한 노드에 3개의 노드가 달려있는 그래프 탐색 문제인 줄 알았다. 최단거리를 찾는 문제와 비슷하므로 BFS로 풀면 될 것이라고 생각했는데 그러면 중복되는 계산이 너무 많다. 예를 들어 X=12일 때 4까지 가는 과정..

[백준] 14502번 - 연구소 (nodejs /조합, BFS)

문제 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 💻 풀이 벽을 세울 위치는 조합으로 구했다. (재귀) 그렇게 구한 벽의 조합들을 다 세워보고 BFS로 바이러스를 퍼트린다. (BFS, 브루트포스) 2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 처음에 이런 데이터가 주어지면 split으로 쪼개며 map으로 넣는 과정에서 빈칸(0)과 바이러스(2)가 들어있는 위치도 따로 배열에 저장해준다. 각각 ..

[백준] 2468번 - 안전 영역

2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 문제 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열..

[백준] 1012번 - 유기농 배추 (nodejs)

문제 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌..

[백준] 7576번 토마토 (nodejs)

7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 골드 5 문제인데, 실버 수준의 bfs와 다르게 네 방향 탐색을 여러 곳에서 동시에 진행하며 넓혀가는 방식이다. 재밌다 더 발전된 문제로는 7569 토마토 가 있다. 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익..