분류 전체보기 (102) 썸네일형 리스트형 [SW 정글] 5/1 ~ 5/4 TIL RB Tree (feat, C) 이번주차는 RED - BLACK TREE를 직접 구현해보는 것이 과제이다. rb tree의 조건은 다음과 같다 1. 모든 노드는 색을 가진다. Red or Black 2. root 노드는 black 3. leaf node는 black 4. red node의 child node는 black(black node의 child node는 상관없다.) 5. 각 노드에서 leaf node로 가는 경로 중 black node의 수는 항상 같아야 한다. (-> 이 조건 때문에 균형이 유지된다.) fact 1, v의 서브트리의 내부노드 개수 >= 2^(bh(v)-1) fact 2, black의 노드 개수 >= h/2 => black(root) >= h/2 fact 3, h = O(log2N) h(v) : v의 높이 bh.. [SW정글] 4/30 TIL - pointer -> Linked List, Queue(feat, C) 주소값 데이터의 주소값이란 해당 데이터가 저장된 메모리의 시작 주소를 의미한다. 예를 들어 int data는 4바이트 크기를 가지지만 int형 데이터의 주소값은 시작 주소 1바이트만 가리킨다. 포인터 메모리의 주소값을 저장하는 변수이다. 연산자 주소 연산자 & 변수의 이름 앞에 사용하며, 해당 변수의 주소값을 반환한다. ampersand라고 읽는다. 참조 연산자 * 포인터의 이름이나 주소 앞에 사용하며, 포인터에 가리키는 주소에 저장된 값을 반환한다. stack 구현 전역변수 Ver #include #include #include #define MAX_STACK_SIZE 100 #define MAX_STRING 100 // 학생 구조체 선언 typedef struct { int student_number.. [SW정글] 4/29 TIL - 메모리 누수, 균형이진트리, RB TREE(feat, C) 메모리누수 메모리 누수란 ? 컴퓨터가 필요하지 않은 메모리를 계속 점유하고 있는 현상이다. c는 파이썬이나 자바스크립트처럼 가비지 컬렉터가 없다. 사용자가 메모리를 할당해주고 해제?(free)를 해주지 않으면 메모리 누수 현상이 발생한다. malloc 등과 같은 메모리를 동적할당 했다면, 꼭! 꼮! free를 해주는 습관을 들이도록 하쟈! 균형 이진 트리 균형 이진 트리란? 말 그대로 균형이 잡힌 이진 트리이다. (높이는 O(logN)을 만족) 균형이 잡히지 않았다면 search까지 최대 O(N)이 걸릴 수 있기 때문에 나온 개념이다. 균형 이진트리의 종류로 AVL Tree, Red-Black Tree가 있는데 Red-Black 트리가 많이 쓰인다. 이유는 밑에서 설명하겠다. AVL Tree Avarag.. [SW정글] week04 후기 (feat, dp, 그리디) Dynamic Programming - DP 정의 - 큰 문제를 작은 문제로 나눌 수 있고, 그 겹치는 작은 문제들의 경우 메모제이션 기법을 사용하여 큰 문제를 푸는 기법 분할 정복을 하는데 그걸 메모제이션해서 나아간다. DP의 장점 - 모든 가능한 경우를 확인하기 때문에 근사치가 아닌 정확한 값을 얻을 수 있따. DP의 단점 - 모든 가능한 경우를 확인하기 때문에 시간복잡도가 크다. 알고리즘 주차를 진행하며 DP가 제일 어려웠다. 점화식을 떠올리는게 정말 어려웠고, 정답 코드는 너무 짧아서 보면 허무했을 정도다. 또한, 알고리즘이 너무 많았다. 예를 들어 Knapsack problem, LIS(Longest Increasing Sequence), LCS(Longest Common Sequence), .. [SW 정글] 백준 2098 외판원순회 - 비트마스킹(feat, Python) 잡설 이번 주차는 동적프로그래밍과 그리디 알고리즘에 대해 공부하고 문제를 푼다. dp문제는 풀 때마다 항상 다른 게 나오는 것 같다. 몇 문제 안 풀어 봣지만, 문제를 보고 어떤 알고리즘인지 아는 것이 중요할 것 같다. Kanpsack problem, bitmasking, LIS(Longest Increasing Subsequence), LCS(Longest Common Subsequence) 등이 있다. 다양한 문제들을 풀어보고 다양한 알고리즘들의 풀이법을 익히는 것이 중요할 것 같다. 위 4개의 알고리즘 문제를 만났을 때, 가장 어려웠던 bitmasking문제를 기록해놓으려한다. 정답 코드 import sys sys.stdin = open(‘input.txt’) N = int(sys.stdin.rea.. [SW 정글] 백준 2573 - 빙산 (feat, python) 문제 설명 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제 접근 1. 빙하 상하좌우에 바닷물이 몇 면에 접해잇는지 파악 2. 1년마다 빙하 녹이기 3. 빙하가 몇덩이인지 확인하기(2이상인지 0인지) 빙하가 1덩이라면 1, 2, 3을 계속 반복하긔 처음에는 빙하 하나씩 하나씩 차근차근 녹이려고 했다. 그러나 0 0 0 0 0 0 2 3 4 0 0 5 0 4 0 0 8 7 9 0 빙하가 있다고 하면 0 0 0 0 0 0 0 1 2 0 0.. [SW정글] week03 후기 + DFS, BFS, 위상정렬 한계를 경험하고 극복해라. - Youngji Jang 재수시절, 선생님에게 "혁아, 너는 잠때문에 인생 망할 거같다."라는 말을 들은 적이 있다. 그 정도로 나는 잠이 많다. 그러나 정글에 와서 "한계를 경험하고 극복해라" 라는 Youngji Jang의 말씀을 듣고 잠을 줄이려고 노력중이다. (오늘은 코피도 났ㄷr...) 실력이 느는 것이 체감이 들지는 않지만, 정글에 오기전에 백준 실버 4-5문제만 골라풀던 내가 이제는 골드문제도 두려워하지 않고 푸는 모습을 보고 뿌듯한 감정을 느낀다. 시간이 벌써 한달 가까이 됐다. 취업하는 날도 얼마 남지 않았으리라 믿는다. 그러나 4개월 후면 모두 흩어진다는 것이 조~~~끔 아쉽다. 잡설은 그만하고 week3동안 문제를 풀면서 느낀 점을 적어보쟈 최근 내카라 기출.. [SW정글] 분할정복(🔥), 이진 탐색 분할 정복이란 devide & conquer로, 큰 문제를 작은 문제로 나눠 정복하여 큰문제를 해결하는 것이다. 나는 이 방식을 모든 알고릐듬 문제에 다 적용시켜 문제를 풀려고 노력한다. 예를 들어 백준의 10830 문제를 보자 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제를 보고 답을 구하기 위해 내가 해야할 것들을 정리한다. 위 문제의 경우 1. 제곱을 분할 정복으로 빠르게 구하기 2. 행렬의 곱셈 3. 행렬에 1000 나눠주기 로 작은문제들로 분.. 이전 1 2 3 4 5 6 ··· 13 다음
