전체 글 (55) 썸네일형 리스트형 위상 정렬 - Topological Sort ) 안녕하세요 오늘은 위상 정렬에 대해서 공부 해 보겠습니다. 위상 정렬에서 위상은 어떠한 사물이나 작업이 가지는 위치나 상태이고 그 위치들 간의 상호관계를 의미하고어떤 사물이나 작업들이 어떻게 연결되고 어떤 순서로 배치되어 있는지에 대한 구조적 관계를 의미합니다. 위상 정렬은 순서에 제약이 있는 작업들을 올바른 순서로 배열 하는 방법입니다.위상 정렬 알고리즘을 활용하려면 DAG(Directed Acycle Graph) 방향 비순환 그래프의 형태이여야 합니다.그리고 정렬의 올바른 결과는 하나 이상일 수 있습니다. 일상 속의 아침 준비시간을 예로 들어보겠습니다. 아침 작업양치하기세수하기머리 감기아침 먹기머리 말리기제약사항머리 감기는 머리 말리기 전 이어야 할 것아침 먹기 다음 양치하기 전 이어야 할 것 만약 .. Thread 반갑습니다 오늘은 Thread를 공부 할 것 입니다. 그 전에 알고 가야 할 지식 메모리 (Memory)메모리는 프로그램이 실행되는 동안 데이터와 명령어가 저장되는 공간주 메모리(RAM) 와 보조 메모리(HDD, SSD)로 구분할 수 있다계층적 구조를 띄고 있습니다 (레지스터 -> 캐시 -> 주 메모리 -> 보조 메모리) - (용량, 접근 속도, 비용)이 절충 관계이다주소를 통해 접근을 합니다 레지스터 (Register)레지스터는 CPU 내부에 있는 매우 빠른 소형 저장 장치입니다.CPU가 연산을 수행할 때 직접 접근하는 가장 빠른 메모리이고데이터와 명령어를 일시적으로 저장한다 힙(Heap) 힙은 프로그램 실행 중에 동적으로 할당되는 메모리 영역런타임에 크키가 결정프로그래머가 명시적으로 메모리를 .. 비트마스크 알고리즘 오늘은 비트마스크에 대해서 공부하며 기록을 할 것입니다. 비트마스크란 무엇일까요 비트마스크비트마스크(Bitmask)는 컴퓨터 알고리즘에서 매우 효율적인 방법입니다2진순의 비트를 이용하여 상태를 표현하고 조작하는 기법입니다. 비트마스크의 장점 메모리 효율성: 작은 집합을 표현할 때 매우 효율적인 메모리를 사용할 수 있습니다.연산 속도: 비트 연산은 CPU에서 매우 빠르게 처리할 수 있습니다.간결한 코드: 복잡한 집합 연산을 간결하게 표현할 수 있습니다. 주요 비트 연산자AND ( & ): 두 비트가 모두 1인 경우에만 1을 반환 합니다.OR ( | ): 두 비트 중 하나라도 1인 경우에 1을 반환 합니다.XOR ( ^ ): 두 비트가 서로 다른 경우 1을 반환 합니다.NOT( ~ ): 비트를 반전 시킵니.. React Router Dom에 관하여 오늘은 React Router Dom에 관해서 공부 해볼까 합니다. 이런 라이브러리들을 설치 해서 대충 사용 해도 되지만 더욱더 원리와 구조를 이해하면서 공부를 하고 싶어서 정리를 해보려고 한다. 1. React Router Dom의 기본 개념 React Router Dom은 싱글 페이지 애플리케이션(SPA)에서 다중 페이지 애플리케이션처럼 동작하는 라우팅 시스템을 제공한다사용자가 URL을 변경할 때 페이지를 새로고침하지 않고 컴포넌트를 교체하는 방식이다 Route는 경로를 정하다라는 의미이다.즉 리액트의 경로를 정하는 문서 객체 모델이라는 뜻 임을 알 수 있다. 그럼 문서 객체 모델(DOM)이란 무엇일까? DOM(Document Object Model)웹 문서의 구조화 된 표현프로그래밍 언어가 웹.. 백준 2230) 수 고르기 골드 5 투 포인터 풀이: 가장 중요한 부분은 투 포인터 알고리즘을 활용하여 해결 하는 것입니다. n이 100,000까지니까 시간 복잡도 O(n 제곱)은 당연히 안될꺼라는 것을 아실겁니다. 투 포인터로 빠르고 간단하게 순회하기 위해서 vector에 값을 입력받고 오름차순 정렬 시켜주면 됩니다. 그리고 투 포인터의 while 조건이 중요합니다 -> while(i 당연히 i와 j는 n을 넘어가면 OutOfBounds 뜰 것 입니다. i가 j보다 커지는 것은 마이너스로 가기 때문에 m은 0 이상 값만 들어오니 i가 j를 넘어서는 상황은 고려하지 않습니다 #include #include #include using namespace std;int main() { long long n,m; cin >> n >> m;.. 백준 1038) 감소하는 수 골드 5 - 백트래킹 풀이: 이 문제는 백트래킹을 사용하면 된다고 한다 하지만 이 문제를 읽고 구상을 해보면 뭔가 BFS의 느낌으로 구현하여야 하는데 백트래킹은 DFS의 원리와 비슷하여 어떻게 백트래킹을 사용할 것 인가가 중요한 것 같다. 아래는 간단한 예시이다 보면 0 1 2 4 5 6 7 8 9인 1의 자리를 먼저 탐색하고 -> 10 20 21 ... 그 다음 자릿수로 넘어가야한다 0 1 2 3 4 5 6 7 8 9 0 0 0 0 ... 1 1 1 2 2 3 이 문제를 푸는 핵심 방법은 현재 자릿수에서 가장 큰 감소하는 수를 찾았다면 자릿수를 하나 더.. 백준 3745 ) 오름세 골드 2 LIS(n log n) 풀이: 오름세 문제를 읽어보면 LIS(최장 증가 부분 수열)를 찾는 것이다. 아래가 정의이다 이걸 사람 눈으로만 찾는다고 치자 (1 4 5 3 9 3 8 10) 가 예시라면 늦어도 30초 안에는 찾을 수 있을 것이다하나의 수열을 찾았다면 길이가 최장 수열이 하나가 아닐수도 있으니 하나 더 찾아보도록 바란다;;; 일단 n이 10만까지 들어올 수 있으니 사람 눈으로는 절대 못찾는다LIS는 보통 2가지로 방법으로 찾을 수 있다 실버수준의 O(n * n)의 시간 복잡도와 골드 수준의 O(n log n)가 있다 실버수준이라면 n이 10만인 경우를 하나만 입력받아도 10만 * 10만은 100만은 아니고 100억정도 연산하는거다 당연히 안된다 그래서 골드 수준의 방식을 쓰면 10만 * 로그 10만이라 아래 와 같.. 백준 2610 ) 회의 준비 골드 2 C++ #include #include #include using namespace std; int main() { int n, m; ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> m; vector> dp(n+1, vector(n+1, 100000000)); for (int i = 1; i > x >> y; dp[x][y] = 1; dp[y][x] = 1; } for(int k = 1; k > we(n+1); for (int i = 1; i .. 이전 1 2 3 4 ··· 7 다음
