Algorithm94 [알고리즘 문제풀이] 백준 6549 히스토그램에서 가장 큰 직사각형 / JAVA https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net /** * 1. 분할정복과 세그먼트 트리 * * 폭은 1로 직사각형이 고정되어있으므로, * * 세그먼트트리로 구간 내 최소 높이의 직사각형 찾기 * * 최소 높이를 찾았을때 구간 폭 을 곱해서 넓이를 구하기 * * 그다음 최소 높이를 제외한 왼쪽 오른쪽 구간으로 나누어 계산 * * (고른 최소높이로는 현재 구간이 제일 크기때문) * * 세그.. 2022. 1. 21. [알고리즘 문제풀이] 백준 2357 최솟값과 최댓값 / JAVA https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 사용개념 : 2022.01.17 - [Algorithm/개념] - [알고리즘 개념] 세그먼트 트리(Segment Tree) / Java import java.io.IOException; /** * 여러개의 특정 구간 내 최솟값과 최댓값 구하기 * * 세그먼트 풀이 */ import java.util.*; import java.io.*; public class .. 2022. 1. 21. [알고리즘 문제풀이] 백준 17219 비밀번호찾기 /JAVA코드 https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net /** * 구현 * * 1. 해시맵에 주소: 비밀번호 매칭하여 저장 * * 2. 해시맵에서 찾아서 출력 * */ import java.util.*; import java.io.*; public class BJ17219_비밀번호찾기 { public static void main(String[] args) throws IOException{ BufferedReader b.. 2022. 1. 19. [알고리즘 문제풀이] 백준 16928 뱀과사다리게임 / JAVA코드 https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net /** * 구현 * * 1. 사다리 정보와 뱀의 정보를 배열에 담기 * * 2. 1~100칸의 정보를 만들고 각 칸에 몇번만에 왔는지를 저장하면서 이동(방문했던 칸은 방문하지 않음) * * 3. 최종 100번째칸에 왔을때 몇번만에 왔는지 출력 * */ import java.util.*; import java.io.*; public class BJ169.. 2022. 1. 19. [알고리즘 문제풀이] 백준 11047 동전0 /JAVA코드 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net /** * 구현 * * 1. 동전 큰 것부터 확인 * * 2. k원보다 작거나 같으면 동전으로 나누어 몇개까지 사용가능한지 확인 * * 3. 몫이 사용개수 이므로 몫만큼 정답 증가 * * 4. 나머지를 기준으로 하위 동전 체크 * * 5. k == 0으로 전환 시 정답 출력 * */ import java.util.*; import j.. 2022. 1. 19. [알고리즘 문제풀이] 백준 9375 패션왕 신해빈 / JAVA코드 https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net /** * 구현 브루트포스 문제 * * 해시에 의상종류별 개수 저장 * * 각 의상 종류별 개수+1 을 곱한다음 다 안고른 상태를 빼면 답 * * 예) headgear = 2, eyewear = 1 * 3*2 = 6 -1 = 5 * */ import java.util.*; import java.io.*; .. 2022. 1. 19. [알고리즘 문제풀이] 백준 7569 토마토 / JAVA코드 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net BFS 풀이 /** * 3차원 bfs로 실행 * */ import java.util.*; import java.io.*; public class BJ7569_토마토 { public static int[][][] box; public static int n,m,h,day; public static Queue q = new LinkedList(); public static vo.. 2022. 1. 19. [알고리즘 개념] 펜윅 트리(Fenwick Tree,Binary Indexed Tree) / JAVA 펜윅트리는 세그먼트 트리를 변형한 버전이므로, 세그먼트 트리를 먼저 알아야 이해가 잘 됩니다! 2022.01.17 - [Algorithm/개념] - [알고리즘 개념] 세그먼트 트리(Segment Tree) / Java 그리고 비트 단위로 연산하기 때문에, 비트 연산자를 알아야합니다! 2022.01.14 - [Algorithm/개념] - [알고리즘 개념] 비트마스크(Bitmask) 펜윅트리란(Fenwick Tree, Binary Indexed Tree, BIT) 세그먼트 트리에서 메모리를 절약한 트리. 시간복잡도 O(MlogN) 데이터 변경: O(logN) 연산: O(logN) 공간복잡도 O(N) 펜윅트리는 세그먼트 트리에서 우측 노드를 지운 트리입니다. 만약 5~7까지의 합을 알고 싶다면, 1~7까지의 .. 2022. 1. 17. 이전 1 ··· 7 8 9 10 11 12 다음
