백준10 [Swift] 백준 16139 : 인간-컴퓨터 상호작용 https://www.acmicpc.net/problem/16139 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net 풀이 과정 누저합 원리만 알고 있다면 크게 어려움이 없는 문제이다. 단, 1) 질문의 수가 최대 200,000번이기 때문에 매번 반복되지 않도록 한번 누적합을 구한 알파벳의 누적합은 저장해놓고 사용하도록 하고 2) 물어보지 않을 특정 문자가 있을 수 있기 때문에 특정 문자가 등장하는지에 대한 누적합을 처음 물어볼 때에만 누적합을 구하도록 한다. 먼.. 2023. 12. 18. [Swift] 백준 3020 : 개똥벌레 https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 풀이 방식 나는 처음에는 1...n 구간마다 장애물로 막혀 있는 곳의 위치들을 높이별로 빈도수 배열을 구한 뒤 배열 전체를 검색하면서 최솟값과 그 개수를 구하는 방식으로 구현했었다. // 완전 탐색으로 구현할 경우 O(n^2) 복잡도 for i in 0.. 2023. 12. 14. [Swift] 백준 10986 : 나머지 합 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 단순히 누적합 알고리즘으로 접근할 경우에 아래와 같이 시작점과 끝점의 모든 경우의 수를 확인해야 하므로 시간 복잡도가 O(n^2) for i in 0...n-1 { for j in i+1...n { count += ( psum[j]-psum[i] ) % 1 == 0 ? 1 : 0 { { 하지만 여기서 누적합 psum[0]...psum[n] 중 나머지.. 2023. 12. 13. [Swift] 백준 2559 : 수열 # 풀이 전형적인 누적합 문제. 아래와 같이 psum[0] = 0 부터 시작하는 prefix sum을 먼저 구한 뒤 var psum = [Int](repeating: 0, count: n + 1) for i in 1...n { psum[i] = psum[i-1] + inputArr[i-1] } psum[m] - psum[0] 부터 psum[n] - psum[n-m] 중 가장 작은 값을 찾는다. var max = Int.min; for i in m...n { if( max < psum[i] - psum[i-m] ) { max = psum[i] - psum[i-m] } } 소스코드 import Foundation let input = readLine()!.split(separator: " ").map{Int.. 2023. 12. 7. No7662 이중 우선순위 큐 https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 두개의 PriorityQueue를 활용해서 하나는 최대값을 앞에 하나는 최소값을 앞에 두는 queue를 활용하면 될 것 같았다. 그래서 입력 값을 받으면 두 queue에 넣고 최대값을 빼라는 명령이 있으면 최대값queue는 poll을 최소값queue는 remove 메소드를 쓰면 될 것 같았다. 코드는 아래와 같다. package com.yuk; import java.io.BufferedRead.. 2022. 11. 23. No7576 토마토 (너비 우선 탐색) 너비 우선 탐색을 이용한 문제풀이다. 전에 사용해봤던 방식은 토마토 박스의 모든 공간를 좌표를 key, 토마토 객체를, value 값으로 하여 HashMap에 넣었다. 하루가 지날 때마다 박스의 모든 공간을 검색하여 그날 익어야 할 토마토를 찾아놓은 후 익게 하는 방식으로 풀어보았다. 하지만 매일마다 모든 토마토를 검색해야 하기에 시간 초과를 피할 수 없었다. https://6cessfuldev.tistory.com/17 No7576 토마토 (HashMap의 Custom key 만들어 풀어보기) 너비우선탐색 문제이다. 그런데 문제는 지금까지 풀었던 너비우선탐색 문제에서 탐색을 시작해야 하는 시작점이 하나였다면 이 문제는 시작점이 여러 개 일 수 있다는 문제이다. 문제를 읽고 6cessfuldev.tist.. 2022. 11. 21. No1260 DFS와 BFS(그래프 이론: 너비우선탐색, 깊이우선탐색) 백준 7576 번(토마토)를 풀기 전에 먼저 전에 풀었던 깊이 우선 탐색(Depth First Search)과 너비 우선 탐색(Breadth First Search) 기본 문제인 이 문제의 문제풀이를 기록하면서 두 가지 알고리즘을 정리해보고자 한다. 1. 깊이 우선 탐색(DFS) 간선들로 연결된 점들을 이차원 배열(int[][])로 표현한 후 i와 j 사이를 연결하는 간선이 있을 경우 arr[i][j], arr[j][i]의 값을 1로, 없을 경우 0으로 표현한다. 이후 탐색할 때 i와 연결된 점들을 찾을 때 arr[i]의 값들을 검색하면 된다. 한번 검색한 곳을 다시 지나치지 않기 위해 visit(boolean[]) 배열 하나를 만들어 i번째 점을 검색한 후 visit[i]는 true값으로 변경한다. 검.. 2022. 11. 18. No2630 색종이 만들기 (분할 정복) 종이를 4분할 하여 1분면, 2분면, 3분면, 4분면 각각의 결과에 따라 멈추거나 다시 4분할하여 재귀 함수를 실행하는 알고리즘이다. 구현하는 방식은 어렵지 않다. package com.yuk; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class No2630 { static int n; static int[][] arr; static int one; static int zero; static void dq(int x, int y, int num) { boolean flag = true; int first = arr[x][y]; loop : for (int i = x; .. 2022. 11. 15. No1931 회의실 배정 (그리디 알고리즘) 본 문제는 그리디 알고리즘을 사용하여 매 선택마다 최적의 답을 구하는 문제이다. 아래 블로그의 글을 참고하였다. https://hongjw1938.tistory.com/172 알고리즘 - 그리디 알고리즘(Greedy Algorithm) 1. 그리디 알고리즘(Greedy Algorithm)이란? 간단히 설명해, 그리디 알고리즘은 "매 선택에서 현재 당장 최적인 답"을 선택해 전체 적합한 결과를 도출하자는 알고리즘 기법이다. 즉, 백트래킹을 통해 hongjw1938.tistory.com 시작 시간과 종료 시간을 가지고 있는 여러 회의들을 시간이 겹치기 않고 가장 많이 담을 때 총 개수를 구하는 문제이다. 핵심은 1. 다음 단계의 회의를 선택할 때 .조건은 전 회의 종료 시간보다 다음 단계의 회의 시작 시간이.. 2022. 11. 8. 이전 1 2 다음
