본문 바로가기

Computer Science27

[Algorithm/Kotlin] 백준 30804번 과일 탕후루: 투 포인터(슬라이딩 윈도우)로 최적화 문제 설명은하는 긴 막대에 N개의 과일이 꽂혀있는 과일 탕후루를 만들었습니다.과일의 종류는 1부터 9까지 있으며, 막대에는 앞쪽부터 차례대로 S1,S2,...,SN번 과일이 꽂혀 있습니다.그러나 주문을 다시 확인해 보니 과일을 두 종류 이하로 사용해야 한다는 요청이 있었습니다.새로 만들 시간이 없는 은하는 앞쪽에서 a개, 뒤쪽에서 b개의 과일을 빼서 두 종류 이하의 과일만 남기기로 했습니다.즉, 막대의 연속된 구간 중에서 과일 종류가 2개 이하인 가장 긴 부분을 찾아야 합니다.이때, 남아 있는 과일 개수가 가장 많은 경우를 구하는 것이 목표입니다.입력첫 줄에 과일의 개수 N이 주어집니다. (1≤N≤200,000)둘째 줄에 탕후루에 꽂힌 과일을 나타내는 NNN개의 정수 S1,S2,...,SN​이 공백으로 .. 2025. 3. 17.
[Operating System & Concurrency] 프로세서, 프로세스, 스레드, 코루틴의 개념과 관계 정리 운영체제를 공부하면서 여러 번 관계성을 정리하려 했지만, 학습할 때마다 다시 헷갈리는 반복이 이어졌습니다. 흐름을 제대로 정리하고자 여러 유튜브 강의를 찾아보던 중, 유튜버 얄팍한 코딩사전님의 "프로세스는 뭐고 스레드는 뭔가요?" 영상을 보고 개념을 정리하는 데 많은 도움을 받았습니다. 이 글은 해당 영상에서 설명된 내용을 바탕으로 나중에 다시 참고하기 위해 정리한 글입니다.또한, 프로세서, 프로세스, 스레드의 관계를 이해한 후, 처음에는 스레드와 비슷하게 보였던 코루틴의 개념까지 정리하고 싶어 관련 블로그 글을 찾아 읽었습니다. 이 과정에서 발견한 글을 통해 스레드와 코루틴의 차이를 이해하는 데 큰 도움이 되었으며, 이를 바탕으로 최종적으로 본 글을 정리하게 되었습니다.혹시라도 이 글을 보게 된 분이라.. 2025. 3. 6.
[Algorithm/Kotlin] 백준 2630번 색종이 만들기: 분할정복을 활용한 풀이법 1. 문제 설명주어진 N × N 크기의 색종이가 하얀색(0)과 파란색(1) 으로 칠해져 있을 때,이를 모두 같은 색이 될 때까지 잘라 각 색상의 개수를 구하는 문제입니다.문제 조건N은 2^k (k = 1~7) 형태로 주어집니다. (즉, 2, 4, 8, 16, 32, 64, 128 중 하나)색종이가 한 가지 색으로만 칠해져 있다면, 더 이상 자르지 않고 해당 색종이 개수를 증가시킵니다.혼합된 색상이 있다면, 정사각형을 4등분하여 동일한 방식으로 재귀적으로 처리합니다.예제 입력81 1 0 0 0 0 1 11 1 0 0 0 0 1 10 0 0 0 1 1 0 00 0 0 0 1 1 0 01 0 0 0 1 1 1 10 1 0 0 1 1 1 10 0 1 1 1 1 1 10 0 1 1 1 1 1 1예제 출력97 즉,.. 2025. 3. 4.
[Algorithm/Kotlin] 백준 1260번 DFS와 BFS: 탐색 알고리즘 구현 및 원리 1. 문제 설명주어진 그래프에서 DFS와 BFS 탐색을 수행한 결과를 출력하는 문제입니다.방문할 수 있는 정점이 여러 개인 경우, 번호가 작은 정점부터 우선 방문해야 합니다.입력첫 번째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점 V가 주어집니다.이후 M개의 줄에는 양방향 간선이 연결하는 두 정점의 번호가 주어집니다.출력첫 번째 줄: DFS 탐색 결과두 번째 줄: BFS 탐색 결과정점 방문 순서대로 출력합니다.2. 문제 해결 아이디어DFS (Depth-First Search, 깊이 우선 탐색)스택(Stack) 또는 재귀(Recursion)를 이용해 탐색을 수행합니다.현재 정점에서 가능한 한 깊이 들어가며 방문한 후, 더 이상 갈 곳이.. 2025. 2. 27.
[DataStructure/Graph] 완전 탐색 문제를 해결하는 두 가지 방법: 인접 행렬 vs 인접 리스트 완전 탐색 문제를 풀면서 완전 탐색을 구현하는 방식에는 두 가지 방법(인접 행렬과 인접 리스트)이 있다는 것을 알게 되었습니다.각 방식이 어떤 경우에 유리하게 활용되는지 문제를 통해 정리해 두면 좋을 것 같아 이번 글을 작성하게 되었습니다.이번 글에서는 완전 탐색을 인접 행렬과 인접 리스트를 사용하여 해결할 때의 차이점과 각각의 장단점을 두 가지 문제를 예제로 설명하겠습니다.1. 인접 행렬을 사용하는 경우1.1 인접 행렬(Adjacency Matrix) 개념배열(Array) 기반이며, BooleanArray를 사용하여 간선 유무를 표현합니다.graph[i][j] = true이면 i번 노드와 j번 노드가 연결된 것입니다.graph[i][j] = false이면 연결되지 않은 상태입니다.공간 복잡도: O(N^.. 2025. 2. 27.
[Operating System] 프로세서, 코어, 프로세스, 스레드를 쉽게 이해하기: 공장 비유로 살펴보기 처음에는 프로세스와 스레드의 관계를 이해한 것 같았지만, 프로세서 개념까지 생각하니 혼란이 생기기 시작했습니다. 이를 해결하기 위해 전체적인 개념을 비유를 통해 정리해보았습니다. 이 글은 프로세서, 코어, 프로세스, 스레드의 관계를 공장에 비유하여 쉽게 이해할 수 있도록 설명하는 데 중점을 두었습니다.프로세서, 프로세스, 스레드의 개념을 "공장"에 비유해서 설명해보겠습니다.프로세서(Processor)는 공장 전체입니다. 공장에는 여러 기계(코어)가 있어 작업을 처리합니다.코어(Core)는 공장 내의 개별 기계입니다. 실제로 제품을 만드는 일을 합니다.프로세스(Process)는 공장의 생산 라인입니다. 각 생산 라인은 독립적으로 운영됩니다.스레드(Thread)는 생산 라인에서 일하는 작업자입니다. 실제로 .. 2025. 2. 26.
[Algorithm/Kotlin] 백준 17626번 Four Squares: DP를 활용한 풀이법 문제 설명1770년, 라그랑주는 모든 자연수는 네 개 혹은 그 이하의 제곱수 합으로 표현할 수 있다는 사실을 증명했습니다. 목표:주어진 자연수 n을 최소 개수의 제곱수 합으로 표현하세요.입력:자연수 n (1 ≤ n ≤ 50,000)출력:n을 표현할 수 있는 제곱수의 최소 개수문제 해결 아이디어 1. 접근 방법처음에는 가장 큰 제곱수를 빼주면 되지 않을까? 하는 생각으로 그리디(Greedy) 접근법을 떠올렸습니다.예: n = 12인 경우가장 큰 제곱수인 9 (3²)를 선택12 - 9 = 3 → 나머지 3을 다시 제곱수 합으로 표현: 1² + 1² + 1²결과: 12 = 9 + 1 + 1 + 1 → 4개 사용하지만, 더 나은 해가 존재합니다:12 = 4 + 4 + 4 (2² + 2² + 2²) → 3개1: .. 2025. 2. 20.
[Algorithm/Kotlin] 백준 11659번 구간 합 구하기 4: 누적 합(Prefix Sum)을 활용한 풀이법 문제 설명주어진 수열에서 특정 구간 [i, j]의 합을 여러 번 구해야 하는 문제입니다. 입력으로 N개의 수와 M개의 구간이 주어집니다. 각 구간에 대해 빠르게 합을 구하는 프로그램을 작성해야 합니다. 제한 사항1 ≤ N ≤ 100,0001 ≤ M ≤ 100,0001 ≤ i ≤ j ≤ N각 숫자는 1,000 이하의 자연수문제 해결 아이디어기본 접근법 (O(N × M), 시간 초과 가능)   M개의 구간 합을 구하기 위해 for 루프를 사용해 N개의 값을 더하면 O(N × M) 시간이 걸립니다.   N, M이 최대 100,000일 경우 10^10 이상의 연산이 발생하여 비효율적입니다.누적 합(Prefix Sum) 기법 (O(N + M), 효율적)   먼저 누적 합 배열을 생성하여 O(N) 시간에 각 위치까.. 2025. 2. 19.
[DataStructure/Kotlin] Kotlin에서 Array, List, MutableList, ArrayList의 차이 정리 Kotlin에서는 Array, List, MutableList, ArrayList 등 다양한 컬렉션 타입을 사용할 수 있습니다.이들은 모두 여러 개의 값을 저장하는 자료구조이지만, 동작 방식과 활용법이 서로 다릅니다.이번 글에서는 각 자료구조의 특징과 차이점, 그리고 언제 어떤 것을 사용해야 하는지 정리하겠습니다.1. Array vs List → 수정 가능 여부 차이Array는 값 변경 가능하지만 크기 변경은 불가능val arr = arrayOf(1, 2, 3)arr[0] = 10 // 값 변경 가능println(arr.joinToString()) // 10, 2, 3// arr.add(4) // 컴파일 오류 (크기 변경 불가능)Array는 배열 크기가 고정되어 있지만, 인덱스를 통해 값 변경이 가.. 2025. 2. 13.
반응형

티스토리툴바