소소한 개발이야기

📄 여행 가자 [백준 1976번] 🔗 [전체 소스 코드] 🔗 [문제 풀러 가기] 문제는 BFS로 해결하였습니다. 먼저 문제의 조건을 보면 여행 계획이 주어지는데 주어진 모든 도시를 여행할 수 있는지 여부를 판단하는 문제 입니다. 여기서 확인해야 할 부분은 중간에 다른 도시를 경유해서 여행을 할 수도 있다는 점입니다. 문제풀이는 다음과 같이 진행할 수 있습니다. BFS를 이용해 문제를 해결하였으므로 한 도시에서 갈 수 있는 모든 도시를 탐색합니다. 여기서 갈 수 있는 모든 도시를 큐에 넣습니다. 그다음 Queue에서 한 원소씩 빼면서 해당 도시에서 갈 수 있는 모든 도시들을 전부 집어 넣습니다. 이렇게하면 처음 도시에서 중간에 다른 도시를 경유해서 갈 수 있는 모든 도시를 확인할 수 있습니다. 문제를 풀 ..

📄 기타줄 [백준 1049번] 🔗 [전체 소스 코드] 🔗 [문제 풀러 가기] 문제는 단순 수학 문제로 해결하였습니다. 문제의 조건을 살펴보면 다음과 같습니다. 모든 브랜드에서 세트 또는 낱개로 구매할 수 있다. 모든 브랜드에서 패키지 안에 들어있는 줄의 개수는 6개로 동일하다. 세트 또는 낱개의 가격은 0원 이상이다. 필요한 기타줄을 가장 싼 가격으로 구매해야 한다. 가장 싼 가격으로 필요한 기타줄을 구매하기 위해 필요한 것은 결국 가장 낮은 구매 가격 입니다. 즉, 모든 브랜드 중 가장 낮은 세트 구매 가격과 가장 낮은 낱개 구매 가격을 적절하게 섞어서 구매를 하면 가장 싼 가격으로 구매할 수 있습니다. 따라서 모든 브랜드의 가격 정보를 알 필요 없이 가장 싼 세트 가격과 가장 싼 낱개 가격만 알고 있..

📄 잃어버린 괄호 [백준 1541번] 🔗 [전체 소스 코드] 🔗 [문제 풀러 가기] 문제는 String배열과 split으로 문자열을 나누어 문제를 해결하였습니다. 문제를 단순하게 들여다 보면 쉽게 해결할 수 있는 단순 수학 문제입니다. +와- 기호만 있는 연산에서 결괏값을 가장 작게 만들기 위한 방법은 -기호를 기준으로 괄호를 만드는 것입니다. 즉 모든 -기호를 기준으로 괄호를 만들어 다음 -기호를 만나기 전까지 모든 +기호를 -연산으로 바꾸는 것입니다. 아래 예시를 보면 쉽게 이해할 수 있습니다. 문제 예시 : 55-50+40-30+40+30-20 위와 같은 문제가 주어 졌을 때 -기호를 기준으로 괄호를 만들면 아래와 같이 만들어 집니다. 55 - (50+40) - (30+40+30) - 20 즉, -..

📄 거스름돈 [백준 5585번] 🔗 [전체 소스 코드] 🔗 [문제 풀러가기] 그리디 알고리즘의 기본적인? 문제 입니다. 문제의 조건을 살펴보면 거스름돈을 거슬러 줄 때 동전의 개수를 최소로 만들어야 합니다. 동전 개수를 최소로 만들려면 단위가 큰 동전의 개수가 많아야 합니다. 문제의 예시를 보면 설명을 해보겠습니다. 문제에서 내야 할 금액은 380엔 입니다. 그러면 거스름돈은 620엔을 거슬러 줘야 합니다. 먼저 가장 큰 금액인 500엔 1개를 사용해 120원을 남길 수 있습니다. 그 다음 100엔 1개를 사용해 20원을 남길 수 있습니다. 그 다음 50엔은 남은 금액보다 크기 때문에 사용할 수 없으며 10엔 2개로 남은 금액을 모두 거슬러 줄 수 있습니다. 따라서 최소 개수는 4개 입니다. 그리디 알고..

📄 대회 or 인턴 [백준 2875번] 🔗 [전체 소스 코드] 🔗 [문제 풀러가기] 그리디 알고리즘 분류에 있는 문제입니다. 문제의 입력은 대회에 참가하는 인원인 여학생 M명과 남학생 N명이 주어지고 인턴에 참여해야 하는 인원 K명이 주어집니다. 인턴쉽에 K명은 반드시 참가해야 하기 때문에 대회에 참여하는 인원은 인턴쉽에 참가해야하는 인원을 뺀 나머지가 참가할 수 있습니다. 문제의 조건을 나열해보면 다음과 같습니다. 대회는 팀으로 참가 가능 하며 여자 2명, 남자 1명으로 구성되어야 한다. 대회에 참가하려는 인원중 K명은 반드시 인턴쉽에 참가하여야 한다. 인턴쉽에 참가하는 인원은 대회를 참여할 수 없다. 대회에 참가할 수 있는 최대 팀의 개수를 구한다 문제 풀이는 다음과 같이 할 수 있습니다. 먼저 인턴..

💡 [BOJ #11945번 JAVA] (뜨거운 붕어빵) 문제 풀이 🔗 [소스 코드] 단순 swap 문제 입니다. 붕어빵 모양이 2차원 배열로 주어지는데 각 행을 역순으로 바꿔주기만 하면 되는 문제 입니다. 문자열 역순으로 출력 등의 문제와 같은 문제라고 볼 수 있습니다. 여기서 확인해야 할 점은 각 행을 역순으로 바꿀 때 모든 index를 확인하는 것이 아닌 열(col)의 1/2만 확인하며 역순으로 변경할 수 있다는 점 입니다. 🌱 붕어빵의 모양을 입력받는 함수 public static void inputShapeOfBoong(int[][] shapeOfBoong, int n, int m) throws IOException{ for (int i = 0; i < n; i++) { String inputMa..

💡 [BOJ #1463번] (1로 만들기) 문제 풀이 🔗 [소스 코드] 다이나믹 프로그래밍의 기본적인 문제라고 말합니다. 하지만 다이나믹 프로그래밍을 접해보지 않은 사람들에게는 너무 어렵게 느껴집니다. 문제를 어떻게 접근하는지에 대해 살펴봅시다. 다이나믹 프로그래밍은 점화식을 세우는 것에서 부터 시작합니다. 그리고 문제를 푸는 방식은 두 가지가 존재하는데 재귀 호출을 이용하는 방법과 반복문을 이용하는 방법이 있습니다. 전자의 경우 Top-Down방식이라고 하며 가장 먼저 호출하는 문제가 가장 큰 문제이기 때문이며, 후자의 경우 Bottom-Up 방식이라고 하며 가장 작은 문제부터 차례대로 답을 쌓아 올려가기 때문입니다. 두 접근법 모두 이미 구해진 문제를 재활용 한다는 개념이 내포되어 있습니다. 🌱 To..

💡 [BOJ #6359] (만취한 상범) 문제 풀이 🔗 [소스 코드] 문제는 다이나믹 프로그래밍으로 분류되어 있지만 도저히.. 다이나믹으로는 생각이 나질 않아서 야매?로 풀었다. 먼저 모든 방의 문의 상태를 나타내는 boolean[] stateOfRoom을 정의한다. 각 index는 방의 번호이며 false일 경우 문이 열려 있다고 가정한다. 문제를 보면 각 방의 번호의 배수가 되는 방의 문을 열고 닫는 문제이므로 2중 for문을 돌며 방 문의 상태를 바꿔주면 되는 쉬운문제다. 여기서 굳이 if문으로 방의 상태를 확인 할 필요 없이 무조건 열려 있으면 닫고, 닫혀 있으면 연다 for (int i = 2; i