열심히 코딩 하숭!

드디어 재귀함수 복습 시간이 왔다!!! 휴학하고 알고리즘 개념을 까맣게 잊어버리면서 살았더니재귀에 대한 두려움이 생긴 것 같다... 다시 열심히 복습해보자!!!   재귀 함수함수가 자기 자신을 호출하여 문제를 반복적으로 해결하는 기법주로 문제를 작은 단위로 나누고, 반복적으로 처리해야 할 때 사용! 기본 구조 및 특징베이스 조건(Base Case)재귀 호출을 멈출 조건.  문제를 더 이상 나누지 않고 결과를 반환한다. 재귀 호출(Recursive Call)함수가 자기 자신을 호출하여 문제를 작게 나눈다.    특징함수 호출이 스택 구조로 쌓인다. 따라서 호출이 많아지면 Stack Overflow가 발생할 수 있다 def factorial(n): if n == 0 or n == 1: # 기저 조건 ..

힙(Heap)우선순위큐를 구현하는 데 주로 사용되는 트리 기반 자료구조 특정 규칙에 따라 부모 노드와 자식 노드 간의 관계가 정해져 있어,효율적으로 최대값이나 최소값을 빠르게 찾을 수 있다 힙의 특징[완전 이진 트리]힙은 항상 완전 이진트리의 형태를 유지함항상 왼쪽에서 오른쪽으로 순차적으로 채워지며, 마지막 레벨만 부분적으로 채울 수 있음 (차곡차곡) [최대 힙]부모 노드의 값이 자식 노드보다 항상 크거나 같음 [최소 힙]부모 노드의 값이 자식 노드의 값보다 항상 작거나 같음 힙의 구조트리 구조이지만 배열로 구현되는 경우가 많음!완전 이진 트리 구조이기 때문에, 배열 인덱스만으로 부모와 자식 노드를 효율적으로 찾을 수 있다 부모 노드 인덱스: i왼쪽 자식 인덱스: 2i + 1오른쪽 자식 인덱스: 2i +..

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net #include #include using namespace std; pair arr[100000]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; cin >> N; int num; for (int i = 0; i > num; i..

https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 숫자 카드를 입력받고 주어진 숫자가 숫자 카드 내에 있는 숫자인지 검사하는 문제. 주어진 숫자들의 범위를 보아하니... 최대한 시간을 단축할 수 있도록 문제를 풀어야겠다고 생각했다. 풀이 첫번째는 시간 초과로 실패하고, 다른 방법으로 다시 도전했을 때 성공했다. 우선 성공한 코드부터 설명하자면, 먼저 숫자 카드를 오름차순으로 정렬하고, 이분검색 (Binary Sear..

https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 풀이 C++의 배열 정렬 함수 sort를 이용하고, compare 함수를 선언해서 문제에 맞는 조건을 적용시켜줬다. #include #include #include using namespace std; bool compare(const pair &a, const pair& b) { if (a.second.first == b.second.first) { return a.first < b.first; } ..

https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 풀이 경우를 생각하여 계산해주었다. 만약 N이 5로 나누어 떨어지는 게 아니라면 계속 3으로 빼주고 5로 나누어 떨어지는 순간이 올 때 호다닥 5로 빼준다. 근데 DP로도 풀어볼 수 있을 것 같은데, DP 식 짜는 게 아직 익숙하지 않고 넘 어렵다... 그래서 DP로 짜는 방법은 블로그를 참고하여 풀었다. #include using namespace std; int main() { ios_base::sync..

https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 풀이 1. string을 받아서 2. 중복은 제거하고 -> set 자료구조 사용 3. 길이를 비교한 후 -> set에 Compare 4. 길이가 같으면 사전 순으로 배열시키고 5. 출력시켜야한다. 아이디어는 떠올랐으나, set 함수를 내가 원하는 조건에 맞게 정렬하는 방법을 모르겠어서, 해당 부분은 블로그를 참고하였다. (참고한 블로그: https://retn0.tistory.com/5..

https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 계속 더해가면서 합을 구해야한다. (이걸 뭐라고 하더라? 등차수열은 아니고 아무튼 계속 더해나가야 함) 그러므로, 반복되는 값들이 최소가 되도록 해줘야 함. -> 오름차순으로 정렬한 후, 더해주기. 오름차순은 sort 함수를 이용했다. 풀이 #include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout..

https://www.acmicpc.net/problem/10250 10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net 복잡해보이지만, 간단한 문제다. 나머지와 몫 연산만 잘 하면 된다! 풀이 #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int T, H, W, N; cin >> T; for (int i = 0; i > H >>..

https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 처음에는 직접 경우의 수를 계산해보며 규칙을 찾아내려고 했는데 그려도 감이 안 왔다... 아놔!!! 그래서 블로그를 참고하여 규칙을 다시 찾아봤다. 표를 쓰면서 확인해야 규칙이 잘 보이는구나... 어쨌든 이렇게 이전 열의 값과 이전 행의 값을 더하면 현재 값이 된다! arr[i][j] = arr[i - 1][j] + arr[i][j - 1]; #include using namespace std; int arr[201][201]; int main() { ios_base::sync_with_stdio(false); cin..