차곡차곡.

N개의 인덱스를 가지는 배열 arr가 있을 때, 배열의 i~j 인덱스의 합을 구하려고 한다. 딱 한개의 구간합을 구하는 문제가 주어진다면 단순히 반복문에서 arr[i]~arr[j]까지의 합을 더해나가면 되겠지만, 주어진 배열에서 여러 구간합을 구해야한다면, 반복되는 작업을 피하기 위해 누적합을 저장하는 배열을 하나 만들어 놓는 것이 좋다. (i

https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 더보기 문제 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 번갈아가면서 등장한다. 아래 그림은 길이가 14미터이고 높이가 5미터인 동굴이다. (예제 그림) 이 개똥벌레는 장애물을 피하지 않는다. 자신이 지나갈 구간을 정한 다음 일직선으로 지나가면서 만나는 ..

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 더보기 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터..

운영체제의 여러 기능중에는 프로세스 관리가 있다. 이번 게시글에서는 프로세스란 무엇이며, 운영체제에서 어떻게 관리되는지 공부해보자. Process란 무엇인가? A process is a program in execution. : 프로세스란 실행중인 프로그램을 말한다. 컴퓨터의 저장소(HDD) 에는 많은 파일과 프로그램들이 있는데, 이를 실행시키기 위해 메모리에 load하면 프로세스로 불리는 것이다. 그리고 이 때, 프로세스는 다음 그림과 같이 메모리에 여러 영역으로 나뉘어 저장된다. o Text section : 소스코드의 명령어 o Data section : 소스코드의 전역변수 o Heap section : 동적 메모리 할당 (dynamic memory allocation) - ex. malloc, n..

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 더보기 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다..

https://www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net 더보기 문제 세계에서 GDP가 가장 높은 서강 나라는 소프트웨어와 하드웨어 기술이 모두 최고라서 IT강국이라 불리고, 2015년부터 세상에서 가장 살기 좋은 나라 1등으로 꼽히고 있다. 살기 좋은 나라 1등으로 꼽힌 이후 외국인 방문객들이 많아졌고, 그에 따라 전기 소비율이 증가하여 전기가 많이 부족한 상황이 되었다. 따라서 서강 나라의 대통령은 최근 개..

https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 더보기 문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다..

토비의 스프링 2장: 테스트 JUnit (자바 테스팅 프레임워크) 지난 게시글에서는 JUnit 단위테스트를 왜 쓰는지, 어떻게 쓰는지에 대해서 기본 개념을 알아보았다. (이전게시글 참고: 2021.07.16 - [책책책/토비의 스프링 3.1] - [Spring] 자바 테스팅 프레임워크 JUnit (개념편)) 어플리케이션 코드 뿐만이 아니라 테스트 코드도 리팩토링이 필요한데, JUnit의 기능들을 사용하며 이전 게시글에서 작성했던 코드를 개선해보자. 1) 반복적인 코드를 제거 : @Before / @After 어노테이션을 메소드에 써주면 각각의 @Test 메소드의 테스트 전 / 후에 공통기능들을 자동으로 호출하여 수행한다. 단, 자동으로 호출되기 때문에, 서로 주고 받을 정보들은 인스턴스 변수를 이용해야 ..

먼저, 신장트리(Spanning Tree)란 방향성이 없는 N개 정점의 가중치 그래프에서 모든 정점을 연결하는 N-1개의 간선으로 구성된 트리를 말한다. 즉, 최소신장트리(MST: Minimum Spanning Tree)는 모든 정점을 연결하는 간선들의 가중치 합이 최소가 되는 신장트리를 찾는 것이다. MST를 구할 때 대표적으로 쓰이는 프림(Prim), 크루스칼(Kruskal) 알고리즘에 대해 알아보자. 프림(Prim) : 정점을 선택/미선택 집합으로 구별하고, 선택된 정점 미선택된 정점 사이의 간선 중 가장 작은 간선을 택하면서 정점을 연결해나가는 방법의 풀이이다. => 정점 중심 풀이 [풀이 순서] 1. 임의의 정점을 하나 선택. 2. 선택된 정점들로부터 인접한 아직 선택되지 않은 정점까지의 가장 ..

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 더보기 문제 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의..