꾸물꾸물 졔의 개발공부

https://www.acmicpc.net/problem/1522 1522번: 문자열 교환 a와 b로만 이루어진 문자열이 주어질 때, a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오. 이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 www.acmicpc.net [풀이] 주어진 문자열 내의 a 갯수가 a_cnt 개 일 때, 입력받은 문자열중 a_cnt 개의 문자들을 연속으로 탐색했을 때 모두 a여야 한다. 단, 원형으로 이루어져 있기 때문에 마지막 문자가 시작점일때까지 모두! 탐색 💡예제 입력 aabbaaabaaba : a의 갯수 8개 > 0번 인덱스 부터 a의 갯수만큼 탐색하면서, 해당 탐색문자열에 포함된 b의 갯수가 교환해야 하는 갯수 aabbaaabaa..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net dp 복습시간.. dp 왜어려워.. [풀이] 현재 탐색중인 값 기준으로 더 작은 값들 중 가장 큰 dp값 +1 예를 들어 탐색하는 값이 30이라면, 앞의 수 중 30보다 작은 수들의 dp값 중 max+1 최종적으로 0~n-1의 dp 값 중 가장 큰 값 출력 [소스코드] import java.util.*; import j..

https://www.acmicpc.net/problem/20437 20437번: 문자열 게임 2 첫 번째 문자열에서 3번에서 구한 문자열은 aqua, 4번에서 구한 문자열은 raquator이다. 두 번째 문자열에서는 어떤 문자가 5개 포함된 문자열을 찾을 수 없으므로 -1을 출력한다. www.acmicpc.net 3번 조건의 '어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이'가 되기 위해선 K개의 어떤 문자가 양 끝에 있어야 한다. 즉, 3번과 4번은 "어떤 문자를 정확히 K개 포함하고, 양 끝이 해당 문자로 같은" 최소길이와 최대길이를 구하는 것이다. 문자열에 각 문자 갯수를 카운트 한다. 만약 탐색하는 문자의 갯수가 K개 이하인 문자라면 탐색할 필요 X 그렇지 않다면, 탐색하는 문..

https://www.acmicpc.net/problem/18428 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 완전 탐색 DFS 로 조합 구현 배열에 3개의 장애물을 배치할 수 있는 모든 경우의 수에 대해 탐색 이후, 선생님(들)의 위치에서 한쪽 방향으로 쭉 이동하며 학생을 만나는지 여부 확인 자세한 구현은 아래 코드로 확인 import java.util.*; import java.io.*; public class Main { static int N; static char[][] map ; sta..

https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 0번부터 시작하여 깊이 우선 탐색 DFS 탐색 과정에서 사이클이 만들어지는지 확인 사이클이 만들어진다면, 사이클에 포함된 숫자 List에 add list 정렬 후, 출력 각 인덱스에 대응된 숫자는 하나이기 때문에 사이클이 겹칠 일은 없다. 아래 코드로 확인 import java.util.*; import java.io.*; public class Main { static List li..

https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net [풀이] 구현 (시뮬레이션) 문제 각 칸의 robot 갯수와 내구도를 1차원 정수 배열에 저장 아래 조건들만 잘 참고해서 그대로 구현하면 된다.! 1. 내리는 위치 [N-1] 인덱스에는 로봇이 무조건 0개이다. (언제든지 "내리는"위치에 도달하면 그 즉시 내리므로) 2. 내리는 위치 이후([N] ~ [2*N-1] 인덱스) 부터는 로봇이 무조건 0개이다. (위와 동일한 이유) ..

https://www.acmicpc.net/problem/16918 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net [풀이] 구현 (시뮬레이션) 문제이다. 문자형으로 주어진 입력을 정수로 변환하여서 풀었다. 0 = 빈칸, 1~3 = 폭탄의 남은 시간 즉, 처음 폭탄이 생길 때 배열의 값을 3으로 초기화 해준 후, 시간이 지날 때마다 -1 폭탄의 값이 0이 되면 폭발 (+인접한 폭탄) 🌟주의해야 할 부분 폭탄을 터트리는 과정에서 "폭탄을 터트리고 빈칸이 될 칸"을 0으로 지정할 경우, 3초가 지나서 폭탄이 터져야 할 칸과 방금 폭..

https://www.acmicpc.net/problem/12919 12919번: A와 B 2 수빈이는 A와 B로만 이루어진 영어 단어 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈 www.acmicpc.net [12904 A와 B] 아주x10000 약간 업그레이드 문제 🫠 [풀이] A와 B (12904) 문제와 거의 비슷하다. 마찬가지로 S → T (x) , T → S 일때 가능한 경우의 수가 더 적다. S에서 할 수 있는 방법은 A를 추가하거나, B를 추가하고 뒤집거나 두개 다 가능하다. 반대로 T에서 가능한 방법은, 각 조건에 따라 하나만 가능하거나 아예 안..