본문 바로가기

알고리즘 문제77

[백준 - Java] 1261번 : 알고스팟 문제 www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 설명 처음엔 BFS로 최단 거리로 가면 되려나?라고도 생각했지만, 기존의 BFS로는 풀 수 없는 문제이다. 최단 거리도 필요 없고, (0, 0) 정점에서 부터 너비 우선 탐색을 해나가며 벽을 더 적게 부수는 방법으로 (M, N)까지 나아가야한다. 이를 위해서 기존의 Queue가 아니라 Deque를 사용했다. Deque는 Queue의 앞 뒤로 값을 삽입할 수 있다. Deque의 앞쪽을 .. 2021. 3. 16.
[백준 - Java] 6087번 : 레이저 통신 문제 www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 설명 2020 카카오 인턴십 문제로 나왔던 경주로 건설과 비슷한 문제이다. 자세한 설명은 경주로 건설 포스팅을 참고해주세요. [프로그래머스 - Java] 경주로 건설 (2020 카카오 인턴십) 경주로 건설은 직선, 코너 도로마다 비용이 부과되는데 둘을 적절히 사용해 가장 적은 비용으로 경주로를 건설해야 한다. 레이저 통신도 마찬가지이다. 레이저를 쏘는데 거울을 가장 적게 쓰는 방법으로 C에서 다른.. 2021. 3. 15.
[백준 - Java] 10836번 : 여왕벌 문제 www.acmicpc.net/problem/10836 설명 매일매일 애벌레를 키우면 무조건 시간 초과가 난다!! 1,000,000 최대 백만일까지 애벌레를 키울 수 있기 때문!! 잘 생각해보면 매일 애벌레를 키워할 필요가 없다! 제일 왼쪽 열과 제일 위쪽 행의 애벌레만 주어지는 N날 동안 주어지는 0, 1, 2로 키우고, 나머지 (1, 1) ~ (M, M) 애벌레들은 N날이 지난 후, 문제의 조건 2에 따라 자신의 왼쪽(L), 왼쪽 위(D), 위쪽(U)의 애벌레들 중 가장 큰 사이즈로 키워진 애벌레의 크기로 바꿔주면 됨! 매일매일 키워보는 거나 제일 왼쪽 위쪽 다 키우고 적용하는 거나 둘은 같다! 그러니 다 키우고 적용하는게 훨 시간을 줄일 수 있다. * Scanner써서 입력받거나 println으.. 2021. 3. 3.
[백준 - Java] 11967번 : 불켜기 문제 www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 설명 data-make.tistory.com/577 [BOJ] 11967.불켜기(완탐).java #. Problem https://www.acmicpc.net/problem/11967 * The copyright in this matter is in BOJ #. Resolution Process 1. Read and understand problem 2.. 2021. 3. 1.
[백준 - Java] 8972번 : 미친 아두이노 문제 www.acmicpc.net/problem/8972 8972번: 미친 아두이노 요즘 종수는 아두이노를 이용해 "Robots"이라는 게임을 만들었다. 종수는 아두이노 한대를 조정하며, 미친 아두이노를 피해다녀야 한다. 미친 아두이노는 종수의 아두이노를 향해 점점 다가온다. www.acmicpc.net 주절주절... 어떻게 하면 최적으로 문제를 풀 수 있을까 고민을 많이 했던 문제다. 미친 아두이노가 파괴되었나 안되었나 상태 변수를 만들어 관리하기도 했었고, 반례를 생각하지 못한 코드를 짠 경우도 있었고 (ex. 2개 이상의 미친 아두이노가 같은 칸으로 이동하는 경우) 같은 칸으로 이동할 경우 이전에 이동한 아두이노를 미리 움직여서 보드판이 뒤죽박죽으로 나오기도 하고... 맵을 지웠다. 다시 썼다. 복.. 2021. 3. 1.
[백준 - Java] 2638번 : 치즈 문제 www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 문제 조건 치즈 내부에 있는 공간은 치즈 외부 공기와 접촉하지 않는 것으로 가정한다. 그러므로 이 공간에 접촉한 치즈 격자는 녹지 않고 C로 표시된 치즈 격자만 사라진다. 그러나 한 시간 후, 이 공간으로 외부 공기가 유입되면 오른쪽 그림과 같이 C로 표시된 치즈 격자들이 사라지게 된다. 파란색으로 칠해진 부분이 외부 공기, 빨간색으로 칠해진 부분이 치즈 내부의 공기이다. 모눈종이의 맨 가장자리에.. 2021. 2. 27.
[백준 - Java] 2156번 : 포도주 시식 문제 www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 설명 백준 2597번 계단 오르기와 비슷하게 DP (Dynamic Programing) 동적 계획법으로 풀 수 있는 문제다. [백준 - Java] 2579번 : 계단 오르기 하지만 계단 오르기완 다르게 하나 더 고려할 점이 있다. 바로 와인을 먹지 않는 경우 역시 고려해야 한다는 것이다. 일단 그 경우를 제외하고 생각해보자. 먼저 와인은 3잔 연속 먹을 수 없다. 따라서 현재 와인을 먹을 수 있는 경우는 1.. 2021. 2. 25.
[백준 - Java] 2579번 : 계단 오르기 문제 www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 설명 (Dynamic Programing) 동적 계획법으로 풀 수 있는 문제다. DP를 푸는 방식은 크게 Top-Down과 Bottom-UP 방식으로 나뉘는데 Bottom-Up방식으로 구현할 것이다. Bottom-Up 방식은 작은문제부터 풀어가며 전체 문제를 풀어가는 방식이다. 이 방법은 대개 반복문을 통해 구현된다. 먼저 계단을 오르는 규칙에 대해 알아보자. 계단을 오르는 규칙 계단은 한 번에 한 계단씩 또는 두 계.. 2021. 2. 23.
[백준 - Java] 11057번 : 오르막 수 문제 www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 설명 DP 동적 계획법을 사용해 해결하는 문제이다. 표를 그려보면 dp를 적용할 규칙이 쉽게 떠오른다. 먼저 각 자릿수에는 0~9까지의 10개의 숫자가 들어갈 수 있다. N=1 한자릿수일 경우 0~9까지 각 숫자들을 한 번씩 이용해 총 10가지의 오르막수를 만들 수 있다. N=2 두자릿수일 경우 00, 01, 02 ... 09 -> 10 가지 11, 12, 13 ... .. 2021. 2. 22.
[백준 - Java] 15683번 : 감시 (삼성 SW 역량 테스트 기출 문제) 문제 www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 설명 헷갈려서 엄청 오래 걸린 문제다... 근데 진짜 말그대로 1~5번까지 cctv를 90도씩 돌려가며 조합해서 사각지대의 최솟값을 구해야 한다. 방향을 바꾸는 과정은 시계방향으로 상 우 좌 하로 0, 1, 2, 3 순서이다. (순서는 그냥 자기 마음대로 정해면 됨 나는 상우하좌가 편해서 저렇게 외웠다!) CCTV는 1~5까지 총 5개의 형태가 있다. 각각의 경우를 90도 회전하는 경우를 생각해.. 2021. 2. 11.
반응형

티스토리툴바