너와 나의 스토리

문제: programmers.co.kr/learn/challenges?selected_part_id=9317 문제 풀이: Point 1. "응답 완료 시간S는 작년 추석인 2016년 9월 15일만 포함" 즉, 날짜는 크게 신경 쓰지 않아도 된다. Point 2. 각 날짜 및 시간을 ms 단위로 변경하자 = (시간*$60^2$ + 분*60 + 초)*1000 + 소수점 이하 예: 01:00:04.002s -> 3604002ms Point 3. 처리 시작 시간 구하기 입력은 "2016-09-15 01:00:04.001 2.0s" 형태로 주어진다. 먼저 응답 완료 시간(S)을 [Point 2]와 같이 변경한다. 처리 시간(T)도 이와 같이 변경해준다. 이때, 처리 시간의 형태는 다양할 수 있으므로 주의해야 한다..

Summary Class P: 해당 문제를 다항 시간에 해결할 수 있는 알고리즘이 존재하는 decision problems의 집합 Class NP: 해당 문제를 해결하는 Non-deterministic 다항 시간 알고리즘이 존재하는 문제. 어떤 certificate를 다항시간에 verification할 수 있으면, 그 문제는 class NP에 속함 Class P The set of decision problems that are polynomially bounded 해당 문제(P)를 다항시간에 해결할 수 있는 알고리즘이 존재하는 decision problems의 집합 다항 시간: 시간 복잡도가 $O(n^k)$, k가 상수 결정론적 튜링 기계에 사용한 프로그램을 비결정론적 튜링 기계에 적용할 수 있으므로,..

Background binary tree / binary search tree -> data structure binary search tree는 순서 조건 만족해야 함 binary search -> algorithm Binary Search Tree property Binary search tree를 inorder traversal(왼쪽부터 탐색)하면 결과적으로 오름차순으로 정렬됨 balanced tree일 경우 어떤 데이터를 찾을 때 O(log n) 시간이 걸린다. 하지만 long chain tree 구조이면, 어떤 데이터를 찾을 때 O(n) 시간이 걸린다. -> 한 방향으로 쭉 늘어진 형태 Binary Tree Rotations 기술을 사용해서 트리를 균형 있게 만들 수 있다 ex) AVL tree..

Array doubling 사이즈가 n인 배열 A가 있다고 하자. A가 꽉 찼을 때, push가 들어온다면 사이즈가 두 배인(2n) 배열 B를 만들어, 배열 A에 있는 것들을 옮기고, 새로운 데이터를 push한다. 이때, (n*t+1)만큼의 연산을 한다. t: A에서 B로 데이터를 하나 옮기는데 드는 시간 1: 새로 들어온 데이터는 처음부터 B로 들어감 그렇다면, push 연산의 시간 복잡도는 O(n)이다. 하지만, doubling은 가끔씩만 발생하는데 O(n)으로 취급하기는 아깝다 ㅠㅠ -> Amortized Analysis를 하자! Amortized Analysis worst case 분석 연속해서 연산이 발생할 때, 최악의 경우의 평균 연산을 고려한다. Average Analysis와의 차이 Ave..

문제: https://www.acmicpc.net/problem/1865 소스 코드: #include #include #include #include #include #include #include #define inf 987654321 using namespace std; typedef pair P; vector adj; int tc, n, m, wf, dist[501]; int main() { ios::sync_with_stdio(false); cin.tie(NULL), cout.tie(NULL); cin >> tc; while (tc--) { cin >> n >> m >> wf; bool chk = false; adj.clear(); adj.resize(n + 2); fill(dist, dist +..

문제: https://swexpertacademy.com/main/solvingProblem/solvingProblem.do 소스 코드: #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include #include #include #include #include #include using namespace std; int tc, n, m; int dx[4] = { -1,0,1,0 }; int dy[4] = { 0,1,0,-1 }; char arr[22][22]; bool visit[22][22][4][17]; struct state { int curx; int cury; int dir; int memory; };..

문제: https://swexpertacademy.com/main/solvingProblem/solvingProblem.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 소스코드: #include #include #include #include #include #include using namespace std; int tc, n,mi, dist[51][51], arr[51][51],res; typedef pair P; int dx[4] = { -1,0,1,0 }; int dy[4] = { 0,1,0,-1 }; vector adj; queue q; int dfs(int curx,int cury) { if (..

문제: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AXDNGXlKagUDFAVX&categoryId=AXDNGXlKagUDFAVX&categoryType=CODE 문제 풀이: 1 ≤ i < K인 i에 대해 $a_i < a_{i+1}$ 이면서, $a_i$이 $a_{i+1}$의 약수여야 한다. $a_0$, $a_1$, $a_2$가 위 조건을 만족한다면, $a_0$*k=$a_1$ $a_0$*r=$a_2$ 이다. 즉, $a_0$를 포함하려면, 각 값들은 $a_0$의 배수인 것! for문을 돌면서, 현재 arr [i] 값을 약수로 두는 값을 찾기 위해, $a_0$*2, $a_0$*3, $a_0$*4 해가며 해당 위치에서..