My life story

1. 문제 링크 https://www.acmicpc.net/problem/2699 2699번: 격자점 컨벡스헐 문제 정수좌표를 갖는 점을 격자점이라고 한다. 격자 다각형은 모든 꼭짓점이 격자점으로 이루어진 다각형이다. 만약, 다각형의 두 꼭짓점을 잇는 모든 선분이 다각형 내부(또는 경계)에 있다면 www.acmicpc.net 2. 문제 개요 좌표가 주어지고 컨벡스 헐을 이루는 점의 개수, 좌표(x, y) 순서를 조건에 맞는 순서대로 출력할 것. 조건은 1. 첫 번째 곡짓점은 y좌표가 가장 큰 점이다. 만약, 그러한 점이 2개라면, x가 작은 점이 첫 번째 점이다. 2. 그 다음 점부터는 시계방향 순서이다. 3. 문제 힌트 평소에 알고 있는 컨벡스 헐 알고리즘인 그라함 스캔 알고리즘은 y좌표가 가장 작고 ..

1. 문제 링크 https://www.acmicpc.net/problem/2254 2254번: 감옥 건설 첫째 줄에 N(1≤N≤1,000), Px, Py (-100,000≤Px, Py≤100,000)이 주어진다. 다음 N개의 줄에는 차례로 담 기둥의 좌표가 주어진다. 각각의 좌표는 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 2. 문제 개요 소들의 반란이 있은 뒤, 이 소들은 포로로 잡은 인간들을 감시해야 했다. 소들은 (Px, Py)의 위치에 감옥을 짓고 여러 겹으로 담을 쌓아 포로들이 도망가기 힘들도록 하려고 한다. 감옥은 하나의 점으로 표현된다. 소들은 감옥 주변에 N개의 담 기둥을 세웠다. 각각의 담은 감옥을 완전히 감싸야하고, 담 안에 포함되는 담이 있다면 완전히 ..

C++의 String class에 대해서 분석해본 내용입니다. C++ reference를 참고하였습니다. 1. String의 특성 우선 C++ String class는 STL에 속하지는 않습니다. 그냥 라이브러리에 있는 표준 클래스입니다. String은 연속적인 문자를 담을 수 있고 원소 각각은 char로 되어있습니다. 그리고 Vector와 같이 Random Iterator를 지원한다는 점이 특징입니다. 2.String의 구성 String은 알고리즘에서 막~ 다뤄본 경험이 조금 없어서 중요해 보이는 것이나, 필요에 따라서 하나하나 모두 살펴보겠습니다. 2.1) 생성자 생성자에 관한 설명은 C++ reference에 아주 잘 나와있습니다. (코드 예제도 이번에는 C++ reference에서 가져왔습니다.)..

1. 문제 링크 https://www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다고 가정해도 좋다. x�� www.acmicpc.net 2. 문제 개요 볼록 껍질(Convex hull)을 만드는 최소 점의 개수를 출력하는 프로그램을 작성하시오 3. 문제 힌트 알고리즘을 알고 있어야 한다. 간단히 설명하면, 0번점을 시작으로 2번점이 0->1을 이은 벡터의 시계 반대방향에 있는지, 시계방향에 있는지 구분하는 부분을 작성해야 한다. 다른 블로그에 알고리즘에 대한 설명이 잘 나와있으니까 코드는 아니..

1. 문제 링크 https://www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 2. 문제 개요 상어에는 1에서 M이하의 자연수 번호가 붙어 있고, 모든 번호는 서로 다르다. 상어들은 영역을 사수하기 위해 다른 상어들을 쫓아내려고 하는데, 1의 번호를 가진 상어는 가장 강력해서 나머지 모두를 쫓아낼 수 있다. N*N 크기의 격자 중 M개의 칸에 상어가 한 마리씩 들어 있다. 맨 처음에는 모든 상어가 자신의 위치에 자..

1. 문제 링크 https://www.acmicpc.net/problem/2670 2670번: 연속부분최대곱 N개의 양의 실수가 있을 때, 한 개 이상의 연속된 수들의 곱이 최대가 되는 부분을 찾아, 그 곱을 출력하는 프로그램을 작성하시오. 예를 들어 아래와 같이 8개의 양의 실수가 주어진다면, 색칠된 www.acmicpc.net 2. 문제 개요 N개의 양의 실수가 있을 때, 한 개 이상의 연속된 수들의 곱이 최대가 되는 부분을 찾아 그 곱을 출력하는 프로그램을 작성하시오. 3. 문제 힌트 우선 모두 자기 자신만 곱한 걸 나타내기 위해 초기화는 자기 자신들로 해주자. 곱해 나갈 때, 곱한 결과가 자기 자신보다 크다면 누적하는 그런 형태로 나타내 주자. 음수가 없기 때문에 문제는 없다. 코드를 보는 편이 ..