개발자일걸요..?

문제링크 : www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 동일한 계산을 반복하는 것을 막기 위해(동적 계획법) 위에서 부터 아래로 계산해 내려감 1) 0번째줄은 변동될 사항이 없으므로 생략. 1번째 줄 부터 윗줄로부터 영향을 받아 변경될 수 있는 수 중 가장 큰 수로 값 변경 1-1) 매 줄의 0번째 값은 바로 윗줄의 0번째 값으로만 영향을 받음 1-2) 매 줄의 마지막 값은 바로 윗줄의 마지막 값으로만 영향을 받음 1-3) 그 외의 값들의 윗 줄의 대각선 두 값중 큰 값을 골라서 더함 2) 매 줄의 매 칸마다 계산하는 동안 ..

문제 링크 : www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 1) 작은 수들(내림차순)과 큰 수들(오름차순)을 구분해서 두개의 priority queue에 각각 집어넣음 2) 입력 받는 수를 두 개의 queue에 번갈아가면서 input 3) 만약 작은 수들 중 제일 큰 값이 큰 수들 중 제일 작은 값보다 클 때 두 수를 swap (작은 수 들 중 제일 큰 값< 큰 수들 중 제일 작은 값 일때까지) 4) 결국 중앙 값은 작은 수들 중 제일 큰..

문제링크 : www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 버전 1. vector를 이용하여 heap 구현(메모리 : 2800KB 시간 : 984ms) #include #include #include using namespace std; void del(vector &d) { d[1] = d[d.size() - 1]; d.erase(d.end()-1); int now = 1; long mini = 0; int miniInd = 1; w..

문제링크 : www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 결과값을 계산해 놓는 배열이용 & 최소의 경우 +1로 횟수 늘려가기 1) 결과값을 계산할 배열을 선언 & 초기화 2) index가 0, 1 일 경우는 0으로 고정 시켜놓기 3) index가 2이 이상일 경우부터, 1씩 뺏을 경우(즉, d[index-1]의 값 +1)로 일단 변경 3-1) 혹시 i가 3으로 나누어지며, d[index//3]+1의 값이 앞서 변경해놓은 값보다 작을 경우 변경 3-2) 혹시 i가 2으로 나누어지며, d[index//2]+1의 값이 앞서 변경해놓은 값보다 작을 경우 변경 4) index가..

문제링크 : www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 1) 조건에 맞춰 삭제 시 1-1) 입력값이 없을 경우 return 0 1-2) 그외의 경우 root위치의 요소를 임시로 저장->마지막요소를 root자리로 끌어옴(set, remove이용) root요소를 그 밑의 서브트리와 비교하여 작은 게 root로 오게 재정리 2) 조건의 맞춰 입력시 배열에 제일 마지막에 넣은뒤, 해당 요소의 parent값과 비교하여 작은 순으로 정렬(해당요..

문제링크 : www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 최대값을 간편하게 pop하기 위해서 입력값에 -1을 곱해서 입력 & 출력시 -1을 곱해서 출력 위의 요소로 인해 heap의 형태가 실제 값으론 가장 큰 값이 위에 위치하게 됨 메모리 : 34700KB 시간 : 164ms import sys import heapq T = int(sys.stdin.readline()) heap = [] for _ in range(T): N = int..

문제 링크 : www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net - 미리 주어진 예시를 보면 i번째 삼각형의 변의 길이는 i-1번째 삼각형과 i-5번째 삼각형의 변의 길이의 합과 같다. 1) ArrayList에 0~4번째까지의 값을 미리 입력함 2) 5번째 값부터는 i-1번째와 i-5번째의 값을 더해서 추가로 입력 3) 이를 N번째까지 반복하여 결과값 찾아 출력 - list에 들어가는 객체값이 어느 순간 int의 범위를 벗어날 수 있으므로 가능한 큰 데이터형을 주어..

문제링크 : www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 00과 1로 만들 수 잇는 조합 결과를 생각하기 보단 그 조합의 갯수를 생각해야함 1) N이 0개인경우, 1개인경우, 2개인 경우를 미리 계산해 배열에 넣어둠 2) 그리고 N번째까지 배열의 값을 구하기 3) 배열의 N번째 값 출력 버전 1. 재귀함수 사용 (시간초과) #include #include using namespace std; long long inttile(int n) { if (n == 0)..

문제링크 : www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 1) 우선 주어진 조건에 따라 분기를 실행하여 재귀 함수 구조를 만든다. 2) 앞에서 이미 한 연산을 뒤에서 또하면 시간이 너무 많이 소요되기에 이미 한 연산은 3차배열을 통해 저장한다. 3) 이미 앞서 계산한 값이 있으면 그 값을 return하고 없으면 계산하는 과정을 거친다. 메모리 : 2052KB 시간 : 504ms #include using namespace std; int d[21][21][2..

문제링크 : www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 1) 함수를 이용하여 지수가 0혹은 1이 될때까지 반복해 2로 나누기 2) 지수가 0이면 1, 1이면 밑을 C로 나눈 값을 return 3) 지수가 그 이상일 경우 홀수인지 짝수인지를 구분하여 pow 함수처럼 곱셈하여 return 메모리 : 2016KB 시간 : 0ms #include using namespace std; long long int divisionAlgo(long long int A, long long int B, long long int C) { ..