공부/백준 2020년 1~2월 알고리즘

11번째 수업

이 글들은 백준 온라인 저지의 백준님이 2020년 1~2월에 강의하시는 강의 내용을 듣고 복습한 뒤 간단하게 정리하여 올리는 글이다. 이 글을 쓰는 이유는 그날그날 들은 강의 내용을 복습하고 정리함으로써 배운 것을 확실히 머리에 남김과 동시에 나중에 다시 상기시킬 때 도움이 되도록 하기 위함이다. ○ 쿼리문제 △ 팰린드롬? 선처리: preprocessing 다이나믹에서는 미리 답을 다 확인해놓고 O(N^2) 답을 그냥 0 또는 1로 출력 O(1) 쿼리는 M개, 1번씩 다 돔. 총 O(N^2+M)의 시간복잡도 △ 1,2,3,더하기 4 구성이 같은데 순서가 다르면 같은 것으로 친다. 예) 1+1+2 = 1+2+1 = 2+1+1 각각의 그룹마다 대표를 하나 결정한다. 순서가 오름차순인 것만 대표로 친다고 하면..

10번째 수업

이 글들은 백준 온라인 저지의 백준님이 2020년 1~2월에 강의하시는 강의 내용을 듣고 복습한 뒤 간단하게 정리하여 올리는 글이다. 이 글을 쓰는 이유는 그날그날 들은 강의 내용을 복습하고 정리함으로써 배운 것을 확실히 머리에 남김과 동시에 나중에 다시 상기시킬 때 도움이 되도록 하기 위함이다. ● 수학 2 ○ 행렬 두 행렬을 더하는 데 걸리는 시간 : O(NM) 두 행렬이 NxM, MxK일때 C[i][j] = ∑A[i][k]*A[k][j] 두 행렬을 곱하는 데 걸리는 시간 : O(NMK) O(N^3)인데 1초안에 수행하려면 N≤500이어야 한다. 행렬 제곱 행렬 A^B제곱 곱셈의 횟수 = O(logB) A^B = AxAxAxAx...xAxA (B번) 곱셈 한번 하는데 걸리는 시간 = N^3 총 시간복..

9번째 수업

이 글들은 백준 온라인 저지의 백준님이 2020년 1~2월에 강의하시는 강의 내용을 듣고 복습한 뒤 간단하게 정리하여 올리는 글이다. 이 글을 쓰는 이유는 그날그날 들은 강의 내용을 복습하고 정리함으로써 배운 것을 확실히 머리에 남김과 동시에 나중에 다시 상기시킬 때 도움이 되도록 하기 위함이다. ● 분할정복 (Divide & Conquer) 어떤 문제가 있을 때, 문제를 나눠서 나눈 문제를 풀고, 푼 결과를 이용해서 우너래 문제를 푼다. 다이나믹과의 차이점 : 다이나믹은 작게 나눈 문제가 중복이 된다. 그래서 중복을 없애기 위해 배열을 사용해 값을 저장한다.(메모이제이션) 그러나 분할정복은 중복이 발생하지 않는다. § 대표적인 분할정복 알고리즘 Binary Search 퀵 소트 머지 소트 큰 수 곱셈 ..

8번째 수업

이 글들은 백준 온라인 저지의 백준님이 2020년 1~2월에 강의하시는 강의 내용을 듣고 복습한 뒤 간단하게 정리하여 올리는 글이다. 이 글을 쓰는 이유는 그날그날 들은 강의 내용을 복습하고 정리함으로써 배운 것을 확실히 머리에 남김과 동시에 나중에 다시 상기시킬 때 도움이 되도록 하기 위함이다. △ 파이프 옮기기 사실 다이나믹 문제인데 방법의 수가 100만 가지라 브루트포스로 풀어도 된다. 방법1 : 양쪽 끝점을 기록하는 방법 (r1, c1) (r2, c2) 방법2 : 한쪽끝과 방향을 저장하는 방법 (r, c), 방향 이 문제에서는 방향이 상당히 중요하기 때문에 2번 방법이 더 좋다. 한쪽 점과 방향을 알고 다른 끝점을 아는 것보다 양 끝점을 알고 방향을 계산하는게 더 오래걸린다. 이동방향 쪽에 있는 ..

7번째 수업

이 글들은 백준 온라인 저지의 백준님이 2020년 1~2월에 강의하시는 강의 내용을 듣고 복습한 뒤 간단하게 정리하여 올리는 글이다. 이 글을 쓰는 이유는 그날그날 들은 강의 내용을 복습하고 정리함으로써 배운 것을 확실히 머리에 남김과 동시에 나중에 다시 상기시킬 때 도움이 되도록 하기 위함이다. ● 그리디 알고리즘 (저번 시간에 이어서~) △ 보석 도둑 ★ 냅색문제 Knapsack N개의 물건이 있고 각각 무게와 가치가 있을때, 가방의 무게에 제한이 있을 때 담을 수 있는 가치의 최대값을 구하는 문제 브루트포스로 풀면 시간복잡도 O(2^N) 다이나믹 프로그래밍으로도 풀 수 있다. D[i][j]: i번째 물건까지 들어있고, 가방의 무게가 j일 때 최대 가치 i번째 물건을 가방에 넣을 수도 있고 안 넣을 ..

6번째 수업

이 글들은 백준 온라인 저지의 백준님이 2020년 1~2월에 강의하시는 강의 내용을 듣고 복습한 뒤 간단하게 정리하여 올리는 글이다. 이 글을 쓰는 이유는 그날그날 들은 강의 내용을 복습하고 정리함으로써 배운 것을 확실히 머리에 남김과 동시에 나중에 다시 상기시킬 때 도움이 되도록 하기 위함이다. ● 문자열 알고리즘 § 문자열 검색 알고리즘 - 문자열 S에서 어떤 문자열 패턴 P를 찾는 알고리즘 모든 문자열을 검사하는 방법이 있다. 시간복잡도. S의 모든 길이마다 P의 길이만큼 검사해야 하므로 O(|S|x|P|) § 라빈 카프 알고리즘 Hash를 이용하는 방법 문자열을 정수로 바꾸는 방법 문자열은 비교하는데 문자열의 길이만큼 시간이 걸리는 반면에 정수는 크고 작음을 비교하는데 걸리는 시간이 O(1)이다...

5번째 수업

이 글들은 백준 온라인 저지의 백준님이 2020년 1~2월에 강의하시는 강의 내용을 듣고 복습한 뒤 간단하게 정리하여 올리는 글이다. 이 글을 쓰는 이유는 그날그날 들은 강의 내용을 복습하고 정리함으로써 배운 것을 확실히 머리에 남김과 동시에 나중에 다시 상기시킬 때 도움이 되도록 하기 위함이다. ● DFS 깊이 우선 탐색 스택을 이용해서 갈 수 있는 만큼 최대한 많이 가고 갈 수 없으면 이전 정점으로 돌아간다. 정해진 순서는 없다. 재귀함수를 이용하면 스택을 이용하지 않아도 된다. 인접행렬 사용시, 시간복잡도는 모든 정점 방문 & 하나 방문시 모든 정점과 연결 여부 검사 즉, O(V^2) = 모든 정점 방문(V) * V번 검사 인접 리스트로 구현시, 연결된 정점만 검사하기 때문에 차수를 모두 더한 것과..

4번째 수업

이 글들은 백준 온라인 저지의 백준님이 2020년 1~2월에 강의하시는 강의 내용을 듣고 복습한 뒤 간단하게 정리하여 올리는 글이다. 이 글을 쓰는 이유는 그날그날 들은 강의 내용을 복습하고 정리함으로써 배운 것을 확실히 머리에 남김과 동시에 나중에 다시 상기시킬 때 도움이 되도록 하기 위함이다. ● 브루트포스 - 백트래킹 백트래킹은 브루트포스의 유형 중 하나다. 브루트포스가 모든 방법을 다 시도하는 것이라면 백트래킹은답의 가능성이 없으면 더이상 호출하지 않고 잘라버리는 것(커팅)이다. △ 문제 - 부등호 문제 : 부등호 기호 가 나열된 수열 A가 있다. 기호의 앞 뒤에 한자리 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 이때, 선택된 수는 모두 달라야한다. k개의 부등호 관계를 모두 만족시키는..