5 Problem A : 지하철
목적 역까지 가는데 걸리는 최소 시간과 최단 경로를 출력 - 플로이드 와샬 N^3 - 다익스트라 대개 N^2 다익스트라 풀이 - D[] : 시작 점으로 인덱스까지의 최단 거리 저장 배열 - P[] : 값에서 인덱스까지 가는데 최단 거리를 가진 노드 - chk[] : 확정적으로 가장 짧은 거리 1로 변경 #include #define LN 11000 #define MAX 10 int N, M, S[MAX][MAX], D[MAX], P[MAX], chk[MAX]; // S는 입력 받는 행렬, D는 최단 거리 저장, P는 void path(int pos) { if (pos == 0) return; path(P[pos]); printf("%d ", pos); } int main(){ int i, j, k, mi..
2019. 11. 8.
2 Problem E : 구간 성분
두 문자열에서 같은 성분을 가진 구간 중에서 가장 긴 구간을 찾아, 그 구간의 길이를 출력하는 프로그램 - 해싱 - 정적 할당 - 해싱 키 값을 만드는 과정 - 완전 탐색에서, 해싱 키 값을 규칙에 의해서 만들어 냄 #include #include #define MOD 10000 char A[1510], B[1510]; int asum[1510], bsum[1510], alen, blen, bn; struct data { int pos; data *next; data *myAlloc(int _pos, data *_next) { pos = _pos, next = _next; return this; } } *hash[MOD], buf[1510]; void push(int key, int pos) { hash..
2019. 11. 7.
2 Problem D : 키로거(Keylogger)
메모장에서 커서 문제로, >, next = next; next->prev = prev; } } *head, *tail, *cur, buf[1000005]; int bn; void push(char ch) { data *pr = cur->prev; pr->next = cur->prev = buf[bn++].myAlloc(ch, pr, cur); } int main() { int T; scanf("%d", &T); // 테스트케이스 갯수 입력받고 head = buf[0].myAlloc(0, 0, 0); // head 와 tail = buf[1].myAlloc(0, 0, 0); // tail 을 만듬 while (T--) { bn = 2; head->next = tail; // 연결 tail->prev = h..
2019. 11. 7.
2 Problem C : 용액
슬라이딩 윈도우 - 양 쪽에서 하나씩 이동 - 이동하면서 비교하는 과정 와일 문 안에 - break 조건을 넣기 #include int N, arr[100010], ans = 2e9 + 1, ans1, ans2; //입력 받는 배열, int Abs(int x) { return x >= 0 ? x : -x; } // 절대 값 int main() { scanf("%d", &N); for (int i = 0; i < N; i++) scanf("%d", &arr[i]); // 입력을 받고 int l = 0, r = N - 1, tmp; while (l < r) { tmp = arr[l] + arr[r]; if (Abs(tmp) < ans) { // 0과의 거리 이므로, 절대값을 한 후 비교 ans = Abs(t..
2019. 11. 7.
1 Problem B : 못생긴 수
소인수분해 했을 경우 나오는 소인수가 2, 3 그리고 5뿐인 수를 이야기 수열로 늘어 놓으면 1, 2, 3, 4, 5, ,6, 8, 9, 10, 12, ... 정수 n이 주어졌을 때, n번째 못생긴 수를 출력하는 프로그램을 작성하시오 - heap을 만들어서 ugly[cnt] 에 못생긴 수를 저장 - 처음 부터 *2, *3, *5 를 해가며 3개의 숫자를 push - minheap을 사용하여, 가장 작은 수를 pop - 위의 내용 MAXN까지 반복 #include typedef long long LL; LL heap[5000] = { 0, 1 }, ugly[1600], hcnt = 1; // 첫 힙에 0과 1을 넣어둠 void Swap(int x, int y) { LL z = heap[x]; heap[x]..
2019. 11. 7.
