본문 바로가기

알고리즘 풀이/백준43

[BOJ] 1941. 소문난 칠공주 - JAVA 🔗 문제 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 💻 풀이 및 코드 문제 유형 : 조합, 벡트랙킹, BFS YYYYY SYSYS YYYYY YSYYS YYYYY 총 25명 중 가로세로가 인접한 7명을 구하는데, 그 중 솜파(S)가 4명 이상으로 구성된 조합의 갯수 풀이 그래프로 표시된 Y 와 S 에 차례대로 0~24 번이 번호를 부여한다. 총 25명 중 7명을 뽑는 조합을 구한다. 7명이 넘어가거나, 솜파가 4명이 이하라면 return 한다.. 2023. 2. 24.
[BOJ] 1914. 하노이 탑 - JAVA 🔗 문제 https://www.acmicpc.net/problem/1914 1914번: 하노이 탑 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 💻 풀이 및 코드 문제 유형 : 재귀, 임의 정밀도 / 큰 수 연산 풀이 N>20 일 때 옮긴 횟수를 출력할 때 주의해야 한다. N 의 최댓값은 100 이므로, 2^100 - 1 = 1267650600228229401496703205375 은 long 범위도 초과한다. 따라서 자바의 BigInteger 를 사용한다. BigInteger 의 pow 라는 지수 메소드를 사용해 2^N 을 구하고.. 2023. 2. 23.
[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.

티스토리툴바