Log

1. 문제이해 제일 먼저 애매했던 부분은 로봇청소기의 위치 였다. 지도의 북쪽에서부터 r번째, 서쪽에서부터 c번째로 위치한 칸이 로봇청소기의 위치로 주어졌는데, 벽에는 로봇청소기가 존재할 수 없으니 첫번째 테스트케이스를 보고 r의 범위가 [0:N), c의 범위가 [0:M)라는 것을 짐작할 수 있었다. 그 다음은 2-b의 설명을 제대로 이해하지 못했다. 질문검색 게시판을 통해 "1번으로 돌아가거나 후진"하지 않고 2a번 단계가 연속으로 4번 실행되는 것을 알 수 있었다. 또한 이 조건은 현재 위치에서 동서남북 모두 (벽 or 청소할 공간이 없음) 경우를 나타낸다. 여기까지 이해하는데 진짜 오래 걸렸다....ㅎ 2. 문제풀이 static class Position { int r, c, d; public Po..

Map이란? Key와 Value가 쌍으로 이루어진 자료구조 Key와 Value가 1:1 매핑되기 때문에 Key의 중복을 허용하지 않지만 Value의 중복은 허용한다. Map의 종류 1. HashMap 순서를 보장하지 않고, Key와 Value가 null이 허용된다. HashTable 구조 2. HashTable HashMap과 동일한 내부 구조, Key와 Value가 null이 될 수 없다. 동기화를 지원 → 멀티스레드 환경에서 Thread Safe 하다. 3. TreeMap 이진 검색 트리 구조, Key를 기준으로 정렬하여 저장된다. 4. LinkedHashMap HashMap 구조 head, tail 변수가 추가되어 Double-LinkedList로 순서를 유지한다.

Hash Function(해시 함수) 해시함수 또는 해시 알고리즘은 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수를 말한다. 고정된 길이의 데이터로 매핑하는 과정을 해싱(hashing)이라고 하고 해시 함수에 의해 얻어지는 값을 해시 값, 해시코드 또는 해시(hash) 라고 한다. 해시함수의 조건 1. 하나의 출력에 대하여 이 출력으로 매핑하는 입력을 찾는 것이 계산적으로 불가능하다. 2. 하나의 입력에 대하여 같은 출력으로 매핑시키는 다른 입력을 찾는 것이 계산적으로 불가능하다. Hash Table(해시 테이블) 입력 키 값을 해시함수를 사용하여 해시를 얻고, 그 해시 값을 인덱스로 사용하여 value를 저장하는 자료구조. 고유한 인덱스에 저장을 하기 때문에 추가/삭제 시 데이터를 이동할..

public static int specialAward(int row, int col, int n) { if(n == 1) { return arr[row][col]; } int mid = N/2; PriorityQueue pq = new PriorityQueue(); pq.offer(specialAward(row, col, mid)); pq.offer(specialAward(row, col+mid, mid)); pq.offer(specialAward(row+mid, col, mid)); pq.offer(specialAward(row+mid, col+mid, mid)); pq.poll(); return pq.poll(); } 보자마자 재귀 문제라고 생각해서 recursion 메소드를 만들어 제출했지만 메모..

이 문제는 가장 긴 증가하는 부분 수열4(https://www.acmicpc.net/problem/14002)에서 범위만 달라진 문제이다. 일단 입력값이 1,000,000이므로 DP로 풀게 될 경우 1,000,000의 제곱을 하면... 무조건 시간초과가 날 것이다. 이분탐색을 이용하여 시간복잡도를 O(N logN)로 낮춰야 한다. 14002번 문제를 풀 때 이분 탐색을 이용해서 구해봤는데 잘 안구해져서 DP로 바꿨는데... 이 문제를 약 2-3시간 동안 끙끙댔다...ㅠㅠ 인덱스를 이용해야 될 것 같다는 것은 알아챘는데 제출하면 반례가 계속계속 나왔다...하하 결국 G님의 힘을 빌렸다... https://dragon-h.tistory.com/35 [백준 14003: JAVA] 가장 긴 증가하는 부분 수열 ..

가장 긴 증가하는 부분 수열은 5까지 있다. 3까지와의 다른 점은 부분 수열을 출력하는 것. LIS를 구하는 방법은 3가지가 있다. 1. 완전탐색 - O(N^2) 2. DP - O(N^2) 3. 이진탐색 활용 - O(N logN) 완전탐색과 DP는 시간복잡도가 같지만 DP로 푸는 방법이 훨씬 간결하다. 가장 긴 증가하는 부분 수열3까지는 이진탐색을 활용하는 방법으로 풀었다. 하지만 이 문제는 이진탐색으로 풀 수 없다. 이진탐색을 활용하는 방법은 LIS의 길이는 구할 수 있지만, 부분 수열의 원소를 구할 순 없기 때문에... (구할 수 있었다...! 2022.04.06 - [알고리즘/BOJ] - [백준] 14003. 가장 긴 증가하는 부분 수열5 - Java 이 글을 참고하시길...) 따라서 이 문제는 D..

당연히 시간초과가 나왔다^^ N이 최대 3,000,000이고 k은 최대 3000이므로 완전탐색을 하면 3,000,000 * 3,000번 다른 방법을 찾아야 한다. 1시간동안 고민하다가 알고리즘 분류를 봤다... 투포인터는 대애애충 알지만 슬라이딩도어는 처음 들어봐서 구글을 찾아봤다. k = 4 이므로 0번째부터 3번째까지 초밥의 종류를 관리한다. 그리고 start는 0, end는 3을 가리킨다. 다음 단계는 0번째 초밥을 관리하는 부분에서 제거하고 start 값을 1 증가시켜주고, end 값을 1 증가시켜 end번째 초밥을 관리하는 부분에 추가한다. 그러면 7-9-7-30 에서 9-7-30-2 다음으로 넘어갈 때 양 끝에 있는 초밥들만..

최장 증가 수열(LIS) 배열 순서를 유지하면서 크기가 점진적으로 커지는 가장 긴 부분집합의 길이 예를 들어 {4, 8, 1, 2, 5}라는 수열이 있다면 {1, 2, 5}의 길이가 3으로 제일 길다. 접근방법 1. Brute Force 모든 부분집합을 구하고, 각각의 부분집합이 증가수열인지 판별 모든 부분집합의 개수는 2^n이므로 시간복잡도가 O(2^n)이 된다. 2. DP int[] DP = new int[N+1] 생성 DP[i]는 A[i]가 부분집합 수열의 마지막 원소일 때 최장길이(최적해)를 저장한다. 밖의 for문은 N번, 안의 for문은 i-1번 돌기때문에 시간복잡도는 O(2^n)이 된다. int N = 5;// A의 길이 int[] A = {4, 8, 1, 2, 5}; int[] DP = ..

1. 현재 계단을 올라올 때 두 칸을 올라왔을 경우 두 계단 전의 점수 중 최대값과 현재 계단의 점수를 더한다. F[k][0] = Math.max(F[k-2][0], F[k-2][1]) + values[k]; 2. 현재 계단을 올라올 때 한 칸을 올라왔을 경우 전 계단을 올라갔었을 때 한 칸 밟고 올라간 상태여야 하므로, 전 계단을 한칸 밟고 올라갔을 때 점수와 현재 계단의 점수를 더한다. F[k][1] = F[k-1][0] + values[k]; 코드는 아래와 같다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class BJ_2576_계단오르기 { public stat..