개발새발

보호되어 있는 글입니다.

vectorint> map[node개수] vectorint> map[시작노드].push_back(연결노드)    예를 들어 위 그림처럼 단방향그래프로1번 정점에서 갈 수 있는 정점이 2, 3, 4 라면map[1].push_back(2)map[1].push_back(3)map[1].push_back(4)를 해주면 된다.     현재 노드에서 갈 수 있는 다음 노드를 선택 하는 방법for(int i=0; i이렇게 노드를 선택해주면 DFS나 BFS에 활용할 수 있다.   #include #include #include using namespace std;int ch[30], cnt = 0, n, path[30], p1 = 0;vector map[30];void DFS(int v) { if (v == n)..

보호되어 있는 글입니다.

보호되어 있는 글입니다.

N = int(input()) num_list = list(map(int, input())) sum = 0 for i in num_list: # num_list 을 반복적으로 가져와서 각 원소를 i에 할당. sum = sum + i print(sum) ※ list(int(input()))는 각 숫자를 하나씩 입력받아서 정수로 변환한 뒤 리스트로 만드는 것이 아니라 첫 번째 숫자를 입력받고 정수로 변환한 후에 그 값을 리스트로 만든다 num_list = list(map(int, input())) 따라서, 이렇게 입력받은 숫자를 문자열로 받은 뒤에 각 숫자를 분리하여 리스트로 만들어주어야 한다!! map() 함수는 반복문을 사용하지 않고도 여러 개의 요소에 동일한 연산을 적용할 수 있다 위의 예제에서는 ma..

그래프의 특정한 경우 → 사이클이 없는 연결 그래프 부모 : 특정 노드 위에 있는 노드 자식 : 특정 노드 밑에 있는 노드 형제 : 한 부모 밑에서 태어난 노드 깊이 : 루트 노드 ~ 해당 노드까지의 길이 레벨 : 깊이가 같은 노드 집합 높이 : leaf노드 까지의 깊이 차수 : 특정 노드의 자식 노드 개수 그림으로 표현! 노드 선언 및 생성 자식 노드 연결 계층적 데이터를 효과적으로 탐색 가능 리스트(단순 나열) vs 부모-자식간 상하관계 사이클 X!!! 루트 노드를 제외한 모든 노드는 단 하나의 부모노드를 가진다. 자식노드는 여러개 가질 수 있음 트리 순회 루트 → 왼쪽 → 오른쪽 왼쪽 → 루트 → 오른쪽 오른쪽 → 왼쪽 → 루트 레벨이 낮은 것부터 왼쪽→ 오른쪽 이진 트리 (Binary Tree) ..

주요 키워드dp, memoization(메모이제이션) , 반복/재귀  → 반복되는 계산을 막기 위해서.가장 대표적인 예 → 피보나치 수열 f(n)=f(n-1)+f(n-2)이러한 식으로 겹치는 계산이 발생한다면 이를 그때그때 다 계산하지않고 한 번 계산한 값을 계속 사용!피보나치 수열 피보나치 수열은 제2항까지는 1, 제3항부터는 바로 앞의 두 항을 더한 수로 정의(0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...프로그래밍에서 피보나치 수열은 보통 재귀를 통해 표현int fibo(int n) { if (nfibo(6)은 어떻게 실행될까? fibo(4)의 연산이 두 번,fibo(3)의 연산이 세 번 진행되는 것을 볼 수 있다. 이미 진행됐던 연산인데도 불구하고!!! 위의 ..

브루트포스 무식한 힘 가능한 모든 경우에 대해 탐색 구현이 쉽고, 해가 존재한다면 무조건 답을 찾을 수 있음 그러나, 모든 경우에 대해 탐색하기 때문에 시간 복잡도 효율성 낮음 → 메모리 사용량 많음 장단점이 명확 ⇒ 사용해야할 문제와 그렇지 않은 문제도 확실 가장 기본적인 알고리즘. 이를 바탕으로 다른 알고리즘으로의 확장 예를 들어, 비밀번호가 4자리이고, 숫자로만 이루어져 있다면 비밀번호를 풀기 위해서 0000부터 9999까지 다 입력해보면 된다. 경우의 수가 10000가지 이므로 이는 컴퓨터에서 충분히 빠른 처리가 가능한 연산이다. 하지만 비밀번호가 12자리라면 범위가 000000000000부터 999999999999이므로 경우의 수가 1000000000000가지이다.python의 경우 1억 개의 ..