열심히 코딩 하숭!

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

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

프로그래머스 알고리즘 고득점 kit 문제 풀이 스터디 2주차!스택/큐 문제를 풀기 전에 개념정리를 하려고 한다. 스택 큐는 학교 프로그래밍(C++) 수업 때 배웠고 익숙하지만python으로 코드를 짜려고 하니 헷갈려서 간단하게 정리를 하게 되었다! 스택LIFO (Last In First Out) 가장 먼저 들어온 데이터가 가장 나중에 나간다top을 통해서만 push 또는 pop이 가능하다. python에서 스택 구현python의 append() 함수를 사용해 pushpop() 함수를 사용해 pop을 진행한다.단순하고 바로 이해된다. 모든 함수들의 계산 복잡도도 O(1)로 효율적이다더보기class Stack: def __init__(self): self.stack = [] def p..

해시테이블이란?특정 키를 빠르게 검색, 삽입, 삭제할 수 있도록 설계된 자료구조(key값을 일일히 하나씩 비교하며 value를 찾지 않고, 해시함수를 사용해 바로 인덱스를 찾아가기 때문에 빠르다!)충돌되었을 땐, 해시테이블에 키도 저장되어있어야 충돌 문제 해결을 할 수 있음!그래서 보통 해시테이블에는 key와 value가 함께 저장되어있음(이해가 되지 않는다면 아래에 나오는 충돌 문제 부분과 궁금증 부분을 확인하면 된다.) 용어해시 함수(hash function): 입력된 키를 해시값으로 변환하여 배열의 인덱스로 변환하는 함수해시 테이블(hash table): 해시값을 인덱스로 하여, 실제 데이터를 저장하는 배열 기본적인 동작 과정1. 저장할 키가 주어지면, 이를 해시 함수에 넣어 해시 값을 계산2. 계..

문제 풀이 처음에는 list에 각 색종이의 왼쪽아래 꼭지점 좌표 정보를 [a, b] 형태로 저장하고 겹친 부분을 구했는데 넓이가 마이너스 값이 나왔다~ 알고보니 색종이가 3개 이상씩 겹치는 걸 계산 안 해줬던... 이런~ ^^ 그래서 겹치는 문제를 해결하기 위해 100 X 100 행렬을 만들어서 도화지를 100 X 100 픽셀이라고 생각하고 계산해주었다. paper = [[0 for _ in range(100)] for _ in range(100)] T = int(input()) for i in range(T): a, b = map(int, input().split(' ')) for j in range(a-1, a+9): for k in range(b-1, b+9): paper[j][k] = 1 area..

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..