목록알고리즘 (19)
소소한 개발이야기
📄 NN [백준 11944번] 🔗 [전체 소스 코드] 🔗 [문제 풀러 가기] 문제는 매우 간단하다. N을 N번 출력하는 프로그램을 작성하여라. 다만, 답이 길어지는 경우 답의 앞 M자리만 출력한다. 다만 길어지는 경우는 N을 N번 출력했을 때 길이가 M보다 클 경우입니다. 문제에서 얘기한 것 처럼 매우 간단한 문제였습니다. 문제 풀이 N을 N번 더해준 문자열 NN을 구한다. NN의 길이가 M보다 작다면 NN 출력 NN의 길이가 M보다 크다면 NN의 subString(0, m) 출력 글보단 코드를 보면 더 이해하기 쉽습니다. 🌱 main 함수 public static void main(String[] args) throws IOException { String[] input = br.readLine().s..
📄 프린터 🔗 문제 풀러가기 Queue를 이용해 문제를 풀 수 있습니다. 문제는 다음과 같이 접근할 수 있습니다. 먼저 인쇄 대기목록의 index와 해당 인쇄물의 priority를 저장하는 PrintItem Class를 정의해줍니다. 🌱 PrintItem Class class PrintItem { int index; int priority; public PrintItem(int index, int priority) { this.index = index; this.priority = priority; } } 그리고 주어진 인쇄 대기목록을 모두 Queue에 넣습니다. 이 후 Queue의 가장 첫 번째 원소를 대기상태로 뺀 다음 Queue에 남은 인쇄 목록 중 대기상태의 priority값 보다 큰 원소들의 개..
📄 방문 길이 🔗 문제 풀러가기 단순 구현문제 입니다. 문제의 조건은 총 2가지로 주어져 있습니다. 첫 번째로, 주어진 좌표 평면 안에서만 움직여야 하고 두 번째로, 한 번 갔던 길은 카운팅 하지 않는다 입니다. 문제 풀이 접근 방식은 다음과 같이 할 수 있습니다. 먼저, 맵에서 캐릭터가 움직인 경로를 체크하는 4차원 배열을 생성합니다. 4차원이라 조금 헷갈릴 수도 있지만 동작 방식은 다음과 같이 설정할 수 있습니다. 예를 들어, 현재의 위치를 curX, curY라 하고 움직인 위치를 dx, dy라 한다면 캐릭터가 움직인 경로는 [curx][curY][dx][dy] 입니다. 만약 움직이는 경로가 처음 가는 길이라면 카운팅을 해주면 됩니다. 여기서 주의해야 할 점은 캐릭터가 움직인 경로를 체크할 때 양 방..
📄 스킬트리 🔗 문제 풀러가기 문제에서 주어진 조건은 생각보다 단순합니다. 먼저 모든 문자열은 알파벳 대문자로만 이루어져 있습니다. 그리고 스킬의 총 길이는 최대 26이며 중복 또한 없습니다. 완전 탐색으로 진행해도 쉽게 문제를 해결할 수 있는 유형입니다. 문제 풀이 접근 방식은 다음과 같이 할 수 있습니다. 스킬트리 안에 스킬 순서에 포함되는 스킬이 있을 시 선행 스킬을 배웠는지 확인합니다. 여기서 문제를 조금 단순화 시킬 수 있는데 현재 스킬을 배우기 위해 이전의 모든 선행 스킬을 다 확인 할 필요가 없습니다. 바로 이전의 선행 스킬만 확인하면 됩니다. 만약 이전의 선행 스킬을 배우지 않았다면 이미 이루어 질 수 없는 조합이기 때문입니다. 여기서 주의해야 할 점은 스킬의 index가 0번째라면 out..
💡 [BOJ #1463번] (1로 만들기) 문제 풀이 🔗 [소스 코드] 다이나믹 프로그래밍의 기본적인 문제라고 말합니다. 하지만 다이나믹 프로그래밍을 접해보지 않은 사람들에게는 너무 어렵게 느껴집니다. 문제를 어떻게 접근하는지에 대해 살펴봅시다. 다이나믹 프로그래밍은 점화식을 세우는 것에서 부터 시작합니다. 그리고 문제를 푸는 방식은 두 가지가 존재하는데 재귀 호출을 이용하는 방법과 반복문을 이용하는 방법이 있습니다. 전자의 경우 Top-Down방식이라고 하며 가장 먼저 호출하는 문제가 가장 큰 문제이기 때문이며, 후자의 경우 Bottom-Up 방식이라고 하며 가장 작은 문제부터 차례대로 답을 쌓아 올려가기 때문입니다. 두 접근법 모두 이미 구해진 문제를 재활용 한다는 개념이 내포되어 있습니다. 🌱 To..
💡 [BOJ #6359] (만취한 상범) 문제 풀이 🔗 [소스 코드] 문제는 다이나믹 프로그래밍으로 분류되어 있지만 도저히.. 다이나믹으로는 생각이 나질 않아서 야매?로 풀었다. 먼저 모든 방의 문의 상태를 나타내는 boolean[] stateOfRoom을 정의한다. 각 index는 방의 번호이며 false일 경우 문이 열려 있다고 가정한다. 문제를 보면 각 방의 번호의 배수가 되는 방의 문을 열고 닫는 문제이므로 2중 for문을 돌며 방 문의 상태를 바꿔주면 되는 쉬운문제다. 여기서 굳이 if문으로 방의 상태를 확인 할 필요 없이 무조건 열려 있으면 닫고, 닫혀 있으면 연다 for (int i = 2; i
[BOJ #11052번] (카드 구매하기) 문제 풀이 🔗 [소스 코드] 다이나믹 프로그래밍 입니다. 많은 문제를 접해봐야지 쉽게 접근할 수 있을거 같습니다. 문제를 풀기전에는 쉬워 보였지만 시간이 너무 오래 걸렸네요. 문제를 풀면서 느낀건 Bottom-Up과 Top-Down 두 방식 모두 풀어봐야 한다는 점이었습니다. 문제에 접근하는 방식을 한 번 살펴봅시다. 문제에서 구하고자 하는 것은 카드를 구매하는데 최댓값을 구하는 문제입니다. 카드를 구매할 수 있는 방법은 카드 팩을 구매하는 것인데 i개의 카드가 들어있는 팩 ~ N개의 카드가 들어있는 팩로 구성되어 있습니다. 각 팩마다 value가 정해져 있는데 문제에서 원하는 것은 N개의 카드를 구매하는데 어떤 팩의 조합이 가장 큰 value값을 가지냐는 것입..
