Today's Algorithm(2019-03-13) baekjoon2163. 초콜릿 나누기 다이나믹 프로그래밍을 연습하려고 이 문제를 뽑았지만 수학 문제에 더 가까운 것 같습니다. 생각할 부분도 딱히 없어서 가볍게 정리하고 넘어가겠습니다. N * M길이의 초콜릿을 효율적으로 나누기 위해선 한번 금을 가를 때 최대한 길게 나누는게 좋겠죠? 가로로 나눈다고 생각해봅시다(세로 나누어도 결과는 같습니다). 그렇다면 가로가 N이라면 M - 1 번 나눌 수 있을 것입니다. 그렇다면 이젠 각 줄 안을 다 잘라야 합니다. 그 개수는 M - 1 줄에 N개씩 있으니 (M - 1) * N 이구요. 결과적으로 (M - 1) * N(M - 1) = NM - 1이 됩니다. 세로를 먼저 나눈다고 하더라도 NM - 1로 계산하는 ..
Today's Algorithm(2019-03-12) baekjoon11399. ATM 탐욕법에 대한 연습으로 뽑은 문제인데요. 사실 이 문제가 어떤 점에서 탐욕법인지 잘 모르겠습니다. 우선 문제를 풀 때 어떻게 하면 각 사람이 걸리는 시간을 최대한으로 줄일 것인가를 살펴봐야 하는데요. 그건 정렬에 있습니다. 만약 [1, 5, 3, 2, 4] 가 주어진다고 했을 때 3, 2, 4 걸리는 사람은 5를 다 더해주는 시간만큼 기다려야 합니다. 하지만 정렬이 되어 [1 2, 3, 4, 5]라면 큰 수를 더해주는 것을 피할 수 있겠죠. 결국 핵심은 빨리 끝날 사람은 먼저 끝내줘야 전체 기다리는 시간이 줄어든다는 것입니다. public class Main { public static void main(String[..
Today's Algorithm(2019-03-10) 한동안 프로그래머스에서 알고리즘 문제를 계속 풀어왔는데요. 하지만 제가 취약한 탐욕법, 다이나믹 프로그래밍을 좀 더 연습하고 싶어서 다시 백준으로 돌아왔습니다. 그 벽을 언제 넘을 수 있을지 모르겠지만 천천히 그리고 꾸준히 해보려 합니다. baekjoon 1010. 다리 놓기 이 문제를 보면 결국 조합을 구하는 문제라는 것을 알 수 있을 것입니다. n과 m을 입력으로 받을 때 nCm 을 구하면 되는 것이죠. 예전에 이것을 풀기 위해선 팩토리얼을 이용하여 n! / (n-m)! * m! 로 풀어서 쓸 수 있다는 것도 기억할 것이라 생각합니다. 근데 그냥 이렇게 풀면 다이나믹 프로그래밍이 아니죠. 최대한 효율적으로 풀어야 하는데 그 방법은 메모입니다. 이전..
정렬 알고리즘(Sorting Algorithm) 항상 정렬 헷갈리네요. 오름차순으로 정렬했을 때를 가정하고 정리해볼게요. Bubble Sort 인접한 두 개의 데이터를 비교해가면서 가장 큰 값을 배열 맨 끝에 두면서 정렬합니다. 한 턴마다 비교대상 중 가장 큰 값이 그 중 제일 뒤에 가도록 보장합니다. 시간 복잡도 : O(n^2) Selection Sort 앞에서부터 시작하여 해당 수보다 작은 수를 찾고, 만약 찾았으면 그 수랑 swap하고 없으면 (그 수가 가장 작은 수이기 때문에) 그대로 둡니다. 다음은 그 다음 인덱스부터 비교합니다. 한 턴마다 비교대상 중 가장 작은 값이 제일 앞에 가도록 보장합니다. 시간 복잡도 : O(n^2) Insertion Sort index 1부터 시작하여 해당 인덱스 아..
Today's Algorithm(2019-02-25) 오픈 채팅방 닉네임 변경만 제대로 체크해주면 큰 어려움은 없는 문제였습니다. 닉네임 변경은 Map 에서 가지고 있다가 들어올때, 변경할때만 해당 아이디에 대한 이름을 바꿔주면 됩니다. 사실 가장 뒤에 있는 것(가장 최신의 것)만 기억하면 되기 때문에 매번 들어올 때마다 Map에 넣기만 하면됩니다. 만약 있는 값이라면 새로운 값을 덮어쓰게 되고, 없으면 새로 넣어질 것이니까요. package p42888; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; class Solution { public String[] solution..
Today's Algorithm(2019-02-22) 최근 여러 일로 바빠서 알고리즘 정리를 제대로 못했네요. 그 동안 총 5문제를 풀었는데요. 어려웠던 2문제의 포인트만 정리해볼게요. 방금그곡 이 문제는 요구사항을 제대로 이해하는 것이 중요합니다. 각 음은 1분에 1개씩 재생된다는 점, 한 음악을 중간에 끊을 경우 원본에 기억한 멜로디가 들어있더라도 그 곡이 아닐 수 있다는 점이 중요합니다. 즉, 해당 재생시간 동안 멜로디를 구성하고 그 안에 기억한 멜로디가 들어있는지 확인하는 것이 핵심이죠. 재생시간의 중요성을 파악하지 못하고, String에서 사용할 수 있는 좋은 메서드를 활용하지 못하여 테스트 케이스 1개를 남겨두고 다른 사람의 코드를 참고했는데요. 결국 제가 문제를 제대로 이해하지 못했다는 것을..
