개발하는 리프터 꽃게맨입니다.

https://powerclabman.tistory.com/90 [C++/이론] 최소 스패닝 트리 : 프림 알고리듬 (Prim Algorithm) 스패닝 트리 임의의 그래프가 있다고 생각해봅시다. 스패닝 트리란 부분 그래프 중 하나로 다음과 같은 조건을 만족해야 합니다. 1) 그래프 내의 모든 정점을 포함하는 부분 그래프 2) 사이클이 powerclabman.tistory.com 개요 크루스칼 알고리즘은 최소 스패닝 트리를 구하기 위한 또 다른 알고리즘입니다. 앞전에 소개한 프림 알고리즘과 차이점은, 프림 알고리즘의 경우 특정 노드에서 출발해 노드들을 탐색하면서 최소 스패닝 트리를 완성시켜나가는 알고리즘이었다면 크루스칼 알고리즘은 모든 경로를 두고, 최소 경로만 쏙쏙 선택해서 트리를 만들어낸다고 보면 되..

스패닝 트리 임의의 그래프가 있다고 생각해봅시다. 스패닝 트리란 부분 그래프 중 하나로 다음과 같은 조건을 만족해야 합니다. 1) 그래프 내의 모든 정점을 포함하는 부분 그래프 2) 사이클이 없는 그래프 이런 그래프를 신장 트리 (혹은 스패닝 트리)라고 합니다. 스패닝 트리를 찾는 것은 매우 단순합니다. 단순 BFS, DFS를 하면 스패닝 트리를 찾을 수 있죠. 그런데 가중치 그래프의 경우를 생각해봅시다. 모든 노드를 다 방문하는데 비용이 다 다르다면, 아무래도 최소 비용으로 방문하는 것이 가장 좋겠죠? 그래서 중요하게 다뤄지는 알고리즘이 최소 신장 트리 (최소 스패닝 트리) 이며, 이는 모든 노드를 방문하는 최소 비용의 신장트리를 찾는 것을 목적으로 합니다. 더보기 최소 비용 경로 알고리즘과 무엇이 다..

이것을 따로 부르는 개념이 있는지는 모르겠지만, 필요해서 연구를 하다보니 꽤나 쓸만한 개념인 것 같아서 포스팅 해봅니다. 대부분의 프로그램이 이런 방식으로 메인 루프가 존재합니다. 예를 들어서 우리가 게임을 만든다고 가정해봅시다. 그럼 플레이어가 화살을 쏜다고 하면 화살을 생성해야할 것 이고, 또 화살이 몬스터에게 닿으면 삭제를 해줘야 할 것 입니다. 그런데, 이런 식으로 루프 중간중간에 막 추가해버리면 코드가 꼬일 수 있습니다. 정확한 예시는 제시하긴 좀 애매하긴한데.. 어쨌든 우리는 함수를 예약해서 지연 처리를 할 필요성이 있다는 겁니다. (좀 엉렁뚱땅 넘어가는 느낌이긴 하지만..) 중간 중간에 특히, 특정 메모리를 추가로 할당하거나 삭제할 때, use-after-free 문제 등이 많이 발생하므로 ..

https://school.programmers.co.kr/learn/courses/30/lessons/42627 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 아이디어 우선순위 큐를 이용한 스케줄링 문제입니다. 큰 아이디어는 이렇습니다. 1) 작업의 길이가 짧은 것을 먼저 해야한다. 2) 1)을 만족해도 요청되는 작업만 수행해야한다. 즉, 이 2가지를 고려해서 해결해야합니다. 풀이이 먼저 1) 이전에 2를 해결하기 위해 jobs를 실행시간 기준으로 오름차순 정렬해줍니다. 그러면 일단 2)를 해결했고, 다음은 1)을 해결해야하는데 현재 jobs 배열..

삼각함수 개요 (Trigonometric Function) 삼각함수는 각의 크기를 삼각비로 나타내는 함수를 합니다. 즉, 삼각형의 각도와 변의 길이의 관계를 다루는 함수라고 생각할 수 있죠. 1. 직각삼각형의 3요소 직각삼각형에는 3개의 요소가 있는데요. 빗변 (hypotenuse) 밑변 (adjacent) 높이 (opposite) 가 있습니다. 2. 삼각비 삼각비란 직각삼각형의 3변 중 2 변의 길이간의 비례 관계를 나타내는 값입니다. 3. 삼각함수 삼각비의 의미를 함수의 개념으로 확장시킨 것을 삼각함수라고 볼 수 있습니다. 여러가지 정의법이 있을 수 있지만, 저는 단위원으로 정의해보겠습니다. 좌표 평면 상에서 원점 O를 중심으로하는 단위원을 고려할 때, 단위원의 한 점 P(x,y) 라하고 원점 O와 ..