일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
- c#
- 다이나믹 프로그래밍
- Vector
- 분할축 이론
- GJK
- 벡터
- 충돌 알고리즘
- 우분투
- Expanding Polytope Algorithm
- C++
- 리눅스
- PS
- SOH
- 알고리즘
- linux
- 내적
- 문제풀이
- ubuntu
- 백준
- dp
- C
- 수학
- Graham Scan
- AABB
- uclidean algorithm
- 보로노이다이어그램
- 유니티
- 외적
- Unity
- Doubly Connected Edge List
- Today
- Total
목록C++ (15)
마이 플밍 블로그
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..
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..
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 ..
https://www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 www.acmicpc.net 풀이 가장 큰 정사각형의 크기를 구하면 되기 때문에 순회중인 타일의 위치를 (x, y)라고 하고 정사각형의 변의 길이를 i라고 하면 (x+i, y) (x, y+i) (x+i, y+i) 위치의 타일이 순회중인 타일의 번호가 같으면 넓이 비교를 하면 된다. 코드 #include #include using namespace std; int map[100][100]; int flag[100][100][4..
C++의 STL에는 Vector와 List라는 컨테이너가 있다. 언뜻보기에는 두 컨테이너에는 차이가 없는것 처럼 보이지만 사실 큰 차이점이 있다. 1. Vector Vector 컨테이너는 일반적인 배열처럼 연속적인 메모리 공간에 저장하는 방식. 후에 들어올 요소들을 대비해 미리 예비 공간을 할당함. 배열과 달리 크기의 제한을 받지않음.(32bit 기준으로 10억개 정도는 있긴함) 맨뒤에 추가하는건 빠르지만 중간에 삽입할 시 O(n)만큼의 시간이 걸림. 중간에 삽입시 원소들을 뒤로 밀어냄. [1] 과 같이 랜덤 접근이 가능함. 동적으로 크기가 확장되지만 비용이 큼 2. List List 컨테이너는 더블 링크드 리스트로 구현되어 있음. 값을 추가할 때마다 메모리를 할당함 중간에 있는 특정 원소를 찾기 위해서..
memset 함수는 메모리의 값을 원하는 범위만큼 값을 변경 시켜주는 함수다. 더보기 void* memset(void* ptr, int value, size_t num); 첫번째 ptr은 메모리의 시작 주소 두번째 value는 바꿀 값 세번째 num은 메모리 길이를 뜻한다. 이 길이는 바이트 단위로써 메모리 크기 한조각단위의 길이를 뜻한다. sizeof(타입) 으로 하면 된다. 함수가 제대로 작동하면 맨 처음인자인 ptr이 반환되고 실패하면 NULL을 반환한다. 예제 #include #include using namespace std; int main() { char arr[20]; cin >> arr; memset(arr, 'b', 3 * sizeof(char));; cout
14238번: 출근 기록 스타트링크에는 세명의 직원이 일을 하고 있다. 세 직원의 이름은 강호(A), 준규(B), 수빈(C) 이다. 이 회사의 직원은 특별한 룰을 가지고 있는데, 바로 하루에 한 명만 출근한다는 것이다. 3일간의 www.acmicpc.net 코드 #include #include #include #include #include using namespace std; int workerCount[3]; bool dp[51][51][51][3][3] = { false }; char ans[51]; bool DP(int a, int b, int c, int bbefore, int before) { if (workerCount[0] == a && workerCount[1] == b && worker..