본문 바로가기

분류 전체보기

 (355)
BOJ-2042 구간 합 구하기 Swift 문제어떤 N개의 수가 주어져 있다. 그런데 중간에 수의 변경이 빈번히 일어나고 그 중간에 어떤 부분의 합을 구하려 한다. 만약에 1,2,3,4,5 라는 수가 있고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지 합을 구하라고 한다면 17을 출력하면 되는 것이다. 그리고 그 상태에서 다섯 번째 수를 2로 바꾸고 3번째부터 5번째까지 합을 구하라고 한다면 12가 될 것이다.입력첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄까지 N개의 수가 주어진다. 그리고 N+2번째 줄부터 N+M+K+1번째 줄까지 세 개의 ..
세그먼트 트리 Swift 세그먼트 트리세그먼트 트리는 트리형태의 자료구조로 해당 노드에는 구간합이 저장되어 있다.일반적으로 배열에서 특정 구간의 합을 구해야 한다면 O(N)이 걸린다.세그먼트 트리는 노드마다 구간의 합이 저장되어 있기때문에 해당 노드에 접근하여 반환하면 되므로 O(logN)이 걸리게 된다.이처럼 세그먼트 트리는 여러개의 데이터가 연속적으로 있을 때, 특정 구간의 합을 구하는데 효율적인 자료구조이다. 세그먼트 트리만들어보기배열 A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]이 주어졌다. 편의상 인덱스는 1부터 시작한다.12345678910이를 트리로 만들어보자.위 그림은 배열 A를 트리로 만들어본 형태다.왼쪽노드는 index*2, 오른쪽노드는 index*2+1이 되고, 트리의 특성상 합을 구하면 ..
분리집합과 Union-Find Swift 분리집합분리 집합은 서로 다른원소를 갖는 집합이다. 그래서 각각 분리집합의 공통원소는 없다.전체집합 U라고 하고, 분리집합 A와 B가 있다면, 아래의 수식이 성립한다.- U = A U B- A ∩ B = Ø(A와B는 U의 부분집합이다.)  Union-Find분리집합끼리의 표현을 효율적으로 구현하고, 조작하기 위해 생긴 알고리즘이다.서로다른 분리집합을 합치는 Union연산과 임의의 원소가 어디의 집합에 속하는지 알기위한 find연산이 주어져서 Union-Find라고 불린다.이 알고리즘을 사용하기위해 3가지의 연산을 구현해야한다. 1. 초기화: 기본적으로 구현하고 조작하기위해 분리집합을 구현해야한다. 분리집합의 원소는 자기 자신을 루트노드로 갖는다.2. Union(x,y): 두 원소 x와 y가 주어졌을때, ..
BOJ-1717 집합의 표현 Swift 문제초기에 𝑛+1개의 집합 {0},{1},{2},…,{𝑛}이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.집합을 표현하는 프로그램을 작성하시오.입력첫째 줄에 𝑛, 𝑚이 주어진다. 𝑚은 입력으로 주어지는 연산의 개수이다. 다음 𝑚개의 줄에는 각각의 연산이 주어진다. 합집합은 0 𝑎 𝑏의 형태로 입력이 주어진다. 이는 𝑎가 포함되어 있는 집합과, 𝑏가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 𝑎 𝑏의 형태로 입력이 주어진다. 이는 𝑎와 𝑏가 같은 집합에 포함되어 있는지를 확인하는 연산이다.출력1로 시작하는 입력에 대해서 𝑎와 𝑏가 같은 집합에 포함되어 있으면 "..
BOJ-2493 탑 Swift 문제KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가..
BOJ-1966 프린터 큐 Swift 문제여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 ..
BOJ-2473 세 용액 Swift 문제KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다.  산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.같은 양의 세 가지 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 세 가지 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 예를 들어, 주어진 용액들의 특성값이 [-2, 6, -97, -6, 98]인 경우에는 특성값이 -97와 -2인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수..
BOJ-2343 기타 레슨 Swift 문제강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다.강토의 각 강의의 길이가 분 단..

티스토리툴바