[Java] 백준 2228. 구간 나누기

📌 문제 링크 - https://www.acmicpc.net/problem/2228        문제N(1 ≤ N ≤ 100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1 ≤ M ≤ ⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되어야 한다.각 구간은 한 개 이상의 연속된 수들로 이루어진다.서로 다른 두 구간끼리 겹쳐있거나 인접해 있어서는 안 된다.정확히 M개의 구간이 있어야 한다. M개 미만이어서는 안 된다.N개의 수들이 주어졌을 때, 답을 구하는 프로그램을 작성하시오.   입력첫째 줄에 두 정수 N, M이 주어진다. 다음 N개의 줄에는 배열을 이루는 수들이 차례로 주어진다. 배열을 이루는 수들은 -32768 이상 ..

• format_list_bulleted Algorithm/백준
• · 2025. 1. 21.
• textsms

[Java] 백준 17259. 선물이 넘쳐흘러

📌 문제 링크 - https://www.acmicpc.net/problem/17259      문제파티가 끝난 다음 날, 욱제는 파티에 왔던 팬들이 놓고 간 5조5억 개의 선물을 발견했다! 이에 감동한 욱제는 자신도 팬들에게 선물을 주기로 했다. 욱제는 귀찮아서 받은 선물을 포장만 바꿔서 주기로 했다. 욱제는 귀찮아서 선물을 조금 팔고 그 돈으로 선물 포장 공장을 차려 버렸다.B×B 크기의 격자 모양 공장에는 안쪽 가장자리를 따라 위치한 ⊐ 모양의 컨베이어 벨트가 있다. 벨트의 시작 지점은 공장의 맨 위 가장 왼쪽 지점이고, 벨트의 끝 지점은 공장의 맨 아래 가장 왼쪽 지점이다. 벨트는 1초 간격으로 시작 지점에서 ⊐ 모양을 따라 끝 지점을 향해 한 칸씩 움직인다. 모든 선물은 이 벨트를 통해 운반되고..

• format_list_bulleted Algorithm/백준
• · 2025. 1. 17.
• textsms

페이지 교체 알고리즘

서론앞서 가상 메모리 포스팅을 하면서 프로세스를 이루는 모든 페이지가 메모리에 적재되지 않아도 된다는 것과, 이처럼 메모리에 필요한 페이지만을 적재하는 기법이 요구 페이징이라고 하는 것을 알아보았다. 요구 페이징을 통해 페이지들을 메모리에 점차 적재하다 보면 언젠가는 메모리가 가득 찰 것이다. 메모리에 페이지가 가득 찬 상태에서 추가적으로 페이지를 적재해야 한다면 메모리에 적재된 일부 페이지를 스왑 아웃해야 한다. 이때 메모리에 적재된 페이지 중 보조기억장치로 내보낼 페이지를 선택하는 방법을 페이지 교체 알고리즘이라고 한다. 페이지 교체 알고리즘은 컴퓨터 전체 성능과 직결된다. 어떤 알고리즘이 사용되느냐에 따라 페이지 폴트의 발생 빈도가 달라질 수 있기 때문이다. 어떤 것이 좋은 페이지 교체 알고리즘일..

• format_list_bulleted Development/운영체제
• · 2025. 1. 16.
• textsms

가상메모리

서론가상 메모리란 실행하고자 하는 프로그램의 일부만 메모리에 적재해, 실제 메모리보다 더 큰 프로세스를 실행할 수 있도록 만드는 메모리 관리 기법이다. 그렇다면 이러한 메모리 관리 기법이 왜 필요할까? 새로운 프로세스는 새롭게 메모리에 적재되고, 사용되지 않는 프로세스는 메모리에서 삭제된다. 즉, 메모리 정보는 자주 변경될 수 있다는 의미다. 그렇기 때문에 메모리에 적재된 모든 프로세스와 CPU가 이렇게 실시간으로 바뀌는 정보를 모두 기억하고 있기는 어렵다. 그렇다면 CPU는 어떻게 메모리에 적재된 프로세스의 주소를 인식하고 관리할까? 지금부터 알아보도록 하자. 물리 주소와 논리 주소CPU와 프로세스는 메모리의 하드웨어 상 실제 주소인 물리 주소가 아니라 논리 주소를 이용한다. 논리 주소는 프로세스마..

• format_list_bulleted Development/운영체제
• · 2025. 1. 12.
• textsms

[Java] 백준 2314. 이세계 게임

📌 문제 링크 - https://www.acmicpc.net/problem/2314        문제트럭 운전사 택희는 오랜 기간 동안의 공로를 인정받아 이세계로 소환되었다. 택희가 소환된 이세계에는 천사 종족 Portableangel과 악마 종족 Legnaelbatrop이 살고 있었다. 택희는 뛰어난 알고리즘 지식을 발휘해 얼마 지나지 않아 두 종족을 모두 지배하는 이세계의 왕이 되었다.폭군 택희는 지루해지면 이세계의 주민들을 이용해 게임을 한다. 먼저 종족과 무관하게 16명의 개체를 모아서 4×4 격자 형태로 세워 놓는다. 그 다음 각 자리에 어떤 종족이 서야 하는지를 지정해 주고, 그에 맞게 다시 서도록 명령한다. 그러면 이들은 서로 자리를 바꿔서 택희가 원하는 배치를 만들어야 한다. 자리를 바꿀..

• format_list_bulleted Algorithm/백준
• · 2025. 1. 9.
• textsms

왜 데이터베이스 인덱스로 B tree 계열을 사용할까?

데이터베이스 인덱스 테이블을 구현할 때 트리 구조의 B+Tree와 B-tree 인덱스 방식을 많이 사용한다. B tree의 시간 복잡도는 O(log N)으로, B tree 인덱스를 사용하면 데이터의 삽입, 갱신, 삭제 등에 드는 작업 비용을 줄일 수 있기 때문이다. 그런데 균형 이진 탐색 트리인 AVL Tree와 Red-Black Tree도 시간 복잡도 O(log N)으로, B Tree와 시간 복잡도가 동일하다.  B 트리의 시간 복잡도 O(log N) 균형 이진 탐색 트리 시간 복잡도 O(log N) 둘 다 O(log N)인데 왜 균형 이진 탐색 트리가 아닌 B 트리 계열을 인덱스로 사용하는 걸까?    잠시 컴퓨터 구조를 살펴보도록 하자. CPU(Central Processing Unit, 중앙 처리..

• format_list_bulleted Development/데이터베이스
• · 2025. 1. 7.
• textsms