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

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와 ..

1. 선형결합 1) 선형결합 (Linear Combination) 선형 결합 (혹은 일차 결합)은 각 항에 상수를 곱하고 결과를 더함으로써 일련의 항으로 구성된 표현식입니다. 이런 식으로 말이죠. 이전 글 '[수학] 벡터'에서 벡터와 스칼라곱의 연산을 다룬적이 있습니다. 임의의 벡터 V를 체 K 위에 정의한다고 하면, 벡터 V의 원소를 v1, v2, v3 ... 스칼라를 a1, a2, a3 ... 로 나타낼 수 있는데, 스칼라 계수와 벡터의 선형결합을 이용해서 새로운 벡터를 만들어 낼 수 있습니다. 이런 식으로 말이죠. 이를 벡터의 선형생성이라고 부릅니다. 수학에서는 span 이라고 표현합니다. 2) 선형독립 실수 n차원 공간에서 정의된 임의의 벡터 V에 대해서 벡터의 방정식이 자명해를 갖고 있을 시에 ..

https://www.acmicpc.net/problem/10158 10158번: 개미 가로 길이가 w이고 세로 길이가 h인 2차원 격자 공간이 있다. 이 격자는 아래 그림처럼 왼쪽 아래가 (0,0)이고 오른쪽 위가 (w,h)이다. 이 공간 안의 좌표 (p,q)에 개미 한 마리가 놓여있다. 개미는 오 www.acmicpc.net 1. 아이디어 첫 번째로 떠올린 아이디어는 '시뮬레이션'이었습니다. 직접 시뮬레이션을 돌려서 문제를 해보고자했죠. 그래서 작성한 코드가 다음과 같습니다. 말그대로 방향을 바꿔가면서 움직여보는 것이였죠. 시간 제한이 0.15초 이고, t가 한 없이 커도 w*h 를 간격으로 똑같은 패턴을 보이기 때문에 나머지를 통해 for문을 돌리면 시간초과가 나오지 않을 것이라 생각했습니다. 하지..

최근에 만들 윈도우 API 프로그램입니다. 방향키를 누르면 사각형이 이동합니다. 그런데 이동을 하면 잔상이 남는 모습을 볼 수 있습니다. 그림을 그리는 것은 모니터의 픽셀 버퍼에 원하는 값을 저장하는 형식으로 진행됩니다. 우리가 이전 버퍼를 지워주지 않았으니 이렇게 잔상이 남는 것이죠. 이런 식으로 매우 큰 흰색 사각형을 그려줘서 지워주는 건 어떨까요? 아마 매우 빠르게 깜빡 깜빡 거릴겁니다. 이게 왜 그렇냐면 그리기 버퍼를 단 1개만 사용해서 그렇습니다. 컴퓨터가 아무리 빨라도 화면에 픽셀을 하나하나 그려서 모두 그리는데 시간이 걸리겠죠? 저 코드를 넣어주면, 컴퓨터가 원하는 그림을 먼저 싹 그린 다음에 흰 색 큰 사각형을 싹 그려주고.. 를 반복합니다. 그러면 깜빡깜빡 거린다는 거죠. 깜빡이는 이유는..

이런 오브젝트가 있다고 해봅시다. 이 오브젝트는 방향키를 누르면 상하좌우로 움직이며 그 값은 0.1 만큼 움직입니다. 그런데 이 코드에는 문제가 있죠. 바로 하드웨어 성능에 따라 초당 이동거리가 다르다는 것입니다. 이게 무슨 의미일까요? 컴퓨터 A는 계산속도가 매우 빨라서 1초에 10000번 계산합니다. 컴퓨터 B는 계산속도가 매우 느려서 1초에 100번 계산합니다. 위 코드에 의하면 컴퓨터 A에서 게임을 실행시 1초에 1000 만큼 이동하고 컴퓨터 B에서는 게임을 실행시 1초에 10 만 이동하죠. 만약, 레이싱 게임이라고 했을때 내 컴퓨터 사양이 구리다는 이유로 매번 경기에서 지면 억울할겁니다. 그렇기에 컴퓨터 사양에 구애받지 않는 상대적인 시간을 얻어야하는데 그것이 바로 델타타임 입니다. 그럼 이는 ..

1. 벡터의 정의 1) 데카르트 좌표계 (Cartesian Coordinate System) 데카르트 좌표계란 임의의 차원의 유클리드 공간을 나타내는 좌표계 중 하나입니다. 유클리드 공간은 평면과 공간을 일반화한 것으로 유클리드가 생각했던 거리, 길이, 각도를 좌표계에 도입하여, 임의 차원 공간으로 확장한 것입니다. 유클리드 공간은 유한 차원, 실수, 내적 공간으로 n차원 유클리드 공간은 실수 집합 R의 n번 곱집합이죠. 간단하게 말해서 2차원 데카르트 좌표계는 2차원 유클리드 공간에서의 좌표 평면 3차원 데카르트 좌표계는 3차원 유클리드 공간에서의 좌표 공간 이라고 할 수 있겠습니다. 이 2차원 데카르트 좌표계는 2개의 실수 집합 R을 곱집합한 원소들의 집합, RxR 로 표현할 수 있고 흔히 가로축을 ..