비밀일기

섹션 9동적 계획법(DP, 다이나믹 프로그램)복잡한 문제를 여러개의 간단한 문제로 분리하여 해결하는 것 point..큰 문제를 작은 문제로 나눌 수 있어야함작은 문제들의 결과값이 항상 같아야함작은 문제들을 최초의 한번만 계산하고 DP 테이블에 저장다시 같은 작은 문제가 발생했을 때 다시 계산하는 것이 아니라 테이블에 저장 된 값을 활용 ex(피보나치 수열) a(n+3)=a(n+1)+a(n+2)수열을 구하기 위해 모든 값을 계산하는게 아니라 점화식을 이용하여 계산함동적 계획법으로 풀이할 수 있는가?== 작은 문제로 나눌 수 있나? 값이 항상 같은가? 6번째 피보나치 수열의 값은 5번쨰 피보나치 수열의 값+4번쨰 피보나치 수열의 값수열의 값은 항상 같음 동적 계획법으로 풀이 가능하고 수열의 값은 항상 같은 ..

조합조합 자체로 코딩테스트에 많이 등장함점화식, 동적 계획법을 이해하는데 기초가 되는 내용임 순열: n개의 숫자에서 r개를 뽑아 나열하는 경우의 .조합: 순열과 다르게 순서를 고려하지 않음. 분모에 추가된 r!부분은 순서를 제거하는 역할.  조합의 점화식1. 특정 문제 가정    5개중에 3개 선택2. 모든 부분 문제가 해결된 상황이라 가정하고 지금 문제 생각    5를 선택했을 때->앞에서 2개의 수가 선택된 상황 4C2    5를 선택하지 않음-> 앞에서 3개의 수가 선택된 상황 4C3        따라서 5C3 = 4C3+4C23. 일반화 점화식 도출  백준 11051 이항계수: 이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수이다.

보호되어 있는 글입니다.

트리 그래프의 특수한 형태로 노드와 엣지로 연결된다. 순환 구조가 없고 1개의 루트노드가 존재한다.  트리에서 임의의 두 노드를 이어주는 경로는 유일하다. 노드: 데이터의 인덱스와 값을 표현엣지:노드사이의 연결루트: 최상위 노드리프노드:최하위에 존재하는 노드자식노드: 두 노드 사이에서 하위노드에 해당하는 노드 tree 문제:1) 그래프 풀이   dfs, bfs 문제2) tree만을 위한 문제   이진트리, 세그먼트 트리,lca (최소 공통 조상)      1차원 배열로 트리를 표현      (자식으로 이동할 때는 index*2 or index*2+1 부모로 이동할 때는 index/2...) [백준 11725] 인접리스트 자료구조 사용일반적으로 dfs, bfs사용dfs를 사용해 쉽게 해결 가능 깊이우선 탐..

섹션 6) 다익스트라에서 최소 신장 트리까지1.다익스트라 알고리즘시작 노드와 그 외 노드들 간의 최단 거리를 구하는 알고리즘. 엣지는 항상 양수여야 한다.  1. 인접리스트로 그래프 구현하기 (각 노드에서 갈 수 있는 노드와 가중치를 리스트 원소로)(인접행렬로도 구현 가능하지만 시간복잡도 측면에서 인접리스트로 구현해주도록 한다.)2. 최단거리 배열을 초기화한다. (시작노드는 0 나머지는 무한대)3. 값이 가장 작은 노드 고르기(처음은 시작노드가 된다)4. 최단거리 배열 업데이트하기5.모든 노드가 처리될때까지 3, 4 반복. 방문 배열을 만들어 재방문이 일어나지 않도록 한다. 2.벨만포드그래프에서 최단거리를 구하는 알고리즘.출발 노드에서 다른 노든까지의 최단 경로 탐색.엣지는 음수여도 된다.(음수 사이클 ..

5-1) 그래프노드와 엣지의 집합 유니온 파인드그래프의 사이클이 생성되는지 판별하는 알고리즘위상 정렬사이클이 없는 방향 그래프에서 사용가능.그래프의 노드들을 선형으로 정렬. 정렬 결과가 꼭 한개는 아님 ex)수강신청다익스트라시작점이 존재하고 그 노드에서 다른 모든 노드로 가는 최단 거리를 구하는 알고리즘.단 음수 간선은 있으면 안됨  =>최단거리 알고리즘 벨만-포드다익스트라 알고리즘인데 음수 간선이 가능함.  음수 사이클이 존재하는가=>최단거리 알고리즘 플로이드-워셜벨만 -포드 알고리즘 인데 시작 노드가 없음. 즉 모든 노드 사이의 최단거리 측정. (시간복잡도가 안좋음)=>최단거리 알고리즘 최소 신장 트리 mst. 그래프에서 최소의 가중치 합으로 모든 노드를 연결할 수 있게 해주는 알고리즘. 사이클이 없..

4-1)소수 구하기 핵심 이론소수: 1과 자기 자신 외 약수가 존재하지 않는 수 기본 원리에라토스테네스의 체:1. 구하고자 하는 범위만큼 1차원 배열 생성2. 2부터 시작하고 현재 숫자가 지워지지 않을 때 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하며 지움.이때 처음 선택한 숫자는 지우지 않는다.3. 배열의 끝까지 반복해준 후 배열에남아 있는 모든 수 출력이중 for문을 사용하므로 시간 복잡도는 N^2최적화 정도에 따라서 실제 속도는 n(log(logn))임.배수 삭제 과정에서 바깥쪽 for문을 생략하는 경우가 빈번하게 발생하기 때문에라토스테네스의 체는 소수를 구하는 일반적 방법으로 이용된다.  4-2)오일러 피자주 등장하지는 않음오일러 피 함수 p(n)의 정의는1부터 n까지의 숫자중..

3-1)깊이 우선 탐색  DFS가장 많이 사용되는 탐색 방법.깊이우선 탐색: 그래프 완전 탐색 기법중 하나. 시작 노드에서 출발하여 한 쪽 분기를 정해 최대 깊이까지 탐색을 마친 후 다음 분기로 너머가 탐색을 수행.재귀 함수, 스택 자료구조를 이용한다. 시간 복잡도: O(노드 수+엣지 수)깊이 우선 탐색에서 재귀함수를 이용하므로 스택 오버플로우에 유의해야 함. 한번 방문한 노드를 다시 방문하지 않으므로 노드 방문 여부를 페크할 배열이 필요하다. 대부분 인접리스트로 표현.후입선출의 특성을 가진다. 실제로는 스택 자료구조보다 스택의 성질을 갖는 재귀함수로 구현하는 경우가 더 많다.   [수행과정]  1. dfs를 시작할 노드를 정한 후 사용할 자료구조(인접리스트)를 초기화한다.  2. 스택에서 노드를 꺼내고..

2-1) 버블정렬 로직이 단순하고 구현이 쉽다는 장점이 있다. 데이터의 인접요소끼리 먼저 비교하고 swap을 통해 정렬한다. 시간복잡도는 n^2으로 다른 정렬보다 많은 시간이 걸린다. 앞에서부터 뒤로가며 요소를 비교해 정렬하여 맨 마지막 인덱스에 위치하게되는 요소는 가장 큰 요소인게 확정된다. 따라서 루프를 1회 실행할때 마다 마지막에 위치하게되는 요소가 확정되어 n^2의 시간복잡도를 가지게 된다. 만약 특정 루프의 전체 영역에서 한번도 스왑이 일어나지 않았다면 전체가 정렬되어있다는 의미이므로 루프를 탈출해도된다. 2-2) 선택정렬 최대나 최소의 데이터를 찾아가며 선택하는 방법. n^2의 시간복잡도로 빠른 방법은 아님. 정렬에 따라 최댓값또는 최솟값을 찾고 남은 정렬부분 가장 앞 데이터와 스왑하는 방식...

1-1)배열과 리스트 파이썬의 리스트는 배열의 특성도 내포하고있음. 파이썬에서의 리스트는 배열의 특성까지 가지게 구현되어있음. 인덱스로 접근이 가능하고 가변적으로 변하는 크기라는 장점만 가지고있다. 자료구조에서 배열: 메모리의 연속된 공간에 값이 채워져있는 형태의 자료구조. 값을 인덱스를 통해 직접 접근할 수 있다. 새로운 값의 삽입이나 삭제가 어렵다는 단점이 있다. 배열의 크기는 선언시에 지정할 수있으며 한번선언한 이후 크기를 조절할 수 없다. 자료구조에서 리스트: 값과 포인터를 묶은 노드라는것을 포인터로 연결한 자료구조. 값에 접근하려면 인덱스가 없기때문에 head 포인터로부터 순차적으로 접근해야한다는 단점이 있다. 포인터로 연결되어 데이터 삽입삭제의 속도가 빠르고 선언할 때 별도의 크기를 지정하지 ..