프로그래밍/알고리즘 문제풀이24 [pg] 프로그래머스 미로탈출 1. 문제 정의 전형적인 길찾기 문제이다. 지도가 주어지고 o로 된 곳은 지나갈 수 있는 곳 x로 된 곳은 벽으로 막힌 곳이다. 맵 안에는 start 지점, 레버, exit 지점이 있으며, start 지점에서 출발해 레버를 찍고 exit지점에 가야 탈출할 수 있다. 맵의 크기는 5x5 부터 100x100까지 가능하다. 2. 내가 한 시도 전형적인 BFS문제였다. 그런데 이 문제에서 BFS로직 만으로는 해결할 수는 없었다. 바로 레버 때문이었는데, 레버에 도착 후 다시 돌아가야하는 경우가 있는데, 이 경우 BFS 썼다면 vistied가 이미 뒤로는 갈 수없기 때문에 그 시점에서 전진이 안되고 끝나버리는 경우가 생겼다. 사실 정말 간단한 발상의 전환만으로도 해결이 가능했지만, 나는 끝내 해결법을 떠올리지 못.. 2023. 9. 9. [pg] 프로그래머스 혼자서 하는 틱택토 1. 문제 정의 3x3의 빙고게임과 동일하다. 3x3의 테이블에 O 또는 X를 순서대로 표시하면서 먼저 빙고를 만드는 쪽이 승리하는 게임이다. 그러나 이 문제에서는 제일 마지막 상황에서의 3x3 테이블의 상태를 보여주고, 이것이 정상적인 게임인가, 아니면 비정상적인 게임인가를 찾아내는 게임이다. (O가 선공이고 X가 후공인데 O의 갯수는 2개 X의 갯수는 3개라면 비정상적인 게임) 2. 내가 한 시도 3x3의 매우 적은 경우의 수를 가지고 있는 빙고게임에도 불구하고, 경우의 수를 공통화 시켜서 짧은 코드를 짜려고 시도하다가 많은 삽질을 경험했다. 그래서 결국에는 3x3에서 나올 수 있는 비정상 게임의 경우의 수를 걸러내는 식으로 진행했다. 3. 코드 import java.util.HashMap; impo.. 2023. 9. 8. [pg] 프로그래머스 당구연습 1. 문제 정의 당구대가 있다고 하고, 당구 볼의 시작 점인 startX와 startY가 주어지며, 목표점의 x좌표와 y좌표가 담긴 리스트들이 주어진다. 이 때 시작점으로 부터 원쿠션으로 진행하여 x,y좌표까지 도달할 수 있는 최소거리를 구하는 것이 문제. (입사각과 반사각은 같다.) 2. 내가 한 시도 처음에는 입사각 반사각이 같다는 말에 조금 혼란이 있었지만, 결국에 1쿠션을 한다는 것은 그 쿠션을 하는 축을 기준으로 한 개의 점을 대칭시켜 일직선으로 연결되는 것이 두 점사이의 최소 값이라는 것 깨닫는 것이 핵심이었던 문제인 것 같다. 직선거리가 최솟값인 것을 깨달았다면 각 면 별로 최솟값을 구해서 그 중에 가장 적은 값을 최솟값으로 저장하면 해결되는 문제였다. 다만 두 점의 x좌표가 같거나 y좌표가.. 2023. 9. 7. [pg] 프로그래머스 리코챗 로봇 1. 문제정의 리코쳇 로봇이라는 보드게임이라고 하는데, 사실 포켓몬스터 게임에서 빙판에서 벽에 닿을때까지 미끌어지면서 상하좌우 움직이며 내가 가고싶은 최종 위치를 찾는 것이 연상되는 문제이다. 벽은 D , 목표는 G이다. G로 가는 최소한의 움직임을 구하는 것이 문제. 2. 내가 한 시도 일단 길찾기이니 bfs로직으로 풀기로 결정했다. bfs로 벽에 닿을 때 까지 진행하면서 벽에 닿으면 해당 위치가 G인지 확인하는 로직으로 구성되어 있다. 3. 코드 import java.util.*; /** * * 프로그래머스 LV2 * 리코쳇 로봇 * 접근 방법: 각각 up, down, left, right를 큐에 담아가면서 전진하면서 해결. */ public class Solution { public int so.. 2023. 9. 6. [pg] 프로그래머스 광물캐기 1. 문제 정의 곡괭이의 종류: 다이아, 철, 돌 광물 종류: 다이아, 철, 돌 이 있고, 곡괭이와 광물에 대한 리스트가 주어진다. 각 곡괭이로 광물을 채집할 경우 피로도가 추가된다. 피로도는 각 곡괭이 및 광물의 클래스 별로 각각 다르다. 다이아 곡괭이로 광물을 채집할 경우 어떤 광물을 채집하던 피로도는 1이다. 철 곡괭이로 광물을 채집할 경우 철, 돌은 피로도 1, 다이아몬드는 피로도 5이다. 돌 곡괭이로 광물을 채집할 경우 돌은 피로도 1, 철은 5, 다이아몬드는 25이다. 광물은 연속해서 5개씩 캐는 과정을 진행한다. 채집 후 곡괭이는 사용완료. 5개 캐기전까지 곡괭이는 바꿀 수 없다.(캐는 중간에 곡괭이 교체 x) 채집 시작시 곡괭이는 리스트의 어떤 것을 선택해도 무방하다. 곡괭이가 없다면 채집.. 2023. 9. 5. [pg] 프로그래머스 과제 진행하기 1. 문제 정의 조건 과제는 시작하기로 한 시작이 되면 시작한다(우선순위가 가장 높음.) 새로운 과제할 시각이 되면 기존에 진행하던 과제는 멈추고 새로운 과제를 실시함. 진행 중인 과제가 끝나고, 멈춘 과제가 있었을 경우 가장 최근에 멈춘 과제부터 진행. 과제가 끝나고, 새로 시작하는 과제와 멈춘과제가 있다면 새로시작하는 과제부터 진행(새로시작하는게 무조건 우선순위) 일 때 과목이 끝나는 순서를 배열로 리턴하는 것이 문제 input 데이터 [["과목1", "10:10", "30"],["과목2","11:00","80"]] output 데이터 ["과목1", "과목2"] 2. 내가 한 시도 문제가 cpu에서 우선순위에 따라 task를 처리하는 모습과 굉장히 닮아 있다고 생각했다. 일단 먼저 생각난 것이 멈춘 .. 2023. 8. 26. [pg] 프로그래머스 연속된 부분 수열의 합 1. 문제정의 문제에서 비내림차순으로 정렬된 수열의 배열과 k값이 주어지는데, 배열 안의 연속된 값의 합이 부분수열의 합이 k가 되는 가장 작은 인덱스 범위를 구하는 것이다. 예시) 배열 : [1,2,3,4,5] k: 5 일때 연속된 수열의 부분수열의 합으로 5가 되는 경우의 수는 [2,3], 그리고 [5] 이다. 이때 5의 인덱스는 4이므로 시작인덱스와 끝인덱스인 [4,4]가 리턴되면 된다. 2. 내가 한 시도 일단 시작인덱스와 끝인덱스 2개의 값을 관리하는 것이 귀찮아서 sum 값과 queue를 이용해서 풀기로 했다. 1. 순차적으로 큐에 값을 넣으면서 k값을 체크. 2. sum값과 k값이 같아지면 인덱스의 시작과 끝 값을 저장[큐에서 peek, 현재 위치 index] 3. sum값보다 k값이 크면 .. 2023. 8. 25. [pg] 프로그래머스 호텔 대실 1. 문제 정의 이차원 배열로 각 고객들이 호텔에 입실한 시간과 퇴실한 시간들이 주어진다. ex) [[10:00, 12:00], [11:00, 12:00]] 퇴실시 청소시간은 10분이 걸리며 이후에 방을 다시 고객에게 제공 가능하다. 위와 같은 배열이 주어질 때 가장 최소한의 방을 사용하여 고객에게 방을 제공한다고 했을 때 그 값을 구하는 것. 2. 내가 한 시도 문제를 봤을 때 이전에 풀었던 요격시스템 문제와 비슷하다고 생각했다. 대신에 다른 점이 있다면 이전에는 그냥 숫자로 풀었다면 지금은 문자열 + 시간계산이 들어갔다는 정도이다. 처음에는 문자열을 아예 시간으로 바꾼 다음에 정렬을 해서 풀려고 했지만, 문자열을 이용해서 정렬하고, 나중에 퇴실시간만 시간계산하는 것이 좀 더 코드가 간결하고 간단할 것.. 2023. 8. 24. [pg] 프로그래머스 무인도 여행 1. 문제 정의 전형적인 bfs / dfs 문제. 맵이 주어지고 맵 안에는 무인도와 바다가 있으며, 바다칸에는 X, 무인도칸에는 1~9의 숫자가 주어진다. 무인도가 인접해 있다면 하나의 무인도라고 정의한다. 최종적으로는 맵 안에 있는 무인도들이 가지고 있는 식량들의 값을 오름차순으로 정렬해서 리턴하는 문제이다.(무인도의 갯수는 0~N) 무인도가 없을 경우에는 -1을 리턴한다. 2. 내가 한 시도 처음 문제를 보고 전형적인 bfs / dfs 문제라는 것을 깨달았다. 나같은 경우는 dfs보다는 bfs로 문제를 푸는 것이 편해서 bfs로 풀기로 결정하고, 로직을 작성했다. 이 문제의 특징이라고 할 수 있는 것은 이전에 탐색했던 루트를 다시 탐색하지 않기 위해서 visited를 전역변수로 공유해서 사용해야 했던.. 2023. 8. 24. 이전 1 2 3 다음
