전체 글

알고리즘 선택 전에 가장 먼저 던질 질문 3가지그래프 문제인가?정점, 간선, 연결, 이동, 경로가 등장하는가최소 / 최대 / 최적화 문제인가?최소 비용, 최단 거리, 최대 값 같은 표현이 있는가구간 쿼리 + 값 변경이 있는가?→ 범위 + 빠른 응답 + 업데이트가 필요한가DFS / BFSKey Words연결되어 있는도달 가능한사이클이 있는지모든 정점을 방문그래프, 트리DFS (Depth First Search)한 경로를 끝까지 파고들었다가 되돌아오면서 처리해야 할 때즉, 탐색 그 자체가 목적일 때void dfs(int v) { visited[v] = true; for (int next : graph[v]) { if (!visited[next]) { dfs(next..

백준 11505 - 구간 곱 구하기https://www.acmicpc.net/problem/11505문제입력첫째 줄: 수의 개수 N (1 , 수의 변경이 일어나는 횟수 M (1 둘째 줄 ~ N + 1번째 줄: N개의 수N + 2번째 줄 ~ N + M + K + 1번째 줄: 세 개의 정수 a, b, ca가 1인 경우 b번째 수를 c로 바꾸고 a가 2인 경우에는 b번째 수부터 c번째 수까지의 곱 구하여 출력출력: 첫째 줄부터 K줄에 걸쳐 구한 구간의 곱 % 1,000,000,0007풀이트리 생성: `arr` 배열 기반으로 세그먼트 트리 한 번 만들어두는 함수`arr = new long[N + 1]`: 실제 배열 값`tree = new long[4 * N]`: 세그먼트 트리 -> 구간 곱 저장static vo..

백준 11066 - 파일 합치기https://www.acmicpc.net/problem/11066문제소설을 여러 장으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장소설의 모든 장을 쓰고 나서 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일 만듦이 과정에서 두 개의 파일 합쳐서 하나의 임시 파일 만들고,임시 파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로 하나의 파일로 합침두 개의 파일을 합칠 때 필요한 비용이 두 파일 크기의 합입력: T개의 테스트로 이뤄져 있고 T는 입력의 맨 첫 줄에 주어짐각 테스트 데이터는 두 개의 행으로 주어짐첫 행: 소설을 구성하는 장의 수 K (3 두 번째 행: 1장 ~ K장까지 수..

백준 11049 - 행렬 곱셈 순서https://www.acmicpc.net/problem/11049문제크기가 NxM인 행렬 A, MxK인 B를 곱할 때 필요한 곱셈의 연산 수는 총 NxMxK번행렬 N개를 곱하는데 필요한 곱셈의 연산 수는 행렬을 곱하는 순서에 따라 달라짐ex. A의 크기 5x3, B의 크기 3x2, C의 크기 2x6인 경우 행렬 곱 ABC- (AB)C_AB를 먼저 곱하고 C를 곱하는 경우: 5x3x2 + 5x2x6 = 30 + 60 = 90- A(BC)_BC를 먼저 곱하고 A를 곱하는 경우: 3x2x6 + 5x3x6 = 36 + 90 = 126입력 첫째 줄: 행렬의 개수 N (1 둘째 줄 ~ N개의 줄: 행렬의 크기 r, c (1 항상 순서대로 곱셈을 할 수 있는 크기만 입력으로 주어짐..

백준 2042 - 구간 합 구하기https://www.acmicpc.net/problem/2042문제어떤 N개의 수가 주어져 있음/ 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려고 함ex. 1, 2, 3, 4, 5 -> 3번째 수를 6으로 바꾸고 2 ~ 5까지의 합 => 17입력첫째 줄: 수의 개수 N (1 , 수의 변경이 일어나는 횟수 M (1 둘째 줄 ~ N + 1번째 줄: N개의 수N + 2번째 줄 ~ N + M + K + 1번째 줄: 세 개의 정수 a, b, ca가 1인 경우 b번째 수를 c로 바꾸고 a가 2인 경우에는 b번째 수부터 c번째 수까지의 합 구하여 출력(1 출력: 첫째 줄부터 K줄에 걸쳐 구한 구간의 합 출력 ($-2^{63}$ 풀이세그먼트 트리(Segment..

백준 1700 - 멀티탭 스케줄링https://www.acmicpc.net/problem/1700문제ex. 3구 멀티탭 사용 순서키보드 -> 헤어드라이기 -> 핸드폰 충전기 -> 디지털 카메라 충전기 -> 키보드 -> 헤어드라이기=> 키보드, 헤어드라이기, 핸드폰 충전기의 플러그를 순서대로 멀티탭에 꽂은 다음 디지털 카메라 충전기 플러그를 꽂기 전 핸드폰 충전기 플러그를 빼는 것이 최적 -> 1번만 빼면 됨입력첫 줄: 멀티탭 구멍의 개수 N (1 두 번째 줄: 전기용품의 이름 출력: 하나씩 플러그를 빼는 최소의 횟수풀이가장 나중에 다시 사용되거나 아예 안 쓰이는 것 제거`Set set = new HashSet`: 현재 멀티탭에 꽂혀 있는 전기용품들`cnt`: 플러그를 뽑은 횟수 (정답) `int cur ..