Problem_Solving
-
BOJ 9934 완전 이진 트리Problem_Solving 2020. 2. 2. 17:41
문제링크 9934번: 완전 이진 트리 문제 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 그림) 각 노드에는 그 곳에 위치한 빌딩의 번호가 붙여져 있다. 또, 가장 마지막 레벨을 제외한 모든 집은 왼쪽 자식과 오른쪽 자식을 갖는다. 깊이가 2와 3인 완전 이진 트리 상근이는 도시에 있는 모든 빌딩에 들어갔고, 들어간 순서대로 www.acmicpc.net #문제 설명 주어진 조건과 노드의 순서를 보고 완전 이진 트리를 구하는 문제 - 주어진 조건 1) 루트에서 시작 2) 왼쪽 노드를 방문하지 않았다면 왼쪽 노드 방문 3) 왼쪽노드를 가지고 ..
-
BOJ 2357 최솟값과 최댓값Problem_Solving 2020. 2. 1. 20:42
문제 링크 1. 문제 설명 N 개의 정수가 주어지고 M개 구간 a와 b가 주어질 때 구간 [a,b]의 최소값과 최대값을 구하는 문제 2.풀이 방법 1) Segment Tree를 이용 하여 구한다. 2) 코딩을 간단하게 하기위해 최소 값 또는 최대값 세그먼트를 구현한뒤 트리를 빌드 할 때 -1를 곱한다. 3.세그먼트 트리 설명 Divide : input으로 들어온 데이터를 반으로 나눈다. Conquer : Divide에서 나누어진 Sub Array A[1...mid] B[mid...N] 의 최소값 또는 최대값을 재귀 적으로 구한다. Combine : 두개로 나누어지 배열에 A, B에서 최소값을 리턴받아 해당 노드에 저장 - 노드에 적혀 있는 번호가 배열의 인덱스 번호 - 해당 구간은 리턴되는 값 만약 N개..
-
Codeforce #521 Div3 D. Cutting OutProblem_Solving 2018. 11. 18. 02:35
문제 원본 문제 설명 배열 S가 주어 졌을 때 길이가 k인 S의 부분 배열 t를 이용해 원소를 제거할 때 가장 많은 시간을 수 행 할 수 있는 부분 배열 t를 구하는 문제 ex 7개의 S배열 원소 3개의 부분 배열의 원소 개수 S = [1,2,3,2,4,3,1] 일 때 부분 배열 [1,2,3]일 때 2 번의 수행 시간동안 배열을 지울 수 있다. 1 번째 수행 때 S배열이 [1,3,2,4]가된다. 2 번째 수행 때 S배열이 [4]가된다. 3 번째 수행 하려고 할 때 S배열에 부분 배열 t가 존재 하지 않으므로 2번의 수행 시간이 걸린다. 문제 풀이 parametric search를 이용한 분제 1 step S배열의 각 원소의 개수를 구한다. 위 예에선 1 : 2개 2 : 2개 3 : 2개 4 : 1개 2 ..
-
Codeforce #521 Div3 E. Thematic ContestsProblem_Solving 2018. 11. 18. 02:05
문제 원본 문제 설명 문제 토픽 N개 가 입력으로 주어 진다. 하루에 하나의 콘테스트가 열리는데 같은 토픽 k개를 제출 할 수 있고 해당 콘테스트는 이전에 열린 콘테스트보다 정확히 2배 많은 토픽을 출제 해야 한다. 이때 최대로 낼 수 있는 문제를 구하는 문제 EX) 첫 번째 input data 18 2 1 2 10 2 10 10 2 2 1 10 10 10 1 1 10 10 첫 째날 1토픽 2개 둘 째날 2토픽 4개 셋 째날 10토픽 8개 총 14개의 문제를 출제 할 수 있다. 문제 풀이 1 step 입력 받은 원소를 정렬한다. 2 step 정렬된 입력받은 원소를 가지고 이분 탐색을 이용하면 각 원소의 개수를 구할 수 있다. 위 예에서 원소를 정렬 하면 1 1 1 1 2 2 2 2 2 10 10 10 1..
-
Array ManipulationProblem_Solving 2018. 11. 11. 14:46
해커랭크의 Array Manipulation문제 풀이문제원본 문제 설명 구간 a b에 k수를 더하는 쿼리가 들어오고, 모든 쿼리가 끝났을 때 배열에서 가장 큰 수를 리턴 하는 문제 문제 풀이 구간 시작 -1 인덱스에 K를 더한다 구간 끝 인덱스에 -K를 한다 배열의 시작부터 끝까지 누적합을 구해가면서 각 인덱스의 값중 최대값을 리턴한다. Ex) 1 5 3 [3,0,0,0,0,-3,0,0,0,0,0] 4 8 7 [3,0,0,7,0,-3,0,0,-7,0,0] 6 9 1 [3,0,0,7,0,-2,0,0,-7,-1,0] 여기서 주의 할점은 인덱스의 위치를 신경써서 저장해야 한다. 개구간인지 폐구간인지는 구현방법에 따라 다르다 소스 코드
-
Codeforce #515 Binary Numbers AND SumProblem_Solving 2018. 10. 28. 14:06
Codeforce #515 Binary Numbers AND Sum 문제 원본 문제설명 입력 조건 2개의 이진수 자리수 n,m 자리수 만큼 이진 수가 들어온다. 이진수 a 와 b를 and 연산 한 값을 구한 뒤 b를 오른쪽으로 shift연산을 한다. 다음 a와 이전에 b를 오른쪽으로 shift 여산한 값을 and연산 한 값을 구한뒤 현재 b를 shift한다. b가 더이상 shift할수 없을 때 까지 반복한다. 문제 풀이 1 step 이진수 a를 전처리 한다. 전처리 방법은 누적합을 구한다. ex) 이진수 1010이 주어지면 비트가 켜신곳에 2의 지수승을 더하고 이전 인덱스에 최종적인 합을 누적해서 보관한다. 만약 b의 이진수 길이가 더 클경우 부분합 배열을 b의 이진수 길이 만큼 구한다. 위의 배열의 값..
-
BOJ 16236 아기상어Problem_Solving 2018. 10. 27. 14:34
BOJ 16236 문제풀이 문제원본 문제 설명 주어진 조건 처음 상어의 크기가 2이고, 상어는 1초에 상하좌우로 이동할 수 있다. 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 물고기를 자신의 무게 만큼 먹으면 무게가 1씩 증가한다. 상어는 같은 크기의 물고기는 먹을 수 없지만 같은 크기의 물고기가 있는 칸은 지날 수 있다. 먹을 수 있는 물고기가 한 마리면 그 물고기가 있는 위치로 이동 만약 먹을 수 있는 물고기가 여러 마리 라면 가장 가까운 위치로 이동 거리가 같은 물고기가 많다면 가장 위쪽 이런 경우도 많다면 가장 왼쪽에 있는 물고기를 먹는다. 먹을 물고기가 없으면 종료한다. 구해야 되는 것 아기 상어가 주어진 조건에 맞춰 물고기를 먹을때 걸리는 시간 문제 풀이 1 step 현재 위치에서 도..
-
BOJ 2479 계단오르기Problem_Solving 2018. 10. 25. 23:37
BOJ 2579 문제 풀이 문제원본문제 설명 0번 째 지점에서 n번째 계단 까지 올라 갈때 최대로 얻을 수 있는 점수를 구하는 문제 단 계단을 하나 또는 두개를 밟을 수 있고 연속으로 세계를 밟을 수 없다. 문제 풀이 점화식 DT[현재 계단 위치][이전에 밟은 스탭] = MAX(DT[+1 계단][1], DT[+2 계단][2]) 단 연속 3계단은 밟지 않는다. 소스코드 사용 알고리즘GOC++DP 재귀호출 (N=300)4608kb/4ms (input에서 string으로 받음)1992kb/0ms