말감로그

회고 오늘은 3주차 마지막 수요일이다. 내일 시험 보면 또 조가 바뀌고 새로운 발제가 시작된다. 다음주부터는 c언어랑 R-B트리 등 등 배운다는데 벌써부터 어려울 것 같다.. 이번 3주차를 요약하자면 2주차 시험을 탈탈 털려버린 것과 코치님과 커피챗을 하게 됐는데 나의 문제점을 정확히 짚어주셔서 팩팩폭을 맞아버린 것이 가장 큰 것 같다. 나의 큰 문제는 정확성이 없는 것과 시간 분배를 못하는 것, 내 것으로 만들지 못한다는 것? 끝까지 가지 않고 하다가 만다는 것.. 더 열심히 해야되겠다.. 공부 키워드 그리디 알고리즘(탐욕법, Greedy Algorithm), 다이나믹 프로그래밍(동적 프로그래밍), Knapsack Problem, LCS, 분할정복, 연결리스트(Linked List), 포인터 CSAPP..

그래프 탐색의 목적은 모든 정점을 한 번씩 방문 하는 것이다. 어떻게 방문할 것이냐에 따라 DFS와 BFS로 나뉜다. DFS - 깊이 우선 탐색 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식. 모든 노드를 방문하고자 하는 경우에 이 방법을 사용 그래프의 구조를 파악하는데 유용 BFS에 비해 간단하지만 검색 속도가 느림 스택 또는 재귀함수로 구현 활용: 미로 찾기 DFS 구현 방법 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노..

위상정렬(Topological Sorting)? 정렬 알고리즘의 일종으로, 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘. 사이클이 없는 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'을 의미 사용 사례 (ChatGPT 검색..) 작업스케줄링 컴파일러 최적화 의존성 관리 과목 수강신청 일정 계획 네트워크 토폴로지 설계 위상정렬을 알아가기 위해 진입차수와 진출차수를 알아야 한다. 진입차수(Indegree) : 특정한 노드로 들어오는 간선의 개수 진출차수(Outdegree) : 특정한 노드에서 나가는 간선의 개수 위상 정렬 알고리즘 동작 과정 진입차수가 0인 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다. 큐에서 원소를 꺼내 해..

그래프는 비선형자료구조이다. 그러면 비선형자료구조는 무엇인가? 비선형자료구조란? 비선형 자료구조란 데이터를 일렬로 구성하지 않고, 자료 순서나 관계가 복잡한 자료구조이다. 자료를 계층적으로 구성한 자료구조, 데이터가 일렬로 연결되는 선형 자료구조와 달리 분기점이나 사이클 등이 존재하여 비선형적인 구조를 가지고 있다. 선형 자료구조보다 복잡한 구조를 가지기 때문에 구현 및 관리가 어려울 수 있지만, 적절하게 활용하면 다양한 문제를 해결할 때 도움. 그래프 정점(vertex)이라고 불리는 노드(node)들과 이 정점을 연결해주는 간선(edge)으로 이루어진 자료구조 그래프 관련 용어 정점(node,vertex) : 데이터를 저장하는 위치 간선(edge, arc) : 정점(노드)를 연결하는 선, 링크 or 브..

알고리즘 문제를 풀다 알게 된 정보들에 대해 정리해봤다. 알고리즘 문제 푸는게 익숙치 않아서 풀이를 많이 참고하게 되는데 아직은 초보인지라.. 그래도 그만큼 알아가는 것들이 많은 것 같다! [백준 2562] 최댓값 a = [] for i in range(1,10): a.append(int(input())) print(max(a)) print(a.index(max(a))+1) 최댓값 내장 함수 max() 최솟값 내장 함수 min() 인덱스 값 구하기 list.index() [백준 11654] 아스키 코드 text = input() print(ord(text)) ord() : 문자 -> 아스키 코드 변환 chr() : 아스키 코드 -> 문자 변환 print(chr(65)) [백준 9020] 골드바흐의 추측 ..

복잡도란? 알고리즘의 성능 , 효율성을 나타내는 척도 크게 시간 복잡도와 공간 복잡도로 나눌 수 있다. 각 알고리즘이 주어진 특정 크기의 입력(n)을 기준으로 수행시간(연산) 혹은 사용공간이 얼마나 되는지 객관적으로 비교할 수 있는 기준 복잡도를 나타내는 방법 점근 표기법으로 빅오, 오메가 ,세타 등 -> 즉 ,어떤 알고리즘이 효율적인지를 판단하는 척도 수행시간 -> 시간 복잡도, 메모리 사용량 -> 공간 복잡도 시간 복잡도(Time Complexity) 알고리즘을 실행하여 종료할때까지 필요한 시간 (얼마나 빠른지) 특정 크기의 입력을 기준으로 할 때 필요한 연산의 횟수 이름은 시간 복잡도이지만 실행시간이 아닌 연산 횟수를 세는 이유는 모든 OS, IDE, 플랫폼에서 동일한 결과가 나오지 않음. 실행 시..

지나온 과거에 대한 성찰 나는 전공자로써 대학을 졸업하였지만, 그때는 그저 학점을 잘 받기 위해서 이해하려는 것보다 거의 외우면서 공부를 했던 것 같다. 그러다보니 여러 기술 스택들에 대해 얕은 지식만 쌓이고 졸업 후에 본격적으로 내가 하고 싶은, 가야 할 분야를 정해야겠다 싶어 먼저 html과 css, 파이썬 공부를 하였지만 이것 또한 오래가지 못하다보니 꾸준히 한 가지 일을 끝내지 못하고 다른 길로 빠지는 일이 많았다. 그러다 작년 6개월동안 유니티를 배우고자 게임 학원을 다니면서 꾸준히 공부하는 습관의 중요성을 알게 되었고 기초의 중요성을 알게 되었지만 열심히 공부하지 않아 아마 지금 다 까먹었을 거다... 그리고 게으른 성격 때문에 지각도 많이 하고 집중력도 낮아 오래 의자에 앉아있지도 않고 집에..

Red-Black 트리 - 이진 탐색 트리(BST)의 한 종류 - 스스로 균형 잡는 트리 - BST의 worst case의 단점을 개선( O(N) -> O(logN) - 모든 노드는 red or black RBTree 특성 #1 모든 노드는 Red or Black #2 루트 노드는 Black #3 모든 nil(leaf)는 Black #4 Red의 자녀들은 black -> red가 연속적으로 존재할 수 없다 #5 임의의 노드에서 자손 nil노드들까지 가는 경로들의 black 수는 같다. (자기 자신은 카운트에서 제외) nil노드란? 존재하지 않음을 의미하는 노드 자녀가 없을 때 자녀를 nil노드로 표기 값이 있는 노드와 동등하게 취급 RB 트리에서 leaf 노드(자식 없는 노드)는 nil노드 노드 x의 b..

동적 메모리 할당이란? - 컴퓨터 프로그래밍에서 실행 중(런타임)에 사용할 메모리 공간을 할당하는 것을 의미한다. - 프로그램이 실행되기 전, 컴파일 시점에 소스 코드를 읽고 메모리 공간을 확보하는 것을 정적할당 이라고 한다. - 컴파일 타임이 아닌 프로그램이 실행되는 중인 런타임에 필요한 만큼의 메모리 공간을 확보하는 것을 동적할당 이라고 한다. 동적 할당이 필요한 이유? 그때 그때 필요할 때마다 새로운 메모리 공간을 할당하는 것이 아니라, 컴파일 타임에 미리 넉넉한 메모리 공간을 확보해두면 되지 않을까?? → 가능하다. 하지만 메모리란 무한한 자원이 아니라 한정되어있다. 만약 우리가 1000000byte 사이즈의 메모리를 할당해두고 실제로는 10 byte만 사용한다면, 남은 메모리 공간을 비효율적으로..