말감로그

위상정렬(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만 사용한다면, 남은 메모리 공간을 비효율적으로..

1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 문제 언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다. 그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적..

1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보..