마이 플밍 블로그

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

https://www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범 www.acmicpc.net 문제에선 Convex Hull에 대한 설명을 하는데 Convex Hull이란 가장 바깥쪽에 있는 정점들을 이어서 만드는 볼록 다각형을 뜻한다. 이런 Convex Hull을 만드는 알고리즘 중에서는 Graham's Scan 알고리즘이 있다. 이 문제는 Graham's Scan 알고리즘으로 풀었는데 이 알고리즘에 대해 설명하자면먼제 Convex Hull을 자세히보면 이어진 정점들이..

C++의 STL에는 Vector와 List라는 컨테이너가 있다. 언뜻보기에는 두 컨테이너에는 차이가 없는것 처럼 보이지만 사실 큰 차이점이 있다. 1. Vector Vector 컨테이너는 일반적인 배열처럼 연속적인 메모리 공간에 저장하는 방식. 후에 들어올 요소들을 대비해 미리 예비 공간을 할당함. 배열과 달리 크기의 제한을 받지않음.(32bit 기준으로 10억개 정도는 있긴함) 맨뒤에 추가하는건 빠르지만 중간에 삽입할 시 O(n)만큼의 시간이 걸림. 중간에 삽입시 원소들을 뒤로 밀어냄. [1] 과 같이 랜덤 접근이 가능함. 동적으로 크기가 확장되지만 비용이 큼 2. List List 컨테이너는 더블 링크드 리스트로 구현되어 있음. 값을 추가할 때마다 메모리를 할당함 중간에 있는 특정 원소를 찾기 위해서..

DCEL 이중 연결 가장자리 목록 혹은 half-edge data structure 라고도 불리는 이것은 일반적으로 위처럼 폴리곤이 Face Vertex Edge 3개의 요소로 이루어지는 구조를 뜻하는데 각 요소의 뜻은 다음과 같다. Face - 폴리곤의 내부 Vertex - 폴리곤의 정점 Edge - 폴리곤의 가장자리 DCEL은 위와같은 모습이 되는데 한 폴리곤의 내부가 시계방향 혹은 반시계방향으로 정렬되 있는데 만약 모서리가 면의 경계에 있다면 그 위치에 있는 모서리는 두개이고 각 모서리를 가진 폴리곤의 회전 방향은 정 반대이다. 방향만 다른 같은 모서리가 두개있는 것이 마치 한 모서리를 반으로 가른것 같아서 half-Edge라고도 불리는 것 같다. 폴리곤을 이루는 각 요소는 다음과 같은 데이터를 가..

CCW란? CCW(Counter Clock Wise)는 시계반대 방향이라는 뜻으로 점 A B C가 있다고 했을 때 벡터 AB를 기준했을 때 C가 오른쪽에 있는지 왼쪽에 있는지를 알아내는 방법을 뜻한다. CCW를 구하는 방법은 외적을 통해서 구할 수 있다. 두벡터를 외적하면 새로운 벡터가 생기는데 그 벡터는 두 벡터의 수직인 벡터로 외적을 통해 생성된 벡터의 크기는 두 벡터를 변으로 하는 평행사변형의 크기가 된다. 외적의 값은 오른손 좌표계, 왼손 좌표계를 하느냐에 따라 값이 틀리게 나오는데 오른손 좌표계를 기준으로 값을 구하겠다. 위는 외적의 공식으로 2차원 평면에서 외적을하면 새로 생긴 벡터의 x와 y 값은 0이된다. z는 해당 벡터의 크기가 되고 그 값의 부호에 따라서 CCW를 판별할 수 있다. 선분..

개인적으로 공부한 것을 정리한 글입니다. 틀린내용이 있을 수도 있으니 주의해주세요. 운동량(momentum) - 뉴턴 역학에서 질량과 속도의 곱을 뜻함 운동량을 p 질량을 m 속도를 v라고 하면 위와같이 정의할 수 있다. 충격량(impulse) - 두 물체가 충돌했을 때 운동량의 변화량 운동량 보존 법칙 물체에 외부의 힘이 작용하지 않는다면 그 물체가 가진 총 운동량은 바뀌지 않는다. 서로 다른 두 물체가 충돌하더라도 총 운동량은 변하지 않는다. m이 질량 v가 속도 v^를 충돌 후 속도라고 하면 다음식이 된다. 반발계수 반발 계수는 두 물체가 충돌 전후의 속도 비율을 나타내는 분수로 0과 1사이값이다. e = 1 일시 탄성충돌(에너지 보존) 0 < e < 1 일시 비탄성충돌 e = 0 일시 완전비탄성충..

https://www.acmicpc.net/status?user_id=dkak14&problem_id=14226&from_mine=1 채점 현황 www.acmicpc.net 코드 #include #include #include using namespace std; int S; int IMT[1003][1003]; int answer = 98765432; void CalIMT(int imtnum, int clipboard, int count) { if (answer S) return; if (IMT[imtnum][clipboard] S; memset(IMT, 5, sizeof(IMT)); CalIMT(1, 0, 0); cout

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