전체 글

출처https://school.programmers.co.kr/learn/courses/30/lessons/1832 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 주어진 도로 상태의 상태에 따라, 목적지 까지 도착 가능한 전체 경로 수를 구하는 문제이다. 문제에 최단 경로라고 명시되어 있지는 않지만, 오른쪽 또는 아래 방향으로 이동 가능하다고 되어있기 때문에 최단 경로를 구하는 문제가 맞다. 보통 지도가 주어지고 최단 경로의 수를 구하려면 오른쪽 또는 아래 방향으로만 이동 가능하다고 가정하고 푼다. (왼쪽 지점과 위 지점 경우의 수를 더함) 풀이처음에는..

출처https://school.programmers.co.kr/learn/courses/30/lessons/118669 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제한 출입구에서 출발하여 하나의 정상만을 거쳐 되돌아 오려고 한다. 이때, Intensity란 방문한 경로들 중 최대 가중치 값을 의미한다. 이 Intensity가 최소가 되도록 하는 경로를 구하여, 최소 intensity를 가지는 경로의 방문한 산봉우리 값과 , 최소 intensity값을 반환하는 문제이다. 풀이문제에서는, 한 출입구로 부터 출발하여 한 산봉우리까지 갔다가 돌아올 때, Int..

출처https://www.acmicpc.net/problem/3190 문제 뱀이 진행하던 중 사과를 만나면 몸길이가 하나 추가된다. 사과가 없다면 몸길이는 변화없이 앞으로만 전진하며, 'D'를 만나면 오른쪽으로, 'L'을 만나면 왼쪽으로 방향을 바꾼다. 위 조건에 따라 뱀 게임을 진행하며, 머리나 몸에 부딪힐때 게임이 종료된다. 풀이특별한 알고리즘이 아닌, 구현, 시뮬레이션 문제이다. 직접 문제 조건에 따라 진행되도록 코드를 구현하면 된다. 시간을 늘려가며 while문에서 게임을 진행하고, 조건이 충족되면 게임을 종료하도록 한다. while문 안에서는 다음과 같은 순서로 진행된다.while (true) { - time 증가 - 뱀의 머리를 큐에서 빼서, 앞으로 한칸 전진시킴 - 벽에 부딪히거나..

출처https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr문제 주어지는 트리의 각 노드에는 양과 늑대 둘중 하나가 놓여져 있다. 노드를 돌아다니며 양과 늑대를 데리고 다니는데, 늑대가 양보다 많아지면 늑대가 양을 모두 잡아먹게 된다. 이 조건에 따라 각 노드를 순회하며 모을 수 있는 양의 최대 마릿수를 구하는 문제이다. 풀이처음에 이 문제를 일반적인 DFS 또는 백트래킹으로만 해결하려고 하였다. 하지만 한번 방문했던 노드도 다시 방문 해야하는 경우가 많기..

출처https://www.acmicpc.net/problem/17142 문제비활성화된 바이러스가 있는 연구실이 주어진다. 바이러스는 활성화 되면 상하좌우가 동시에 감염된다. 이 중 M개의 바이러스를 골라 활성화상태로 시킨다고 할때, 연구실에 빈곳 없이 모두 감염될때 까지 걸리는 최소 시간을 구하는 문제이다.풀이먼저, 우리는 비활성화인 바이러스 중 M개를 골라야 한다. M개의 순서는 상관이 없기 때문에 순열이 아닌 조합을 구해야하며, 자바에서 조합을 구하기 위해서는 DFS를 활용해야 한다. 먼저, 바이러스의 위치가 담긴 List를 만들고 이 중 M개만 조합을 만든 뒤 바이러스를 전염시켜야 한다. M개의 조합을 기록하기 위해 DFS에서 현재 고른 배열을 들고다닐수도 있지만, 메모리 절약을 위해 전역 변수로 ..

출처https://www.acmicpc.net/problem/14502 문제격자모양의 구조로 되어있는 연구소에 바이러스가 유출되었다. 바이러스는 상하좌우 빈칸이 있는곳으로 퍼질 수 있으며, 벽이 있으면 진행이 불가능하다. 벽을 새로 3개만 세워 바이러스 유출을 최대한 막아 안전지대를 확보한다고 하였을 때, 가장 넓은 안전지대의 면적을 구하는 문제이다. 풀이정석적인 DFS + BFS 문제이다. 먼저, 벽을 3개를 막아야 하는데 어느 벽을 막아야 안전지대가 가장 넓은지 직접 세워보기 전까지는 알 수 없기때문에, 모든 경우를 살펴보아야 한다. 또한 3개를 막기 위한 벽 위치의 조합을 구하기 위해서는, DFS를 이용해야 한다. DFS를 이용하여 세개의 벽을 막아놓았다면, 이후 막혀있는 연구실에서 BFS를 이용하..

출처https://school.programmers.co.kr/learn/courses/30/lessons/60063 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제 길이가 2인 로봇은 왼쪽과 오른쪽 둘중 한 축을 기준으로 위 회전이 가능하다. 이 로봇을 적당히 회전시키거나 상하좌우로 이동시켜 목적지까지 이동하는데 걸린 최단 시간을 구하는 문제이다. 풀이이 문제는 어떠한 공식을 적용해서 직접 움직여 보지 않고 해결하기엔 어려운 문제라고 판단하였다. 따라서, 직접 조건에 따라 움직이며 해답을 구하는 시뮬레이션 문제이며, 최단 시간을 구해야하는 조건이 붙었기..

출처https://www.acmicpc.net/problem/13459 구슬 탈출 문제 가장 바깥 행과 열이 모두 막혀있고, 밖으로 나갈 수 있는 구멍이 하나 뚫린 상자를 이리저리 기울여서 그 안에 있는 빨간공을 구멍을 통해 꺼낼 수 있는지 판별하는 문제이다. 단, 파란공은 어떠한 경우에도 빠지게 되면 실패로 간주한다. 먼저, 문제의 조건을 추려보면 아래와 같다 #으로 된 것은 벽 또는 장애물이며, 이 곳으로 공은 갈 수 없다.R로 표시된 빨간 공과 B로 표시된 파란공은 각 한칸을 차지하고 있다고 가정한다. 이때 빨간공과 파란공은 같은 위치에 있을 수 없다.빨간공과 파란공은 보드를 기울였을때 동시에 움직인다.빨간 구슬은 10회 이하로만 움직여야 한다.이 문제에서 기울인다 함은, 공이 기울인 방향으로 장애..