너와 나의 스토리

문제: https://www.acmicpc.net/problem/1708 문제 풀이: Convex Hull 알고리즘 중 Graham's Scan 방법을 이용하여 풀었다. (다른 방법으로는 monotone chain convex hull 방법이 있다) 입력 받은 좌표 중 가장 작은 y값을 가진 점 중 가장 작은 x값을 가진 점을 기준점으로 삼는다. 그 기준점과 모든 점과의 기울기를 기준으로 좌표를 정렬한다. 기울기가 작은 점들부터 비교 연산을 시작한다. 처음에 벡터(나는 벡터를 스택처럼 사용)에 기준점과 기울기가 가장 작은 점, 두 점을 백터에 넣는다. 그 후 인덱스(idx)를 증가시켜가며 현재 벡터의 top에 있는 2점을 기준으로 ccw가 양수이면 해당 좌표의 인덱스를 벡터에 넣고 idx++ ccw가 음..

문제: https://www.acmicpc.net/problem/2162 문제 풀이: 두 선분을 뽑아 만나는지 확인한다 선분1에서 선분2의 한 점과의 ccw, 다른 점과의 ccw가 둘 다 0이고 반대의 경우도 다 0이면 두 선분이 일직선 상에 존재한다는 말이므로 따로 if문을 만들어서 겹치는지 확인해준다 다 0이 아니라면 선분1에서 선분2로의 ccw곱이 음수이고, 선분2에서 선분1로의 ccw곱도 음수이면 둘은 겹친다고 볼 수 있다. 겹친다면 union find 알고리즘을 이용해서 연결 시켜준다. 각 그룹에 속하는 선분의 개수를 알기 위해 루트에 새로운 선분 그룹을 연결할 때, 그 인원수를 루트 부모 변수에 더해준다. 즉, 부모를 기록하는 변수인 p를 처음에 -1로 초기화하고 다른 선분이 추가되면 -2, ..

문제: https://acmicpc.net/problem/2166 문제 풀이: 한 점을 잡고 두 점씩 뽑아 (ccw 값/2)를 해준다. * ccw 값: 두 변을 기준으로한 평행사변형의 넓이 빨간 원이 기준 소스 코드: typedef pair P; vector v; long double res; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; while (n--) { long double x, y; cin >> x >> y; v.push_back({ x,y }); } long double ax = v[0].first; long double ay = v[0].second; for (int i = ..

문제: https://www.acmicpc.net/problem/9202 문제 설명: 상하좌우, 대각선 총 8개의 방향으로 이어지는 단어가 사전에 존재하는 단어를 찾아 해당 단어의 길이별로 점수를 매긴다 각 단어에 속하는 글자 수 1,2 글자 -> 점수는 0점, but 찾은 단어로 카운트는 해야함 3,4 글자 -> 점수: 1점 5 글자 -> 점수: 2점 6 글자 -> 점수: 3점 7글자 -> 점수: 5점 8글자 -> 점수: 11점 문제 풀이: 1. 사전에 들어있는 단어를 입력 받을 때, trie에 삽입한다. boggle 보드에서 abcdef라는 조합이 가능하고 사전에 abcd와 abcde라는 단어가 있을 때 우리는 두 단어 모둘 카운트를 해야한다. 그러므로 트라이에 해당 위치에서 자식이 있는지를 판별하는..

문제: https://www.acmicpc.net/problem/5670 Ries님의 블로그를 참고하여 문제를 풀었다 마지막에 생성한 trie를 할당 해제(delete root)를 안해줘서 메모리 초과가 났다 ㅠㅠ 입력 받을 때, while (scanf("%d", &n))로만 하면 출력 초과가 난다. -> while (scanf("%d", &n)>0)로 바꿔주면 됨 소스 코드: ...더보기 #define _CRT_SECURE_NO_WARNINGS #include using namespace std; int n; struct trie { trie* next[26]; int word, branch; trie() { fill(next, next + 26, nullptr); word = branch = 0; }..

문제: https://www.acmicpc.net/problem/14425 문제 설명: 1. n과 m을 입력 받음 2. n개의 문자열을 입력 받음(형광펜) -> 집합 S 3. m개의 문자열을 입력 받음 이 때 입력 받은 문자열이 집합 S에 있으면 cnt++ * baekjoon은 집합 S에 포함되는거 아님 baekjoononlinejudge처럼 완전히 일치하는 것만 포함되는 걸로 취급 문제 풀이: Trie 메모리 제한이 1536 MB로 넉넉하므로 trie로 풀어보았다. insert함수로 trie를 만들고 check함수로 포함되는지 확인 했다. check함수에서 현재 문자열이 새로운 길로 가려고 하면 S에 포함되지 않는 것이므로 -> false 리턴 현재 문자열을 끝까지 다 봤고 S에 속하는 문자열도 이 곳..

문제: https://www.acmicpc.net/problem/9934 문제 풀이: 위에서부터 왼쪽에서 오른쪽으로 1번부터 순서를 매긴다고 하자. 깊이가 k일 때, 마지막 레벨의 번호는 $2^{k-1}$≤N≤$2^{k}-1$이다. l: $2^{k-1}$ r: $2^{k}-1$ pos: 1 (도착 순서) 이라고 하자. 1. 왼쪽 노드를 방문 안했고 현재 l보다 작다면(아직 마지막 층이 아니라면) -> 왼쪽 노드로 이동 2. 왼쪽 노드를 방문 했고 현재 자신의 위치에서 방문한 적이 없으면 -> 입력 받은 순서대로 트리의 해당 위치에 값을 넣어준다. 3. 현재 위치를 방문했고, 오른쪽 노드는 방문 하지 않았는데 현재 l보다 작다면 -> 오른쪽 노드로 이동 소스 코드: int h,l,r,arr[1026],re..

문제: https://www.acmicpc.net/problem/3830 문제 풀이: 1. 입력 받은 샘플에 상대적인 무게를 지정해준다. (그룹별로) 2. 두 그룹이 합쳐지는 경우 사이즈가 작은 그룹을 큰 그룹에 포함되도록 만든다 큰 그룹의 끝에서 작은 그룹으로 dfs를 돌려서 큰 그룹의 번호와 큰 그룹의 상대적인 무게에 맞는 무게를 부여 이미 존재하는 그룹에 새로 연결하는 경우는 그냥 상수시간으로 해결 가능하고, 두 그룹 묶을 때, 작은 그룹만 dfs 돌리니까 최악의 연산은 전체 dfs 한 번 돌리는 정도가 된다. * 주의: 무게 저장할 때, long long 써야하는데, 이것만 long long으로 하는 것이 아니라 이 것과 관련된 변수들도 다 long long으로 해줘야 한다. 소스 코드: type..