Passwd

문제문제 : https://www.acmicpc.net/problem/2178N X M 크기의 배열로 표현되는 미로가 있다.101111101010101011111011미로에서 1은 이동할 수 있는 칸이고, 0은 이동할 수 없는 칸이다. 이 미로에서 (1, 1)에서 출발해 (N, M)으로 이동할 때 지나야 하는 최소 칸의 개수를 구하는 프로그램을 작성하라. 한 칸에서 다른 칸으로 이동할 때는 서로 인접한 칸으로만 갈 수 있다.입력의 첫째 줄에는 두 정수 N, M이 주어지고, 다음 N개의 줄에 M개의 정수가 붙어서 입력으로 주어진다. 또한 항상 도착 위치로 이동할 수 있는 경우만 고려한다.  2024.05.10-[프로그래머스] 게임 맵 최단거리와 동일한 형태의 BFS 문제이다. 게임 맵 최단거리에서 불필요한..

문제문제 : https://school.programmers.co.kr/learn/courses/30/lessons/1844ROR 게임은 두 팀으로 나눠서 진행하는데, 상대 팀의 진영을 먼저 파괴하면 이긴다. 즉, 각 팀은 상대 팀 진영에 빠르게 도착해야 한다. 아래 그림은 당신의 팀 캐릭터(행 :1, 열 : 1), 상대 팀의 진영(행: 5, 열: 5) 그리고 게임의 맵(5 X 5)을 표현한 것이다.맵에서 검은 부분은 벽으로 막혀 갈 수 없는 길이고, 흰 부분이 갈 수 있는 길이다. 캐릭터는 동서남북으로 한 칸씩 이동하되 맵을 벗어날 수는 없다. 만약 상대 팀 진영이 벽으로 막혀있다면 상대 팀 진영에 도착할 수 없다.게임의 맵을 이차원 배열 maps 매개변수로 전달받을 때, 캐릭터가 상대 팀 진영에 도착..

너비 우선 탐색너비 우선 탐색(Breadth First Search)이란 그래프 탐색 방법 중 하나로, 임의의 시작 정점을 방문한 후 인접한 모든 정점을 우선 방문하는 방법이다. 갈림길에 연결되어 있는 모든 길을 탐색한 뒤, 다시 연결되어 있는 모든 길을 넓게 탐색하는 방법이다.그래프 내 모든 간선의 가중치가 같으면 너비 우선 탐색으로 찾아낸 두 점 사이의 경로는 최단 경로에 해당한다. 따라서 두 점 사이의 최단 경로 또는 임의의 경로를 찾고 싶을 때 너비 우선 탐색을 사용한다. 보통 너비 우선 탐색에 대해 찾아보면 트리 형태의 그래프 탐색이 가장 흔하게 보이는데, 트리 형태가 아닌 그래프에도 사용할 수 있다. 또는 미로 찾기와 같은 이차원 배열에도 사용할 수 있다.   동작 방식너비 우선 탐색은 방문한..

문제문제 : https://school.programmers.co.kr/learn/courses/30/lessons/258712친구들끼리 카카오톡 선물하기 기능을 사용해 선물을 주고받은 이번 달까지의 기록을 바탕으로 다음 달에 누가 선물을 많이 받을지 예측하고 싶다.두 사람이 선물을 주고받은 기록이 있으면, 두 사람 사이에 더 많은 선물을 준 사람이 다음 달에 선물 하나를 받는다.두 사람이 선물을 주고받은 기록이 없거나 그 수가 같으면, 선물 지수가 큰 사람이 작은 사람에게 선물 하나를 받는다.선물 지수는 이번 달까지 자신이 친구들에게 준 선물의 수에서 받은 선물의 수를 뺀 값이다.두 사람의 선물 지수가 같으면 다음 달에 선물을 주고받지 않는다.위의 규칙대로 선물을 주고받을 때, 다음 달에 선물을 가장 ..

문제 문제 : https://www.acmicpc.net/problem/11053 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하라. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 최장 증가 부분 수열 이런 문제는 일반적으로 최장 증가 부분 수열(LIS: Longest Increasing Subsequence) 문제라고 하는데, 동적 계획법으로 풀어낼 수 있는 유명한 알고리즘 풀이다. 최장 증가 부분 수열이란 임의의 수열에서 몇 개의 수를 제거하여 만들 수 있는 부분 수열 중 오름차순으로 정렬된 가 장 긴 수열을 의미한다. 예로 들어,..

문제 문제 : https://www.acmicpc.net/problem/2579 계단 오르기 게임은 계단 아래인 시작점부터 꼭대기인 도착점까지 가는 게임이다. 계단을 밟으면 계단에 쓰여있는 점수를 얻는다. 예로 들어 시작점에서 첫번째, 두번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 30 = 75점이 된다. 계단을 오를 때는 다음의 규칙을 지켜야 한다. 한 번에 한 계단 또는 두 계단 씩 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안된다. 단, 시작점은 계단에 포함되지 않는다. 도착 계단은 반드시 밟아야 한다. 각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오. 접근 dp 문제다!..

문제 문제 : https://www.acmicpc.net/problem/2193 이진수란 0과 1로만 이루어진 수를 말한다. 그중 0으로 시작하지 않으면서 1이 두 번 연속 나타나지 않는 수(1, 10, 100, 101)를 이친수(pinary number)라고 한다. 0010101, 101101은 0으로 시작하거나 1이 연속으로 나타나므로 이친수가 아니다. 수의 길이를 입력받아 해당 길이의 이친수의 개수를 구하여라. 접근 2024.04.04 - [백준] 11057 - 오르막 수와 비슷한 면이 있는데, 마지막 자리의 값에 따라 다음에 올 수 있는 수가 정해져 있다는 점이 특징이다. 1이 연속으로 나올 수 없다는 이친수의 성질을 만족해야 하기 때문이다. 따라서 숫자가 1로 끝나면 다음 길이의 이친수는 0으로..

문제 문제 : https://www.acmicpc.net/problem/1890 각 칸에 수가 적힌 N * N 크기의 게임판이 있다. 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프하여 이동하는 것이다. 각 칸에 적힌 수는 현재 칸에서 갈 수 있는 거리를 뜻한다. 단, 0은 종착점을 의미한다. 오른쪽이나 아래쪽으로만 이동할 수 있고, 한 번 점프하는 중간에 방향을 바꿀 수 없다. 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 수를 구하여라. 접근 2024.04.08 - [백준] 11048 - 이동하기와 비슷한 문제인데, '이동하기'는 한 번에 한 칸씩 움직이는 반면 '점프'는 이동할 수 있는 칸의 수가 정해져 있지 않다. 때문에 현재 위치..

문제 문제 : https://www.acmicpc.net/problem/11048 1 * 1 크기의 방에 사탕이 놓여져 있는 N * M 크기의 미로가 있다고 하자. 미로의 가장 왼쪽 윗 방의 좌표는 (1,1)이고, 가장 오른쪽 아랫방 좌표는 (N, M)이다. 또한 사람이 (r, c) 좌표의 방에 위치하고 있으면 (r+1, c), (r, c+1), (r+1, c+1) 방향으로만 이동할 수 있고, 방을 방문할 때마다 방에 놓여진 사탕을 모두 가져갈 수 있다. 사람이 (1,1) 좌표 방에서 (N, M) 좌표 방으로 미로를 빠져나온다고 할 때, 가져올 수 있는 사탕 개수의 최대값을 구하여라. 접근 이 문제도 동적 계획법과 관련된 문제다. 현재 위치한 방을 어떻게 왔는지 고려해보면 아래 그림을 떠올릴 수 있다. ..

문제 문제 : https://www.acmicpc.net/problem/10844 45656과 같이 인접한 자리수의 차이가 1인 수를 계단 수라고 한다. 수의 길이 n이 주어질 때, 길이가 n인 계단 수의 계수를 구하여라. 단, 0부터 시작하는 수는 계단 수가 아닌 것으로 취급한다. 접근 이 문제는 2024.04.04 - [백준] 11057 - 오르막 수와 비슷하게 동적 계획법으로 접근할 만한 문제다. 수의 길이가 1일 때, 계단 수의 1부터 9까지 수가 해당된다. 그리고 수의 길이가 2인 경우, 각 자리 수 마다 계단 수는 다음과 같이 생성할 수 있다. 개수를 표시하면 아래 그림과 같다. 참고로 0으로 시작하는 수의 개수는 다음 길이의 계단 수의 개수를 구할 때 구하기 위해서 구해야 한다. 즉, 숫자 ..