꾸물꾸물 졔의 개발공부

https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 🌟내가 실수한 부분 - 문자열 배열을 Arrays.sort로 정렬하게 되면, 숫자/알파벳 순으로 정렬된다. - 문자열 길이에 따라 정렬된다고 생각했다... 하핫 . [풀이] str1.startsWith(str2) : 문자열 str1이 문자열 str2로 시작한다면 true 반환 모든 문자열을 비교하기에는 O(N^2)로 시간초과가 난다. ▶ 정렬 주어진 문자열을 오름차순으로 정..

https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net [풀이] S → T 찾기(X) , T → S 찾기(O) 주어진 문자열 S에서 할 수 있는 방법은 A를 추가하거나, B를 추가하거나 (+뒤집기) 두개 다 가능하다. 반대로 T에서 가능한 방법은 , 아래와 같이 가장 끝 문자가 무엇이냐에 따라 하나만 가능하다. 1. 가장 끝 단어가 'A' 일경우 : A 빼기 2. 가장 끝 단어가 'B' 일 경우: B 빼고 뒤집기 ..

https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net [풀이] 조합 + BFS + 구현(시뮬레이션) 1. 두개의 선거구 각각에 포함될 구역을 정한다. - 조합 2. 각각의 선거구에 포함된 구역들이 서로 연결되어 있는지 확인한다. - BFS 3. 연결되어 있다면 인구수 차이, 그렇지 않다면 적당히 큰 값을 리턴한다. [구현 과정] int num[] : 각 구역의 인구 수 List graph : 각 구역의 연결정보 저장 boolean select[] : 조합을 구현하는 과정..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net [풀이] DFS 탐색 인접리스트에 각 노드의 자식 노드(들) 저장, 1차원 정수배열에 각 노드의 부모 노드를 저장한다. 지워질 노드(erase)가 주어지면, 1. erase의 자식 노드를 모두 삭제한다. (erase 리스트를 비운다.) 2. erase의 부모 노드 리스트에서 erase를 삭제한다. 만약 지운 노드가 루트노드라면 0 출력 후 종료. 그렇지 않다면 루트노드에서 시작하여 DFS 탐..

https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net [풀이] DP를 사용해서 접근 dp[i] : i원을 만드는데 필요한 최소 동전의 갯수 n가지 종류의 동전 coin[j] 가 주어졌을 때, coin[] 금액만큼 제외한 dp 값 +1 중 최솟값을 찾는다. 점화식 : dp[i] = min(dp[i], dp[i-coin[j]] +1) 단, 최솟값을 찾기 위해서 dp 초기값을 큰 정수값으로 초기화 시켜줘야하는데 Intege..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net [풀이] 시간초과에 주의해야 한다. 구간합 배열을 따로 구해서 이중 포문을 돌렸더니 시간초과 투 포인터로 접근 연속된 수 하나여도 가능하므로 left 와 right를 같은 값에서 시작한다. 만약 더한 값이 S 보다 작다면 right를 오른쪽으로 옮겨가며 값을 더한다. S보다 크거나 같다면, left에서 하나씩 빼면서 S 최소 길이를 구한다. [구현 과정] arr[]: 입력받은 N개의..

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net [풀이] 구현(시뮬레이션) + DFS 치즈를 녹이는 외부공기와 내부공기를 먼저 구분해야한다. DFS 를 통해 외부공기를 찾아 값을 2로 바꾸어주었다. - 문제에 보면, "모눈종이의 맨 가장자리는 치즈가 놓이지 않는 것으로 가정한다"고 명시되어있다. - 즉, 가장자리의 모든 칸은 무조건 빈칸이자 외부공기이고, 외부공기끼리는 무조건 연결되어있다. - (가장자리 빼고 다 치즈이더라도, 가장..

https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net [알고리즘] 투 포인터 제일 앞/뒤 양끝에서 두개의 포인터가 중간으로 오면서 투 포인터가 가리키는 값이 동일한지 확인 만약 다른 값이 나온다면 하나씩 제외하고 회문인지 확인하여 회문/유사회문/일반 판별 [설계] 양 끝을 가리키는 포인터로 시작 (left /right) 만약 left, right 가 가리키는 값이 같을 경우 left와 right를 가운데쪽으로 이동 left, right가 가리키는 값이 다를 경우 1. left가 ..