프로그래머스 AND 백준17 백준 16139 인간-컴퓨터 상호작용 간단한 dp 문제로 접근해서 풀었다.흐름은 다음과 같다. 1. 2차원 배열 int[][] dp = new int[알파벳의 개수][글자의 자리수] 로 설정한다. (3번째 자리까지의 c의 dp값은 dp['c' - 'a'][3])이다.2. dp를 돌려주는데 해당 알파벳인 경우 dp[][i] = dp[][i-1] + 1;을 해주고 이외의 경우에는 dp[][i] = dp[][i-1]을 해준다3. a ~ b번째 자리수의 경우 dp[][b] - dp[][a-1] 로 접근하면 되므로 이렇게 return하는 함수를 만든다. subtask가 있으므로 scanner대신 BufferReader와 StringBuilder 이용했다.package programers;import java.io.BufferedReade.. 2024. 5. 11. 백준 14889 스타트와 링크 java 팀 밸런스가 잘 맞아야 한다. 해결 아이디어는 다음과 같다. 1. n 수가 굉장히 적다. 20명중에서 10팀을 뽑는다고 해도 20 c 10이기 때문에 브루트포스로 해도 충분하다. 그래서 백트래킹을 쓰면 될 것 같았다.2. 일단 백트래킹으로 10팀을 뽑고, 2중 for문으로 team1의 시너지를 모두 sum에 더해준다.3. team1에 속하지 않은 팀 2의 시너지도 모두 필요하기 때문에 visited 배열 또한 만들어줘서 visited[]가 false인 값을 team2로 설정한다.4. Math.abs(sum1-sum2) 값을 Math.min(min, 절대값) 이렇게 해준다.5. min을 출력한다. package programers;import java.util.Scanner;public class .. 2024. 4. 29. 프로그래머스 호텔대실 우연히도 PriorityQueue를 배우자 마자 써먹을 기회가 생긴 것 같다.회의실 관련 문제는 이렇게 접근하면 된다. 1. 회의 전체를 시작시간 순서대로, 시작 시간이 동일하다면 끝나는 시간 순서대로 정렬한다.2. PriorityQueue를 만들어서 끝나는 시간 기준 오름차순으로 설정한다 (제일 빨리 끝나는 회의가 필요하기 때문)3. 회의 전체의 while문을 돌려서 만약 회의 시작 시간 기준 끝난 회의가 있다면 pq를 모두 poll해준다4. pq에 offer 해준다5. result = Math.max(result, pq.size())를 해준다 다만 시간이 String으로 되어있고 사용하기 불편했기 때문에 나같은 경우에는 시간이 있다면 :를 떼어버리고 parseInt를 해줬다.이럴 경우에는 00 : 5.. 2024. 4. 25. 비트마스크 알고리즘 풀다가 비트마스크라는 것을 처음알았다. 이진수를 이용해서 집합을 만든다고 이해하면 될 것 같다. 이해한 대로 설명하자면 비트 하나하나를 집합(set)으로 쓸 수 있다는 것이다. 큰 장점은 비트 하나 하나가 집합 하나 하나기 때문에 메모리 사용량이 극도로 적어진다는 것이다. ex) 10진수 2진수 16 1000 17 1001 31 1111 즉 만약 length가 4인 집합을 만들고 싶다면 이렇게 4비트의 메모리만 있어도 된다. 여기서 0,1이 false, true값이다. 1. 1 2024. 4. 11. 백준9019_DSLR 생각보다 별거 없었다. DSLR가져오는 아이디어만 고려하면 나머지는 그냥 기본 BFS로 접근하면 완성,. 아래와 같이 만들었다. 어차피 9999까지 만들고 visited 배열 있으니까 시간복잡도에 무리는 없을 것 같았다. 물론 test case가 많지만. - 참고 사항으로는 그냥 초기화만 해줬는데- 그렇게 되면 String 배열에서는 null값이 들어간다는 것을 알았지만서도 (이전것 + " ")를 통해서 graph 배열에 넣어주니까 예상과는 다르게 NullDSLR 이런식으로 들어갔다. 그래서 start 배열에는 그냥 "" 2024. 4. 11. 백준 14888번 재귀로 풀었다. 어차피 n의 최대 수는 11이고 연산자의 최대는 10, 즉 2 3 2 3 으로 나오고 처음으로 나오는 0이 가장 적을 때니까 2323 = 4 2223 = 4 2222 = 4 1222 = 4 1122 = 4 1112 = 4 1111 = 4 0111 = 3 0011 = 2 0001 = 1 0000 = 1 으로 나오는 경우의 수는 98304인 것 같다. 단순하게 4의 11승으로 계산해도 백만 대에서 멈추기 때문에 상관없다. 그냥 재귀 돌려도 된다. 아이디어는 다음과 같다. 1. 재귀를 이용해서 푼다. (base case는 depth가 nums 배열의 length -1과 같을 때, or 수식 배열의 모든 원소가 0일때), 즉 모든 원소에 대한 식을 끝마쳤을 때 2. 수식의 개수를 배열에 넣는다고.. 2024. 4. 3. 이전 1 2 3 다음
