전체 글

11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 세그먼트 트리 개념 [Algorithm] 세그먼트 트리란? HTML 삽입 미리보기할 수 없는 소스 세그먼트 트리는 주어진 데이터들의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조의 형태입니다. 핵심 이론 세그먼트 트리의 종류 g-db.tistory.com 문제 어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 곱을 구하려 한다. 만약..

10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net 세그먼트 트리 개념 [Algorithm] 세그먼트 트리란? HTML 삽입 미리보기할 수 없는 소스 세그먼트 트리는 주어진 데이터들의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조의 형태입니다. 핵심 이론 세그먼트 트리의 종류 g-db.tistory.com 문제 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하..

HTML 삽입 미리보기할 수 없는 소스 세그먼트 트리는 주어진 데이터들의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조의 형태입니다. 핵심 이론 세그먼트 트리의 종류는 구간 합, 최대, 최소 구하기로 나눌 수 있습니다. 구현 단계에서 구현해야 하는 것은 트리를 초기화하기, 질의 값을 구하기, 데이터 업데이트 하기로 나눌 수 있습니다. 1. 트리 초기화 하기 리프 노드의 개수가 데이터의 개수(N) 이상이 되도록 트리 배열을 만듭니다. $2^k≥N$을 만족하는 k의 최솟값을 구하고 $2^{k+1}$ 크기의 트리 배열을 생성하면 됩니다. 또한 리프 노드의 시작 위치를 인덱스로 구해두어야 하는데, 리프 노드의 시작 위치는 $2^k$입니다. 예시 int[] data = {5, 8, 4, 3,..

2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 문제 어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다. 풀이 수들이 주어졌을 때 빈번..

20438번: 출석체크 1번째 줄에 학생의 수 N, 졸고 있는 학생의 수 K, 지환이가 출석 코드를 보낼 학생의 수 Q, 주어질 구간의 수 M이 주어진다. (1 ≤ K, Q ≤ N ≤ 5,000, 1 ≤ M ≤ 50,000) 2번째 줄과 3번째 줄에 각각 K명 www.acmicpc.net 문제 지환이는 무작위로 한 명의 학생에게 출석 코드를 보내는 행위를 Q번 반복한 뒤, 출석부 정리를 위해 특정 구간의 입장 번호를 받은 학생들 중에서 출석이 되지 않은 학생들의 수를 구하고 싶다. 풀이 해당 문제는 먼저 출석이 안된 인원의 범위를 주고 해당 범위 안에 몇 명의 출석이 안된 인원이 있는지를 묻고 있다. 범위를 주고 해당 범위에 대한 값을 빠르게 구하기 위해서 누적합을 사용했다. 📌 졸고 있는 학생 for(..

1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 문제 트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다. 풀이 해당 문제는 트리가 주어졌을 때 노드를 하나 지우고 해당 노드가 지워진 상태에서의 리프 노드의 개수를 구하는 문제였습니다. 저는 문제를 해결하기 위해서 해당 삭제되는 노드를 탐색하지 않고 DFS, BFS를 진행함으로써 삭제된 것 처럼 풀었습니다. 📌 입력 Stri..

11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 풀이 해당 문제는 전체 노드들을 돌면서 상위 노드가 누구인지 체크하는 문제였다. 따라서 인접 리스트 형태의 그래프를 구현하고 DFS와 BFS로 탐색하여 문제를 해결했다. 📌 입력 StringTokenizer st; for(int i=1; i

영속성 컨텍스트 엔티티 매니저는 엔티티를 저장, 수정, 삭제, 조회하는 등 엔티티와 관련된 모든 일들을 처리한다. 영속성 컨텍스트는 데이터베이스와 코드 사이의 가상의 데이터베이스 역할을 한다. 1. 엔티티 매니저 팩토리와 엔티티 매니저 엔티티 매니저 팩토리는 엔티티 매니저를 만드는 공장이며 스레드 세이프하게 설계되어 여러 스레드가 공유해서 사용하더라도 안전하게 사용할 수 있다. 엔티티 매니저는 보통 트랜잭션을 시작하면서 DB 커넥션 풀에서 DB 커넥션을 획득하며 스프링 프레임워크에서 JPA를 사용한다면 해당 컨테이너가 제공하는 데이터 소스를 사용한다. 2. 영속성 컨텍스트란? 엔티티 매니저를 통해 엔티티를 저장하거나 데이터베이스에서 엔티티를 조회하면 엔티티 매니저는 영속성 컨텍스트에 엔티티를 보관하고 관..