![]()
문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 🔎문제 설명 문제만 보고 이게 DP문제인가? 싶었다. 그냥 무작정 BFS를 사용해서 풀었다. 그랬더니 시간초과가 났다. 이동하는 조건만 맞으면 큐에 넣어줬고, 도착지점에 도착한다면 그게 적절한 이동이라고 생각해서, 결괏값을 계속 더해줘서 함수를 탈출한다면 결과값을 출력해 줬지만 아마 배열 크기도 크고, 큐에 쓸데없는 없는 값이 많이 들어가서 그런 거 같다. 다른 사람들의 풀이를 보니 dfs..
![]()
문제 서기 2012년! 드디어 2년간 수많은 국민들을 기다리게 한 게임 ACM Craft (Association of Construction Manager Craft)가 발매되었다. 이 게임은 지금까지 나온 게임들과는 다르게 ACM크래프트는 다이내믹한 게임 진행을 위해 건물을 짓는 순서가 정해져 있지 않다. 즉, 첫 번째 게임과 두 번째 게임이 건물을 짓는 순서가 다를 수도 있다. 매 게임시작 시 건물을 짓는 순서가 주어진다. 또한 모든 건물은 각각 건설을 시작하여 완성이 될 때까지 Delay가 존재한다. 위의 예시를 보자. 이번 게임에서는 다음과 같이 건설 순서 규칙이 주어졌다. 1번 건물의 건설이 완료된다면 2번과 3번의 건설을 시작할 수 있다. (동시에 진행이 가능하다) 그리고 4번 건물을 짓기 위..
![]()
문제 https://school.programmers.co.kr/learn/courses/30/lessons/142085 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📕문제 풀이 무적권을 적절한 라운드에 사용해서 최대한 많은 라운드를 버텨야 한다. 따라서 무적권을 사용하는 라운드를 선정하는 방법이 중요하다! 📗초기 풀이 방식 초기 풀이 방식은 queue에 넣어서, 모든 경우의 수를 탐색했다. 하지만 N의 길이가 커서 시간초과가 났다. 초기 알고리즘은 이렇다. queue에 원소를 계속 넣어서, 만약 가용가능한 병사의 수가 현재 라운드의 적의 수보다 적으면..
![]()
문제 https://school.programmers.co.kr/learn/courses/30/lessons/159993 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔎문제 해석 출발점에서 레버를 당겨서 탈출점까지의 최소 경로를 구하는 문제입니다. BFS 알고리즘을 사용해서 쉽게 풀 수 있습니다. 문제는 굉장히 간단합니다..(저는 너무 복잡하게 생각해서 오래 걸렸습니다ㅜㅜ) 문제를 보면 출발정메서 레버로 있는 칸으로 이동하고, 레버를 당긴 후, 탈출점으로 이동하라고 나와 있습니다. 이 문제는 반드시 탈출을 하기 위해서는 레버를 당겨야 합니다. 만약 출발..
![]()
문제 https://school.programmers.co.kr/learn/courses/30/lessons/92342 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 🔎문제 해석 우선 문제를 읽고, DFS 혹은 백트래킹으로 풀어야겠다고 생각을 했습니다. 쭈욱 진행하다가, 만약 끝에 도달했을 때의 점수를 비교해서, 가장 큰 점수로 이기는 방법을 계속 찾아줬습니다. 문제에서는 만약 가장 큰 점수로 이기는 방법이 여러 가지라면, 특수한 조건을 부여했고, 그 조건도 그렇게 어려운 조건이 아닙니다. 문제에서 포인트는 이 문제를 DFS로 풀어야 한다는 것입니다. 우..
![]()
문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 이동하지 않고 같은 칸에 머물러있는 경우도 가능하다. 이 경우도 방문한 칸의 개수가 하나 늘어나는 것으로 생각해야 한다. 이번 문제에서는 낮과 밤이 번갈아가면서 등장한다. 가장 처음에 이동할 때는 낮이고, 한 번 이동할 때마다 낮과 밤이 바뀌게 된다. 이동하지 않고 같은 칸에 머무르는 경우에도 낮과 밤이 바뀌게 된다. 만약에 이동하는 도중에 벽을 부수고 이동하는..
![]()
문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다. 호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다. 아래에는 세 가지 예가 있다. ...XXXXXX..XX.XXX ....XXXX.......XX .....XX.......... ....XXXXXXXXX.XXX .....XXXX..X..... ......X.......... ...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X..... ..XXXXX..XXXXXX....
![]()
문제 크기가 1 ×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 설치해야 하는 거울 개수의 최솟값을 구하는 프로그램을 작성하시오. 레이저로 통신한다는 것은 두 칸을 레이저로 연결할 수 있음을 의미한다. 레이저는 C에서만 발사할 수 있고, 빈 칸에 거울('/', '\')을 설치해서 방향을 90도 회전시킬 수 있다. 아래 그림은 H = 8, W = 7인 경우이고, 빈칸은 '.', 벽은 '*'로 나타냈다. 왼쪽은 초기 상태, 오른쪽은 최소 개수의 거울을 사용해서 두 'C'를 연결한 것이다. 7 . . . . . . . 7 . . . . . . . 6 . . . . . ..
![]()
문제 https://www.acmicpc.net/problem/1600 1600번: 말이 되고픈 원숭이 첫째 줄에 정수 K가 주어진다. 둘째 줄에 격자판의 가로길이 W, 세로길이 H가 주어진다. 그 다음 H줄에 걸쳐 W개의 숫자가 주어지는데, 0은 아무것도 없는 평지, 1은 장애물을 뜻한다. 장애물이 있 www.acmicpc.net 🔎문제 해석 원숭이의 동작수의 최소값을 구해야 하므로, BFS 알고리즘을 이용해서 출발지부터 도착지점까지 갈 수 있는지를 판단해야 합니다. 문제는 간단합니다. queue를 이용해서 좌표와 말처럼 이동한 횟수를 계속해서 기록해 둡니다. 만약 말처럼 이동한 횟수가 k-1 이하라면 말처럼 이동할 수 있습니다. 하지만 k이상이라면 말처럼 이동할 수 없습니다. 즉 queue에서 기록한..
