본문 바로가기

알고리즘 풀이56

[BOJ] 14889. 스타트와 링크 - JAVA 🔗 문제 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 💻 풀이 및 코드 문제 유형 : 브루트포스, 백트랙킹 인원을 두 그룹으로 나누어 두 그룹 간의 실력 차가 가장 적은 그룹 조합을 구하는 문제 전체 코드 import java.io.*; import java.util.*; public class Main_bj_14889_스타트와링크 { static int N, ans = Integer.MAX_VALUE; static int[][] graph; public sta.. 2023. 2. 21.
[BOJ] 16139. 인간-컴퓨터 상호작용 - JAVA 🔗 문제 https://www.acmicpc.net/problem/16139 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 💻 풀이 및 코드 문제 유형 : 누적합 풀이 모든 알파벳에 대해서 그 알파벳이 몇 번 나왔는지 저장하면 된다. 0번 idex 에서 배열의 범위를 벗어나는 것을 방지하려고 문자열의 길이 + 1 을 크기로 하는 배열을 선언했다. prefixSum[i][j] 는 i 번째 문자열까지 알파벳 j (a ~ z ) 가 몇 번 나왔는지 기록한다. 느낀 .. 2023. 2. 16.
[BOJ] 12015. 가장 긴 증가하는 부분 수열 2 🔗 문제 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 💻 풀이 및 코드 문제 유형 : 이분 탐색, LIS(가장 긴 증가하는 부분 수열) 풀이 in[ ] input : 입력으로 들어오는 수열 , List Lis : 증가하는 부분 수열 입력으로 숫자가 들어올 때 2가지 경우로 나뉜다. 1. Lis 의 맨 뒤의 숫자보다 클 때 2. Lis 의 맨 뒤의 숫자보다 작거나 같을 때 Lis 의 맨 뒤 숫자보다 현재 입력으로 들어온 숫자가 더 크다면 맨 .. 2023. 2. 16.
[BOJ] 4195. 친구 네트워크 - JAVA 🔗 문제 https://www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 💻 풀이 및 코드 문제 유형 : 자료 구조, 해시를 사용한 집합과 맵, 분리 집합 풀이 기존의 Union-Find 문제는 parent 배열만 있으면 됐지만, 이 문제는 노드가 정수형이 아닌 문자열로 주어지기 떄문에 3개의 변수가 필요하다. 기존의 부모 노드를 저장하는 int [] parent 배열 이름에 해당하는 parent 인덱스를 저장하는 Hashmap parent 에 속한.. 2023. 2. 15.
[BOJ] 16946. 벽 부수고 이동하기 4 - JAVA 🔗 문제 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 🧩 풀이 및 코드 문제 유형 : 그래프 이론, 그래프 탐색, 너비우선탐색(BFS), 깊이우선탐색(DFS) , 분리 집합 풀이 문제는 1의 위치를 0으로 변환하고 인접한 그룹의 0의 갯수의 합을 구하는 문제다. 일일이 1일 때 인접한 0의 갯수를 BFS를 이용해 구하면 시간초과가 발생한다. 분리집합을 통해 해결할 수 있다. 우선, 분리 집합 개념을 이용해 0으로 이루어.. 2023. 2. 10.
[BOJ] 16933. 벽 부수고 이동하기3 - JAVA 🔗 문제 https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 🧩 풀이 및 코드 문제 유형 : 그래프 이론, 그래프 탐색, 너비우선탐색(BFS) 풀이 참고 - https://wngml56.tistory.com/80 [BOJ] 14442. 벽 부수고 이동하기2 - JAVA 🔗 문제 https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1.. 2023. 2. 9.

티스토리툴바