본문 바로가기
반응형

전체 글1307

[BOJ] 백준 14681 사분면 고르기 출처: https://www.acmicpc.net/problem/14681 Input 9 -13 Output 4 ※ x, y ≠ 0 이므로, 경계선에 존재하지 않습니다. #include using namespace std; int main(void) { int x, y; cin >> x >> y; if(x > 0 && y > 0){ cout 0){ cout 2021. 2. 26.
[BOJ] 백준 11651 좌표 정렬하기 2 출처: https://www.acmicpc.net/problem/11651 Input 5 0 4 1 2 1 -1 2 2 3 3 Output 1 -1 1 2 2 2 3 3 0 4 - 우선순위 큐와 Comparable을 이용해 구현 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = null; int N = Integer.parseInt(br.readLine()); PriorityQu.. 2021. 2. 26.
[BOJ] 백준 11650 좌표 정렬하기 출처: https://www.acmicpc.net/problem/11650 Input 5 3 4 1 1 1 -1 2 2 3 3 Output 1 -1 1 1 2 2 3 3 3 4 Java API 중 Comparator를 이용해 정렬 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = null; int N = Integer.parseInt(br.readLine()); List list.. 2021. 2. 26.
[BOJ] 백준 1605 반복 부분문자열 출처: https://www.acmicpc.net/problem/1605 접미사 배열(Suffix Array) 접미사 배열(Suffix Array) 접미사 배열(Suffix Array) 접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해 놓은 배열. ex) S = "banana"에는 접미사가 총 6 개 있습니다. "banana", "anana", "nana", "ana", "na", "a" ▶Suffix.. zoosso.tistory.com LCP (Longest Common Prefix) LCP (Longest Common Prefix) LCP (Longest Common Prefix) LCP는 두 접미사의 최대 공통 접두사의 길이를 의미 ※ 앞서 접미사 배열(Suffix Array)에 대해서 .. 2021. 2. 26.
[BOJ] 백준 9248 Suffix Array 출처: https://www.acmicpc.net/problem/9248 접미사 배열(Suffix Array) 접미사 배열(Suffix Array) 접미사 배열(Suffix Array) 접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해 놓은 배열. ex) S = "banana"에는 접미사가 총 6 개 있습니다. "banana", "anana", "nana", "ana", "na", "a" ▶Suffix.. zoosso.tistory.com LCP (Longest Common Prefix) LCP (Longest Common Prefix) LCP (Longest Common Prefix) LCP는 두 접미사의 최대 공통 접두사의 길이를 의미 ※ 앞서 접미사 배열(Suffix Array)에 대해서 .. 2021. 2. 26.
[BOJ] 백준 11656 접미사 배열 출처: https://www.acmicpc.net/problem/11656 - 문자열을 자르는 것은 substring() 이용. - 접미사를 오름차순 정렬은 Collections.sort() 이용 ※ 배열 이용시 Arrays.sort()도 존재. 접미사 배열(Suffix Array) 접미사 배열(Suffix Array) 접미사 배열(Suffix Array) 접미사 배열은 문자열 S의 모든 접미사를 사전순으로 정렬해 놓은 배열. ex) S = "banana"에는 접미사가 총 6 개 있습니다. "banana", "anana", "nana", "ana", "na", "a" ▶Suffix.. zoosso.tistory.com LCP (Longest Common Prefix) LCP (Longest Common .. 2021. 2. 26.
[BOJ] 백준 1328 고층빌딩 출처: https://www.acmicpc.net/problem/1328 Input 3 2 2 Output 2 ▶ 동적계획법(Dynamic Programming, DP) 동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 zoosso.tistory.com N개의 빌딩을 재배열하는 경우의 수는 O(N!)이며, 좌우에서 보여지는 빌딩의 개수를 구한다면 O(N × N!)으로 TLE 발생. DP[i][L][R] = i 번째 빌딩을 배치할 때, 왼쪽에서 보이는 빌딩 수 L / 오른쪽에서 보이는 빌딩 수.. 2021. 2. 26.
[BOJ] 백준 8895 막대배치 출처: https://www.acmicpc.net/problem/8895 Input 4 4 1 2 4 1 1 5 2 4 20 2 1 Output 2 0 4 6402373705728000 ▶ [BOJ] 1328 고층빌딩와 동일한 문제로 해당 풀이 참조 [BOJ] 백준 1328 고층빌딩 출처: https://www.acmicpc.net/problem/1328 Input 3 2 2 Output 2 N개의 빌딩을 재배열하는 경우의 수는 O(N!)이며, 좌우에서 보여지는 빌딩의 개수를 구한다면 O(N × N!)으로 TLE 발생. DP[i][L][R] = i.. zoosso.tistory.com ▶ 동적계획법(Dynamic Programming, DP) 동적계획법(Dynamic Programming, DP) 동적 .. 2021. 2. 26.
[BOJ] 백준 2505 두 번 뒤집기 출처: https://www.acmicpc.net/problem/2505 Input 10 6 7 8 2 1 5 4 3 9 10 Output 1 5 3 8 초기에 1...N 까지 정상 문자열을 두 번 뒤집어서 Input Data로 주어지는 것이기 때문에 무조건 답인 두 구간을 출력해야 합니다. - 앞쪽에서부터 뒤집기 2번 내로 성공할 수 있는지 확인 - 뒤쪽에서부터 뒤집기 2번 내로 성공할 수 있는지 확인 뒤집기(Reverse()) 연산을 사용해야 하는 시점은 다음과 같습니다. 배열 인덱스에 맞는 값이 오지 않았을 때입니다. array[i] ?= i 이를 앞쪽과 뒷쪽 각각 수행합니다. # 뒤집기 1번 필요한 경우 Input 10 1 2 3 6 5 4 7 8 9 10 Output 4 6 1 1 # 뒤집기 0.. 2021. 2. 26.
[BOJ] 백준 5620 가장 가까운 두 점의 거리 출처: https://www.acmicpc.net/problem/5620 Input 3 5 5 0 0 -3 -4 Output 25 N의 범위가 충분히 크기 때문에 완전 탐색이나 분할 정복 기법으로는 TLE 발생. Line Sweep 알고리즘을 사용합니다. ※ y 좌표 기준에 따른 비교대상 선정을 TreeSet을 이용해서 시간 효율 Up set에는 항상 입력받은 배열의 한 구간이 들어가있게 됩니다. 그 구간의 끝점은 항상 i-1이 됩니다. 시작이 어디인지를 변수 start에 저장하면 됩니다. x좌표에는 -100,000을 넣는 이유는 같은 y좌표를 가지는 점이 여러 개일 때, 가능한 x좌표의 값 중 가장 작은 값(-10,000)보다 작기 때문입니다. (upper_bound도 마찬가지 입니다.) import .. 2021. 2. 26.
반응형

티스토리툴바