전체 글361 [BOJ]2665번: 미로만들기 문제: https://www.acmicpc.net/problem/2665 parametric search + BFS 문제입니다. 몇 개의 검은 블럭을 바꿔야 이동 가능한지는 직접 시뮬레이션해보기전까지는 알 수 없습니다. 그러므로 최소 0개부터 최대 N^2 개의 블럭을 모두 바꾸는 경우까지 시도해봐야 합니다. N제한이 작으므로 O(N^4)으로 BFS를 돌려도 시간초과는 나지 않습니다. 그러나 0개에서부터 ~ N^2를 탐색하는 과정을 이분 탐색을 통해 O(log(N^2)^N2)으로 줄일 수 있습니다. Q. X개의 블럭을 바꿀 수 있을 때 board[N][N]에 도달가능한가? 를 결정하는 결정문제로 바꿀 수 있습니다. X가 주어진 조건을 만족한다면 상한을 줄여서 다시 탐색해보고, X가 조건을 만족하지 않으면 .. 2022. 3. 22. [BOJ]13116번: 30번 문제: https://www.acmicpc.net/problem/13116 수학 문제입니다. 최대 1024개의 노드가 있을 때 임의의 두 수가 주어지면 최대 공통 조상을 찾아야 합니다. 최대 공통 조상을 찾는 방법은 힙의 원리처럼 주어진 수 / 2 를 계속해서 1까지 가보면 거쳐가는 모든 수가 자신의 조상 노드입니다. 쿼리가 최대 5만개이고, 하나의 쿼리를 처리하는데 걸리는 시간은 O(10) 입니다. (최대 노드 크기가 1023이고 1023도 2^10 이기 때문에 나누기 2 연산의 최대 깊이는 10을 넘지않습니다.) 문제를 해결하는 방법은 여러가지입니다. 저는 주어진 수를 작은 수, 큰 수로 나눴고 작은 수가 거쳐간 모든 조상을 표시한 뒤, 큰 수의 모든 조상을 구하면서 한 번이라도 작은 수의 조상과 일.. 2022. 3. 17. [PRGRMS]92341번: 주차 요금 계산 문제: https://programmers.co.kr/learn/courses/30/lessons/92341 시뮬레이션 문제입니다. 주어진 정보를 입력받아 아래와 같이 처리를 하면 됩니다. 1. 시간을 분으로 환산하고 2. 해당 시간에 맞는 주차요금을 계산 저는 차량 번호가 작은 자동차부터 결과를 주기 위해 최종 연산결과는 treeMap에 담았습니다. 코드: https://github.com/cotchan/algorithm/blob/main/PRGRMS/%EC%A3%BC%EC%B0%A8%20%EC%9A%94%EA%B8%88%20%EA%B3%84%EC%82%B0.java 2022. 3. 17. [PRGRMS]42747번: H-Index 문제: https://programmers.co.kr/learn/courses/30/lessons/42747 시뮬레이션 문제입니다. 논문이 인용될 수 있는 최대 크기만큼 int[] 배열을 잡아놓은 뒤 논문 정보가 들어올 때 마다 해당 논문 인용 횟수를 ++ 해줍니다. int[] refCounts; refCounts[1] = 1번 인용된 논문의 갯수 refCounts[2] = 2번 인용된 논문의 갯수 refCounts[3] = 3번 인용된 논문의 갯수 H-Index의 최댓값을 구해야하므로 (최대 인용 횟수 ~ 최소 인용 횟수)만큼 for loop를 돌며 해당 인용 횟수가 H-Index 조건을 만족하는지 확인합니다. 만족하면 바로 break로 빠져나와서 해당 횟수를 정답으로 리턴하면 됩니다. H-Index .. 2022. 3. 17. 이전 1 ··· 6 7 8 9 10 11 12 ··· 91 다음
