소소한 개발이야기

📄 문자열 [백준 1120번] 🔗 [전체 소스 코드] 🔗 [문제 풀러 가기] 문제는 2중 for문으로 해결하였습니다. 먼저 문제의 조건 및 접근하는 방법에 관하여 살펴보겠습니다. 문제는 두 문자열의 길이를 같게 만들고 각 차이를 최소로 만드는게 목적입니다. 여기서 가장 먼저 생각할 수 있는 방법은 만약 문자를 추가해야 한다면 앞, 뒤 어디든지 추가할 수 있으므로 앞에 추가한다면 Y의 첫 번째 문자를 X에 추가하고, 뒤에 추가한다면 Y의 마지막 문자를 X에 추가해서 차이를 최소로 해야겠다~ 라고 생각하신 분들은 저와 같이 잘못 접근한겁니다. 문제를 다시 살펴보면 문자열을 알고 싶은게 아니고 최소 차이만 알고 싶어합니다. 그렇다면 X의 앞, 뒤에 추가 할 문자는 어차피 내맘대로 넣는거니 신경쓰지 않아도 됩니..

📄 위장 🔗 문제 풀러가기 문제는 HashMap을 이용해 해결하였습니다. 문제의 의도는 도둑이 가진 옷의 이름과 옷의 종류(category) 가 주어지고, 여기서 도둑이 입을 수 있는 옷의 경우의 수를 구하는 문제 입니다. 문제의 조건을 보면 다음과 같습니다. 매일 입는 옷은 달라야 한다. 옷을 입거나 안입는 경우도 있다. 적어도 1개 이상의 옷은 입어야 한다. 처음 문제를 접근할 때 방향을 잘 잡아야 하는데 문제를 천천히 읽어보면 옷의 이름은 중요하지 않습니다. 문제에서 가장 중요한 부분은 옷의 종류별 갯수 입니다. 예제를 보면서 천천히 설명해보겠습니다. 예제 1 상의 : 반팔, 긴팔 하의 : 청바지, 반바지, 슬랙스 위의 예제를 보면 상의 2개, 하의 3개입니다. 문제에서 제시하는 것은 도둑이 어떤 ..

📄 비밀지도 🔗 문제 풀러가기 문제는 2진수의 OR연산을 이용해 해결하였습니다. 문제의 조건을 살펴보면 2개의 지도가 주어지는데 벽(#) 또는 공백으로 이루어져 있습니다. 예시에서 친절하게 2진수로 나타낼 수 있다고 알려주고 있습니다. 그렇다면 2개의 지도를 겹쳐 두 지도에서 모두 공백인 부분을 찾아내는 것이 목표인데 OR연산을 이용하면 쉽게 문제를 해결할 수 있습니다. 다만 문제의 입력이 2진수가 아닌 10진수로 주어지기 때문에 이를 2진수로 변경해야지 문제를 해결할 수 있습니다. 직접 변경해도 되지만 JAVA에서 10진수를 2진수로 변경시킬 수 있는 함수 Integer.toBinaryString을 활용해 문제를 해결할 수 있습니다. 주의사항 문제에서 주어지는 지도는 n x n 이지만 10진수를 2진수..

📄 가장 큰 수 🔗 문제 풀러가기 문제는 문자열의 정렬을 이용하여 해결하였습니다. 가장 큰 수를 만드는 방법은 가장 큰 수가 앞으로 오면 됩니다. 여기서 가장 큰 수는 0 ~ 9 중 가장 큰 수를 말합니다. 즉, 30 보다는 9가 앞으로 와야지 더 큰 수가 되는 것입니다. 처음 문제를 접근 할 때에는 그냥 문자열 정렬을 한 뒤 모든 수를 이어 붙이면 가능할거라 생각했지만 함정이 존재 했습니다. 아래는 문제의 예제중 하나 입니다. 예제 1 (3, 30, 34, 5, 9) 여기서 단순 문자열 정렬을 한다면 아래와 같은 순서로 정렬이 됩니다. (9, 5, 34, 30, 3) 이대로 이어 붙인다면 9534303이라는 결괏값이 나오게 되는데 문제의 정답은 9534330입니다. 즉 단순 정렬이 아니라 정렬의 조건을..

📄 여행 가자 [백준 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개 입니다. 그리디 알고..