[2021.12.29 ~ ]
코딩 테스트 준비 및 알고리즘 공부를 위한 저장소 입니다.
| 문제 유형 | 순번 | 문제 번호 | 문제 이름 | 풀이 날짜 | 코드 |
|---|---|---|---|---|---|
| Brute Force | 1 | 10819 | 차이를 최대로 | 2021.12.29 | 바로가기 |
| 2 | 2661 | 좋은수열 | 2021.01.13 | 바로가기 | |
| 3 | 1007 | 벡터 매칭 | 2021.01.18 | 바로가기 | |
| 4 | 1339 | 단어 수학 | 2021.01.25 | 바로가기 | |
| 5 | 9663 | N-Queen | 2021.02.07 | 바로가기 | |
| DFS | 1 | 2667 | 단지번호붙이기 | 2022.01.03 | 바로가기 |
| 2 | 2468 | 안전영역 | 2022.01.13 | 바로가기 | |
| 3 | 9466 | 텀 프로젝트 | 2022.01.20 | 바로가기 | |
| 4 | 1987 | 알파벳 | 2022.01.22 | 바로가기 | |
| 5 | 2239 | 스도쿠 | 2022.01.23 | 바로가기 | |
| BFS | 1 | 2178 | 미로 탐색 | 2022.01.04 | 바로가기 |
| 2 | 14502 | 연구소 | 2022.01.13 | 바로가기 | |
| 3 | 3197 | 백조의 호수 | 2022.01.28 | 바로가기 | |
| 4 | 2933 | 미네랄 | 2022.01.30 | 바로가기 | |
| 5 | 6087 | 레이저 통신 | 2022.01.31 | 바로가기 | |
| Dynamic Programming | 1 | 1463 | 1로 만들기 | 2022.01.04 | 바로가기 |
| 2 | 2293 | 동전 1 | 2022.01.12 | 바로가기 | |
| 3 | 2098 | 외판원 순회 | 2022.01.15 | 바로가기 | |
| 4 | 12852 | 1로 만들기 2 | 2022.01.16 | 바로가기 | |
| 5 | 10942 | 팰린드롬? | 2022.01.17 | 바로가기 | |
| 6 | 9252 | LCS 2 | 2022.01.18 | 바로가기 | |
| 7 | 7579 | 앱 | 2022.01.19 | 바로가기 | |
| 8 | 2533 | 사회망 서비스(SNS) | 2022.01.26 | 바로가기 | |
| 9 | 12865 | 평범한 배낭 | 2022.01.27 | 바로가기 | |
| 10 | 11066 | 파일 합치기 | 2022.01.31 | 바로가기 | |
| 11 | 5582 | 공통 부분 문자열 | 2022.02.02 | 바로가기 | |
| Dijkstra | 1 | 1753 | 최단경로 | 2022.01.05 | 바로가기 |
| 2 | 16118 | 달빛 여우 | 2022.01.14 | 바로가기 | |
| Floyd Warshall | 1 | 11404 | 플로이드 | 2022.01.12 | 바로가기 |
| 2 | 2458 | 키 순서 | 2022.01.14 | 바로가기 | |
| Binary Search | 1 | 10815 | 숫자 카드 | 2022.01.11 | 바로가기 |
| 2 | 14003 | 가장 긴 증가하는 부분 수열 5 | 2022.02.03 | 바로가기 | |
| 3 | 12738 | 가장 긴 증가하는 부분 수열 3 | 2022.02.03 | 바로가기 | |
| Topology Sort | 1 | 2252 | 줄 세우기 | 2022.01.12 | 바로가기 |
| 2 | 1516 | 게임 개발 | 2022.01.13 | 바로가기 | |
| 3 | 2623 | 음악프로그램 | 2022.01.16 | 바로가기 | |
| 4 | 1005 | ACM Craft | 2022.01.24 | 바로가기 | |
| 5 | 1766 | 문제집 | 2022.02.28 | 바로가기 |
| 순번 | 문제 번호 | 문제 이름 | 풀이 날짜 | 코드 | 메모 |
|---|---|---|---|---|---|
| 1 | 1644 | 소수의 연속합 | 2021.01.15 | 바로가기 | 에라토스테네스의 체, 투 포인터 |
| 2 | 2166 | 다각형의 면적 | 2021.01.16 | 바로가기 | 기하학, 다각형의 넓이 |
| 3 | 1197 | 최소 스패닝 트리 | 2021.01.17 | 바로가기 | 최소 스패닝 트리 |
| 4 | 2467 | 용액 | 2021.01.17 | 바로가기 | 투 포인터 |
| 5 | 9527 | 1의 개수 세기 | 2021.01.18 | 바로가기 | 수학, 누적 합, 비트마스킹 |
| 6 | 1647 | 도시 분할 계획 | 2021.01.21 | 바로가기 | 최소 스패닝 트리 |
| 7 | 2473 | 세 용액 | 2021.01.24 | 바로가기 | 두 포인터 |
| 8 | 1655 | 가운데를 말해요 | 2021.01.27 | 바로가기 | 우선순위 큐 |
| 9 | 11401 | 이항 계수 3 | 2021.01.29 | 바로가기 | 페르마의 소정리, 분할 정복 |
| 10 | 2749 | 피보나치 수 3 | 2021.01.29 | 바로가기 | 피사노 주기 |
| 11 | 10830 | 행렬 제곱 | 2021.01.30 | 바로가기 | 행렬, 분할 정복 |
| 12 | 11758 | CCW | 2021.02.01 | 바로가기 | 기하학 |
- 탐색 문제에서 상하좌우 이동을 해야 할 경우에는 아래의 방법으로 코드를 짧게 작성할 수 있다.
int dx = {-1, 0, 1, 0}; int dy = {0, -1, 0, 1}; for(int i = 0; i < 4; i++){ int nx = x + dx[i]; int ny = y + dy[i]; // 범위 예외 처리 } - 다익스트라 알고리즘에서 메모리 사용을 줄이기 위한 방법으로 우선순위 큐를 활용한다.
#include <queue> priority_queue<pair<int,int>> pq; - C++에서 endl은 '\n'에 비해 속도가 20배정도 느리다. cin/cout의 경우도 scanf/printf에 비해 느리다.
입출력이 많고 속도가 중요한 문제라면 C스타일의 입출력 함수를 사용하는 것이 좋다.cin/cout을 사용할 경우 다음의 코드를 추가하면 속도가 향상된다.#include <cstdio>ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); - C++ STL - Pair
pair<int, int> pos = make_pair(x, y); nx = pos.first; ny = pos.second; - CCW - 외적을 이용한다.
- 외적 : A X B = a * b * sin(a)로 vector A를 기준으로 vector B가 얼마나 회전하려는 성질을 가지고 있는지를 표시한다.
* 외적 값의 부호 1) 양수 - sin값이 양수이므로 선분의 위치가 시계 방향 2) 음수 - sin값이 음수이므로 반시계 방향 3) 0 - sin값이 0이므로 일직선 - 비트 연산에서 N자리를 1으로 바꾸고 싶을때
N만큼 shift 시킨 후 1을 빼면 N자리 비트를 1로 만들 수 있다.
num = (1 << N) - 1;