✏CodingTest-Study

[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	바로가기	기하학

📖 MEMO

1. 탐색 문제에서 상하좌우 이동을 해야 할 경우에는 아래의 방법으로 코드를 짧게 작성할 수 있다.

   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];  
       // 범위 예외 처리  
   }
   

2. 다익스트라 알고리즘에서 메모리 사용을 줄이기 위한 방법으로 우선순위 큐를 활용한다.

   #include <queue>
   priority_queue<pair<int,int>> pq;
   

3. C++에서 endl은 '\n'에 비해 속도가 20배정도 느리다. cin/cout의 경우도 scanf/printf에 비해 느리다.
   입출력이 많고 속도가 중요한 문제라면 C스타일의 입출력 함수를 사용하는 것이 좋다.

   #include <cstdio>
   

   cin/cout을 사용할 경우 다음의 코드를 추가하면 속도가 향상된다.

   ios::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   

4. C++ STL - Pair

   pair<int, int> pos = make_pair(x, y);
   nx = pos.first;
   ny = pos.second;
   

5. CCW - 외적을 이용한다.
   • 외적 : A X B = a * b * sin(a)로 vector A를 기준으로 vector B가 얼마나 회전하려는 성질을 가지고 있는지를 표시한다.

   * 외적 값의 부호  
   1) 양수 - sin값이 양수이므로 선분의 위치가 시계 방향   
   2) 음수 - sin값이 음수이므로 반시계 방향  
   3) 0 - sin값이 0이므로 일직선 
   

6. 비트 연산에서 N자리를 1으로 바꾸고 싶을때

   num = (1 << N) - 1;
   

   N만큼 shift 시킨 후 1을 빼면 N자리 비트를 1로 만들 수 있다.