Dev:P

문제 이번에 다뤄볼 문제는 1759번 문제 '암호 만들기'입니다. 우선 문제를 분석해보도록 하겠습니다. 문제에서 원하는건 "주어진 문자들을 활용하여 L개의 문자로 구성된 암호문자열을 만들어내라" 입니다. 첫째 줄에서 두 정수를 입력받습니다. L = 암호문자의 글자수, C = 암호를 구성할 문자들의 수 두번째 줄에서는 C개 만큼의 암호구성이 주어지네요. 그리고 여기서 조건이 두가지가 주어졌습니다. 1. 최소 한 개의 모음, 최소 두 개의 자음 으로 구성된 암호여야 한다. 2. 각 알파벳 암호는 오름차순을 갖는다. 두번째 조건의 경우 Arrays.sort() 메서드를 통해 입력받은 C개의 암호문자를 미리 정렬을 시켜놓고 진행하면 쉽게 만족시킬 수 있으니 첫번째 조건에 대해서만 메서드를 하나 만들어 체크하면 ..

문제 이번에 다뤄볼 문제는 11726번 문제 '2xn 타일링'입니다. 2xn 타일링 문제에서 연습해야 하는 key-point는 DP입니다. DP(Dynamic Programing)는 이름때문에 어려워 하시는 분들이 많습니다. DP는 쉽게 말하면 어려운 또는 커다란 문제를 작은 문제들로 나눠서 풀이하겠다 인데요. 작은 문제들을 해결해서 메모해놓고 나중에 더 큰 문제를 해결하면서 같은 작은 문제를 만난다면 앞서 풀었던 작은 문제의 결과를 활용하는 방식입니다. 해당 문제에서 주어진 큰 문제는 2xn 사이즈의 직사각형이며 이를 작은 직사각형인 2x1과 1x2 타일로 채워나가는 문제입니다. 목적지인 n까지 반복문을 수행하며 계속해서 이전에 해결한 작은문제들을 더해가면 완성됩니다. 문제에서 제시한 입력의 범위 중 ..

문제 이번에 다뤄볼 문제는 1463번 문제 '1로 만들기'입니다. 1로 만들기 문제에서 연습해야 하는 key-point는 DP입니다. DP(Dynamic Programing)는 이름때문에 어려워 하시는 분들이 많습니다. 그렇다고 해서 동적계획법에 대해 구글링하며 찾아보실 필요는 없습니다. DP는 쉽게 말하면 어려운 또는 커다란 문제를 작은 문제들로 나눠서 풀이하겠다 인데요. 작은 문제들을 해결해서 메모해놓고 나중에 더 큰 문제를 해결하면서 같은 작은 문제를 만난다면 앞서 풀었던 작은 문제의 결과를 활용하는 방식입니다. 문제에서 주어진 1로 만들기의 경우 총 3가지의 연산방식이 있습니다. 3으로 나누기 / 2로 나누기 / 1 빼기 이 3개의 연산을 갖고 dp[]라는 메모장에 작은 문제부터 올라가며 해결하고..

문제 이번에 다뤄볼 문제는 2667번 문제 '단지번호붙이기'입니다. 단지번호붙이기 문제에서 연습해야 하는 key-point는 DFS입니다. DFS(깊이 우선 탐색)이란 맹목적 탐색방법의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식입니다. 문제에서 원하는건 총 몇개의 단지가 존재하는지, 그리고 그 단지들이 갖고있는 각 집의 총 수를 오름차순 정렬으로 보여달라 입니다. 제공받은 map을 순회하며 집을 뜻하는 1을 만날경우 해당 포인트에서 바로 깊이우선탐색을 시작합니다. 탐색을 시작하는 포인트에서부터 상,하,..

문제 이번에 다뤄볼 문제는 5014번 문제 '스타트링크'입니다. 스타트링크 문제에서 연습해야 하는 key-point는 BFS입니다. 너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법입니다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용합니다. 따라서 해당 문제를 풀기 위해 앞으로 탐색을 시작할 층을 담을 queue를 하나 만들고 방문한 층을 기록할 visited 배열을 하나 만듭니다. visited에 담기는 값이 곧 방문 횟수가 되는데요. 예를들면 4층에서 시작할 경우 visited[4]의 값은 1부터 시작합니다. (한번에 방문했다..

문제 이번에 다뤄볼 문제는 7569번 문제 '토마토'입니다. 토마토 문제에서 연습해야하는 key-point는 BFS입니다. BFS는 너비 우선 탐색을 뜻하는데요. 너비 우선 탐색은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법입니다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용합니다. 이 문제는 7576번(토마토) 문제에서 살짝 응용 된 문제입니다. 기존에서는 x,y에 의한 방향 이동만 존재했다면 이 문제에서는 z축 방향의 이동을 생각해 주면 됩니다. 그 외 문제를 푸는 방식은 7576번과 같습니다. 백준 알고리즘 7576번 (토마토) 문제 이번에 다뤄볼 문제는 7576번 문제 '토마토'입니..

문제 이번에 다뤄볼 문제는 7576번 문제 '토마토'입니다. 토마토 문제에서 연습해야하는 key-point는 BFS입니다. BFS는 너비 우선 탐색을 뜻하는데요. 너비 우선 탐색은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법입니다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용합니다. BFS를 활용하여 토마토가 익어나가는것을 탐색 할 수 있으며 탐색되어 익게되는 토마토의 값을 1로 map에서 바꿔줍니다. visited 2차원 배열에 탐색 횟수를 증가시켜가며 저장해 줍니다. 모든 탐색이 끝난 후 map에 아직 익지 않은 토마토(0)가 존재한다면 이는 토마토가 모두 익지 못하는 상황이므로 예외처..

문제 이번에 다뤄볼 문제는 1527번 문제 '금민수의 개수'입니다. 금민수의 개수 문제에서 연습해야하는 key-point는 큐입니다. 큐(queue)란 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 뜻합니다. A와B사이에 존재하는 모든 금민수의 개수를 구하는 문제 입니다. 해당 문제의 test case 값 범위가 1,000,000,000이기 때문에 변수를 선언알때 long long int 를 활용하였습니다. 큐에 기본 금민수인 4 와 7을 초기값으로 넣어놓고 이들 각각의 자리수를 한 자리씩 올려주며 4,7을 더해줍니다. 그 후 바꾼 수를 큐에 넣습니다. ex) 4,7 -> 44,47,74,77 -> 444,..

문제 이번에 다뤄볼 문제는 1526번 문제 '가장 큰 금민수'입니다. 가장 큰 금민수 문제에서 연습해야하는 key-point는 큐입니다. 큐(queue)란 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 뜻합니다. 금민수는 4와 7로만 이루어진 수를 말합니다. 입력받은 n을 4가 될때까지 1씩 줄여나가며 해당수를 각 자리수 별로 잘라 큐에 집어 넣습니다. 큐를 하나씩 빼며 4혹은 7을 갖는 수 라면 count값을 증가시켜줍니다. 큐에 들어갔던 자리수의 갯수(rear)가 count된 수와 같다면 이는 4와 7로만 이루어진 수 이므로 금민수입니다. 아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다. 코드(..

문제 이번에 다뤄볼 문제는 7562번 문제 '나이트의 이동'입니다. 나이트의 이동 문제에서 연습해야하는 key-point는 BFS와 큐입니다. BFS는 너비 우선 탐색을 뜻하는데요. 너비 우선 탐색은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법입니다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용합니다. 큐(queue)란 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)구조로 저장하는 형식을 뜻합니다. 나이트가 이동 할 수 있는 8방향을 dirX,dirY배열에 입력합니다. 그리고 나이트의 다음 탐색 가능 위치를 큐에 넣..