[알고리즘] 위상정렬(Topology Sort)
·
공부/알고리즘
참고 자료GeeksForGeeks : https://www.geeksforgeeks.org/topological-sorting/?ref=header_outindyoungeui_hong.log : https://velog.io/@youngeui_hong/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC-%EB%AC%B8%EC%A0%9C-%EC%B4%9D-%EC%A0%95%EB%A6%ACClaude AI ( 문법 확인용 )🖐️[알고리즘] 위상정렬(Topology Sort)위상정렬은 순환성이 없는 방향 그래프(DAG)에서 사용 가능한 알고리즘이며, 결과 값으로 그래프의 노드들을 선형적으로 나타낸다. 이때 결과 값은 항상 일정하..
[자료구조] 동적 메모리 할당
·
공부/자료구조
☑️ 동적 메모리 할당동적 메모리 할당은 C언어에만 한정된 개념이 아니라, 다양한 프로그래밍 언어에서도 사용되고 있는 개념이다. 동적 메모리 할당의 내용과 사용 방법 자체는 어렵지 않다. 이 개념은 프로그램이 실행 중(런타임)에 있을 때, 필요한 시점에서 메모리를 할당 받고 필요하지 않은 시점에서 할당 받은 메모리를 반환하는 것을 의미한다. 반대되는 개념으로는 정적 메모리 할당이 있다. 🟧 동적 메모리 할당의 장점프로그램이 실행되는 동안에 원하는 크기의 메모리를 할당 받을 수 있어 유연성이 높아진다. 사용자의 입력에 따라 메모리 크기를 가지는 가변 크기의 자료구조를 구현할 수 있다. 🟧 동적 메모리 할당의 단점만약, 메모리를 할당하고 할당 해제하는 것을 까먹는다면 메모리 누수가 생긴다. 🟧 가비지 ..
[알고리즘] LCS(Longest Common Subsequence)
·
공부/알고리즘
참고 자료Introduction to Algorihms (CLRS)GeeksForGeeks : https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/SNU OPEN COURSEWARE : https://ocw.snu.ac.kr/sites/default/files/NOTE/Week 6_2.pdfCarnegie Mellon Univ : https://www.cs.cmu.edu/~15451-s15/LectureNotes/lecture04.pdfClaude AI ( 문법 확인용 )🖐️[알고리즘] LCS(Longest Common Subsequence) LCS는 공통 부분 수열 중에서 길이가 가장 긴 공통 부분 수열, 즉 최장 공통 부분 수열을 의미한다...
[알고리즘] 백트래킹(Backtracking)
·
공부/알고리즘
☑️ 백트래킹(Backtracking)해를 찾다가 더 이상 진행할 수 없으면, 다시 뒤로(Back) 돌아가서 해를 찾는 방법을 의미한다.수학과 친하지 않기 때문에 다른 방식으로 설명하면 모든 조합의 수를 탐색하지만, 조건이 맞는 경우만 탐색한다. 조건에 부합하지 않으면 제외한다.  ☑️ DFS / BFS랑은 무슨 관계인가?백트래킹에 관련된 키워드로 DFS와 BFS를 들을 수 있다. 백트래킹 알고리즘은 DFS와 BFS 알고리즘과 무슨 관계에 있을까? 별 것 없다. DFS와 BFS 알고리즘을 통해서 백트래킹을 구현할 수 있다. 백트래킹은 일종의 추상적인 개념과 같다면, DFS와 BFS는 추상적인 개념을 기법으로 정의해둔 것이다. 우리가 여기까지 알았다면 이제 이렇게 말할 수 있다.아! 백트래킹 문제니까 DF..
[알고리즘] 재귀란 무엇인가?
·
공부/알고리즘
☑️ 재귀란 무엇인가?드디어 블로그에 재귀를 포스팅한다. 짧은 크래프톤 정글 기간에 나를 많이 괴롭혔던 이론이다. 재귀란 무엇인가? 간단하고 쉽다. 재귀는 자기 자신을 참조하는 알고리즘이다. 어? 자기 자신을 참조한다고? 이게 무슨 의미지? 싶다면 아래 사진을 보자. 재귀의 이론 자체는 어렵지 않다. 정말 그대로 자기 자신을 참조하는 알고리즘이 전부이기 때문이다. 사실 프로그래머는 코드로 이해하는 게 더 빠를 수 있다. 바로 팩토리얼을 구하기 위해서 재귀를 사용한 예시를 보자.def factorial(a : int) -> int: if a  팩토리얼은 정수 1부터 N까지 곱한 연산을 결과로 반환한다. 수학적으로는 다음과 같이 표기하고 연산한다.5! (5 팩토리얼) // 5 * 4 * 3 * 2 * ..
[자료구조] 배열이란 무엇인가?
·
공부/자료구조
☑️ 배열이란 무엇인가?배열은 연속된 자료구조(Contiguous Data Structures)를 가지는 대표적인 예시다. 연속된 자료구조는 단일 메모리 청크에 모든 원소를 저장하며, 모든 원소의 접근 소요 시간은 일정하게 O(1)을 가진다. 또, 연속된 자료구조의 특징으로 캐시 지역성(Cache Locality)이 있는데, 이는 연속된 자료구조의 특성 상, 원소와 원소가 인접하기 때문에 주변 원소에 접근할 때 빠르게 접근할 수 있도록 원소 하나를 가져올 때, 주변 원소를 캐쉬(Cache)에 가져오는 것이다. 위의 설명한 특성들로 인해서 배열의 원소들은 각자 같은 크기의 메모리 공간을 가지는데, 이 공간들은 연속성을 가진다. 그렇기 때문에 다음과 같은 수식을 통해서 인덱스의 위치를 찾을 수 있다.배열 원..