2JINISHAPPY 2JINISHAPPY

이진트리에는 여러 종류가 있다 트리 중에서도 가장 많이 사용하는 것이 이진트리이지만, 이진 트리들에도 명칭이 존재한다 Binary Tree의 종류에는 1️⃣Full Binary Tree 2️⃣Perfect Binary Tree 3️⃣Complete Binary Tree 가 있다 세 가지 트리를 한글로 번역하면... 그렇다 트리들의 이름만으로는 분간이 안 간다 그럼 세 가지 트리는 어떤 특징을 가지고 있고, 어떻게 다를까? 1️⃣ Full Binary Tree full binary tree는 모든 node의 child가 2개 or 0개인 트리를 말한다. 즉, leaf node가 아닌 node는 child를 두 개 가져야만 한다는 뜻이다 😄 그림의 오른쪽 트리에서, '2'와 '4'는 child를 하나씩 가졌..

www.acmicpc.net/problem/1493 1493번: 박스 채우기 세준이는 length × width × height 크기의 박스를 가지고 있다. 그리고 세준이는 이 박스를 큐브를 이용해서 채우려고 한다. 큐브는 정육면체 모양이며, 한 변의 길이는 2의 제곱꼴이다. (1×1×1, 2×2×2, www.acmicpc.net 분할 정복을 이용한 문제 L * W * H의 길이를 가진 박스를 분할해서, 가지고 있는 큐브들로 채우는 문제이다 큐브의 한 변은 2의 거듭제곱 꼴로 제한되어 있다 이 때, 박스에 같은 부피의 빈 칸이 있다면 무조건 큰 큐브로 채우는게 유리하다 Why? 만약 K*K*K 크기의 빈 칸을 현재 사용 가능한 작은 큐브로 채우는게 큰 큐브보다 총 큐브 수가 적다고 가정. but 작은 큐..

스택 실생활에서도 정말많이 사용하는 자료구조이다 물론 Computer Science에서도 정말정말정말 중요하고 몰라서는 안될 자료구조이기도 하다 인터넷 방문 기록(뒤로가기)의 구현에도, 함수의 재귀 호출에도 스택이 사용된다 하지만 스택에 대해서 음 후입선출~ 정도까지만 간략히 알고있는 경우가 많다 또 스택이면 스택이지 ADT 스택은 뭘까? 우선 스택에 대해 간략하게 알아보자면 스택에는 데이터들이 저장되어 있다. 가장 위(마지막)에 저장한 데이터의 위치를 스택의 탑이라고 한다. 데이터의 추가/삭제는 오직 스택의 탑 위치에서만 가능하다. ADT Stack은 어떠한 자료의 형태에 'Stack'이라고 명명할 수 있게 하는 자료의 형태와 연산을 정의한 것을 말한다. 즉, 이것을 만족하지 않는 자료는 스택이라고 할..

www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 전형적인 DP문제이다 iteraton을 이용해서 구현하되, 현재 칸에서 이동 가능한 칸 중 최소 점프 수를 갱신할 수 있다면 해준다 n=int(input()) arr=list(map(int,input().split())) dp=[987654321 for _ in range(n+1)] dp[0]=0 for i in range(len(arr)): for j in range(i+1,i+arr[i]+1): ..

우리가 정말 많이 사용하는 재귀함수 처음에는 개념과 구현이 조금 헷갈리지만, 시간이 지나면 이만큼 편한게 없다 하지만 재귀함수를 구현할 때에는 몇 가지 주의할 점들이 있고, 이를 지키지 않으면 수많은 오류가 발생할 수 있다 재귀: 특정 개념 or 함수를 정의할 때 자기 자신을 이용하는 방법 ex) 내 연봉은 1년에 천만원씩 증가하고, 입사 첫 연봉은 1억원이었다. 이 경우 현재 나의 연봉은 (작년 연봉 + 천만원)이며, 입사 몇년차인지에 따라 연봉 금액이 달라진다. 현재 연봉을 정의하는 데에 작년 연봉을 이용하는 이러한 예시가 재귀라고 할 수 있다. 재귀를 처음 학습할 때 참고하는 대표적인 예시 두 가지가 있다 그것은 바로 Factorial과 Fibonacci 1️⃣ Factorial: 어떤 자연수 n에..

C++의 vector는 다양한 연산들이 존재한다 (아래 포스팅 참조) 2jinishappy.tistory.com/67 [STL] vector 생성자, 함수 및 iterator 사용법 C++에서 사용되는 벡터(vector)는 배열과 유사한 자료구조지만 자동 크기 조절과 객체의 추가 삭제를 제공한다 크기가 가변적이거나 객체의 추가 및 삭제가 자주 일어날 때, 동적인 상황에서 자주 2jinishappy.tistory.com 정적 array와 비교되는 vector의 가장 큰 장점은 stl 라이브러리 내에서 자동으로 크기를 조절해주고, element들의 추가 및 삭제가 굉장히 용이하다. 또한 다양한 멤버함수들을 제공해줘서 vector를 이용한 다양한 연산을 할 수 있다. 우리는 vector의 자동 크기 조절에 대..

www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 전형적인 DP문제인 구간합 구하기이다 !! 1. 문제 정의 (x1, y1)부터 (x2, y2)까지의 직사각형 영역에 있는 element들의 합을 구한다 2. Subproblem & Recurrence (0,0) ~ (X2,Y2)까지의 구간합은 (X1-1,Y2)의 구간합+ (X2,Y1-1)의 구간합 - (X1-1,Y1-1)의 구간합으로 나타낼 수 있다(아래의 그림 참조)..

www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net valid parentheses string(vps)를 활용하면서, 스택을 활용하는 전형적인 문제 여는괄호가 나오면 그대로 push하고, 닫는 괄호가 나올 때 pop한 뒤 다시 연산해서 스택에 push한다 정확히는, 위의 그림처럼 1. 여는 괄호가 나오면 기호를 구분해서 push( '('는 0, '['는 1)한다. 2. 닫는 괄호가 나오면 해당 괄호와 일치하는 여는 괄호가 나올 때 까지(중간 과정에 숫자가 있..