마이 플밍 블로그

1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 풀이 평범하게 모든타일에서 시작해서 탐색하면 시간초과에 걸린다. 메모이제이션을 이용하면 쉽게 통과할 수 있다. 코드 #include using namespace std; int board[501][501]; int dp[501][501]; int dx[4] = {0,0,-1,1}; int dy[4] = {1,-1,0,0}; int answer = 0; int n; bool InMap(int x, int y){ if( 0 n; priority_queue..

개요 컴퓨터와 관련된 일을 하다보면 리눅스와 우분투라는 말을 많이 들어보았을 것이다. 많은 사람들이 쓰는 것 같지만 뭔지 잘 몰라서 리눅스와 우분투에 대하여 이번시간에 한번 정리해 보았다. Linux란 무엇인가? Linux는 리누스 토르발스가 커뮤니티 주체로 개발한 Unix 기반의 컴퓨터 운영체제, 혹은 커널을 말한다. Window나 Mac 같이 잘 정의되어진 운영체제가 아니고 커스터마이징 가능한 오픈소스 OS를 만들 수 있는 커널에 가깝다. Linux는 유닉스 기반의 무료 오픈 소스 운영체제라 커널을 통해 사용자가 직접 커스터마이징이 가능하다. 무료이기에 다운하고 수정하여 수정판을 배포할 수 있고 다른 사람들이 공유한 다른 배포판을 사용할 수도있다. Linux커널은 사용자를 위한 운영체제 역할을 하는 ..

11780번: 플로이드 2 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 풀이 플로이드-워셜 알고리즘에서 경로추적을 추가하면 되는 문제다. 문제는 쉬웠으나 못가는 경우 0을 출력하는걸 깜빡해서 여러번 틀렸다. 코드 #include #include using namespace std; #define CITY 105 #define INF 200000000 int map[CITY][CITY]; int nextNode[CITY][CITY]; int n, m; void FloydWarshall(){ for(int i = 1; i n >> m..

아래 링크는 GJK 알고리즘에 대한 설명이다. GJK 알고리즘을 잘 모르면 읽어보길 바란다. 충돌 알고리즘(collision detection algorithms) 충돌 알고리즘인 AABB, OBB, GJK 알고리즘에 대한 설명 www.slideshare.net EPA(Expanding Polytope Algorithm)의 필요성 GJK 알고리즘으로 우린 도형이 충돌판정을 알 수 있다. 하지만 말그대로 충돌을 했냐 안했냐만 알 수 있기 때문에 이것만 가지고선 제대로된 게임을 만들 수 없다. 그래서 우린 EPA를 통해서 충돌한 Edge 방향을 가리키는 노멀인 Contact Normal과 얼마나 깊게 충돌했는지 알수 있는 충돌 깊이 값인 Depth를 알아내어야 한다. GJK에서는 민코스키 차가 원점을 포함하..

작은 컨퍼런스에서 발표할때 쓴 AABB OBB GJK에 대한 설명이다. 원래 티스토리에 다시 쓸려고 했는데 귀찮아서 그냥 파일만 올린다. https://www.slideshare.net/ssuserbe87d6/collision-detection-algorithms?qid=d75a9483-0b7a-454a-8797-d3b24c6c4deb&v=&b=&from_search=3 충돌 알고리즘(collision detection algorithms) 충돌 알고리즘인 AABB, OBB, GJK 알고리즘에 대한 설명 www.slideshare.net

보통 가장 간단한 모든 약수를 구하는 알고리즘하면 1부터 N까지 반복문을 돌려 N % i == 0 일경우 약수로 하는 알고리즘을 생각할 것이다. 이경우 시간 복잡도는 O(N)이 되는데 O(√N) 으로 줄일 수있다. 방법은 간단하다. N의 약수들 중 √N 이하의 것들을 구하고 그 것들을 N에 나누면 다른 약수들도 구할 수있다. 예를 들어서 111의 약수를 구할 때 √110 이하의 약수들은 1, 2, 5, 10 이고 이 것들을 110에 나누면 11, 22, 55, 110 이 나온다. #include #include #include using namespace std; vector vec; int main() { int n = 110; // sqrt를 안쓰고 i * i를 이용함 for (int i = 1; i..

1. 유클리드 알고리즘(Euclidean algorithm) 두 자연수의 최대 공약수(greatest common divisor)를 찾는 알고리즘을 뜻한다. 2. 유클리드 알고리즘 원리 두수 A와 B(A>B)가 있고 A를 B로 나누었을때 나머지가 C일 때 C가 0일경우 B가 최대 공약수이고 아닐경우 A = B 로 B = A % B로 하고 반복해서 C가 0일 될때까지 하면 된다. ex) GCD(12, 8) -> GCD(8, 4) -> GCD(4, 0) 최소공배수 = 4 장점 최대공약수를 구하는 방법중 가장 간단한 방법인 1부터 min(A,B)까지 순서대로 찾는 방법의 시간 복잡도는 O(N)이지만 유클리드 호제법을 이용할 경우 O(Log N)으로 줄일 수 있다. 3. 구현(C/C++) 반복문을 통한 GCD ..

GC란? 다들 알다시피 C#은 C나 C++과 달리 직접 메모리 해제를 할 필요가 없다. 이렇게 할 수 있는 이유로는 Garbage Collector라는 것이 있기 때문인데 이것은 CLR(Common Language Runtime, 공용 언어 런타임)에서 자동메모리 관리기능을 한다. GC덕에 우리는 메모리 관리 부담을 덜하면서 개발할 수 있다. 1. CLR의 메모리 할당 C#에서의 할당을 보자면 소스코드 컴파일 후 실행하면 CLR에선 일정 크기의 메모리를 확보하게된다. 이렇게 관리되는 Heap 메모리 영역을 Managed Heap라고 한다. 이렇게 확보한 Managed Heap의 첫번째 주소에 다음 객체를 할당할 메모리 주소를 메모리의 포인터로 가리킨다. 객체를 생성하게 된다면 포인터가 가리키고 있는 주소..