Algorithm/백준풀이40 [알고리즘 문제풀이] 백준 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. [알고리즘 문제풀이] 백준 16172 나는친구가적다(Large) / JAVA코드 https://www.acmicpc.net/problem/16172 16172번: 나는 친구가 적다 (Large) 첫 번째 줄에는 알파벳 소문자, 대문자, 숫자로 이루어진 문자열 S가 주어진다. (1 ≤ |S| ≤ 200,000) 두 번째 줄에는 성민이가 찾고자 하는 알파벳 소문자, 대문자로만 이루어진 키워드 문자열 K가 www.acmicpc.net 참조 개념 2022.01.12 - [Algorithm/개념] - [알고리즘 개념] KMP - 문자열 검색 알고리즘(JAVA 코드) /** * * KMP 사용 풀이 * * 1. 정규식으로 숫자 제거(replaceAll 시간복잡도 O(N)) * * 2. KMP 실행 O(N+M) * * 총 시간복잡도 O(N+M) */ import java.util.*; impor.. 2022. 1. 17. [알고리즘 문제풀이] 백준 2098 외판원순회 (JAVA코드) https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 실패해서 타 블로그들을 참조해서 풀은 문제 /** * * 실패 ㅠ * * 본인에서 시작해서 본인으로 돌아오는 가장 적은 비용을 쓴 경로 * * 외판원 순회 알고리즘 사용.. * * DP + dfs + 비트마스킹 * * DP[현재도시][방문했던도시정보(bit)] = 이후에 방문하는것들 포함한 최소비용 * * 어느 도시에서 출발했던지 최소비용 사이클을 찾는거기때문.. 2022. 1. 16. 이전 1 2 3 4 5 다음