빠르게 성장하는 개발자

N-Queen 문제는 백트랙킹의 대표적인 문제이다.체스의 Queen은 같은 행, 열, 대각선에 대해서 공격할 수 있다.NxN 체스판에서 서로 공격하지 않는 Queen을 몇 개 둘 수 있나? 가 문제이다. 문제는 간단하지만, 풀이과정은 간단하지 않다.처음에는 SWEA에서도 풀이한 문제이기 때문에, 이틀 전에 교수님께서 짜신 코드를 생각하면서 다음과 같이 제출했다.# n-queen def queen(row, k): global cnt if row == k: cnt += 1 return else: for j in range(N): can_position = True # 열 검사 for l in range(0, row+1): if board[l][j] == 1: can_position = False # 대각선 ..

1. 다익스트라 알고리즘이란 무엇인가?MST 다음에 배워서 MST와 비슷한가? 싶었지만 약간 다른 다익스트라!MST는 모든 정점을 잇는 간선이 하나씩 존재해서 모든 정점을 다 이었다면, 다익스트라는 시작정점에서 끝정점으로 가는 경로 중에 가중치가 제일 적은 값을 고르는 알고리즘이다!이 때 특징은 ‘유향’ 그래프, 즉 A → B로는 갈 수 있지만 반대로 B → A로는 가지 않는 ‘방향’ 이 주어지는 그래프라는 것이다. 2. 다익스트라 알고리즘 python 으로 구현하기1. V개의 노드를 방문할 때마다 V개의 인접 노드에 대해서 검사하는 방식→ Prim 알고리즘과 유사한 방식, 시간복잡도가 O(V^2)로 큰편이다.T = int(input()) for tc in range(1, T+1): N, E = map(..

저번에 Prim 알고리즘을 포스팅 하면서, 최소신장트리(MST)에 대해서 작성한 적이 있었다.Kruskal도 Prim과 마찬가지로 MST를 구하는 다른 방법에 해당한다.신장트리: n개의 정점으로 이루어진 무방향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리MST (Minimum Spanning Tree): 신장트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리1. Kruskal 알고리즘이란?Prim 알고리즘을 간단하게 복습해보자면, 임의의 점을 골라서 시작한다 .key값이 최소인 점을 탐색한다 그 점으로부터 도달할 수 있는 지점에 대한 최소 key값을 갱신한다. → 모든 지점을 방문할 때까지 1. 2.를 반복한다.Prim 알고리즘을 공부하다 보면, 이런 생각이 들 수도 있다.💡그냥 가중..

1. 서로소..?중학교 수학시간에 ‘서로소’ 라는 개념을 들어본 적이 있는가?영어로 (disjoint). 즉, 교집합이 없는 서로 다른 두 집합을 서로소 라고 부른다. 그렇다면, 지금 배우고 있는 python으로 서로소 (이하 ‘상호배타집합’ ) 을 어떻게 구할 수 있을까?2. idea0. 상호배타집합에 필수적인 연산 Make-Set(x) : x가 자신을 가리키도록 초기화 하는 것.Find-Set(x) : x의 대표 요소가 있으면, 대표 요소를 가리키도록 타고 올라 가는 것Union(x,y) : x,y를 하나의 집합으로 합친다 ⇒ 즉, x,y 집합중에 대표자를 새로 정하는 것.1. 연결리스트 먼저 단순하게 ‘연결리스트’로 표현해 볼 수 있을 것이다.2. 트리 다음으로는 트리가 있다. 리스트 배열을 사용하..

신장트리: n개의 정점으로 이루어진 무방향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리MST (Minimum Spanning Tree): 신장트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리 Prim 알고리즘Kruskal 알고리즘Dijkstra 알고리즘첫 번째로 Prim 알고리즘에 대해서 알아보려고 한다. 1. Prim 알고리즘의 기본 원리하나의 정점에서 연결된 간선들 중에서 하나씩 선택하면서 MST를 만들어 나간다.임의 정점을 하나 선택해서 시작한다.선택한 정점과 인접한 정점들 중 최소 비용의 간선이 존재하는 간선을 선택한다.모든 정점이 선택 될 때까지 1~2를 반복한다. 서로소인 2개의 집합(2 disjoint-sets) 정보를 유지한다.트리 정점들(tree vertices) :..

1. 백트래킹(Backtracking)과 DFS의 차이어떤 노드에서 부터 더이상 가능성이 없는 노드를 따라가지 않음으로 시도의 횟수를 줄인다.⇒ 이 과정을 (Prunning, 가치치기) 라고 부른다.백트래킹의 과정상태 공간 트리의 DFS 를 실시한다.각 노드가 유망한지를 점검한다.만일 노드가 유망하지 않으면, 부모 노드로 돌아가서 검색을 계속한다.백준의 N과 M문제가 대표적임 Uploaded by N2T

1. 퀵 소트?퀵소트는 주어진 배열을 분할하고 - 각각은 정렬한다.분할한다는 점에서 merge sort와 닮아 보이지만, 다른 점은 ‘병합’ 과정이 필요하지 않다는 것이다!!why? ⇒ merge sort는 각각을 분할하고 끝! 이지만, quick sort는 pivot을 중심으로 작은 것은 왼편, 큰것은 오른편에 두는 과정을 거치기 때문이다. 2. pivot 고르기결국 quick sort의 핵심은 pivot 고르기! 라고 할 수 있겠다.시간복잡도는 O(nlogn)O(nlogn)O(nlogn) 이지만, 최악의 경우 O(n2)O(n^2)O(n2) 가 될 수 있다.예를 들어 이미 정렬이 되어있는 리스트에, 리스트의 첫 원소를 pivot으로 설정하면?? → 최악의 경우가 발생하여 문제 풀이시에 시간초과를 경..

1. 조합(Combination) nCr=n−1Cr−1+n−1CrnCr = n-1Cr-1 + n-1CrnCr=n−1Cr−1+n−1CrN = 5 for i in range(N-2): for j in range(i+1, N-1): for k in range(j+1, N): print(i,j,k)# output 0 1 2 0 1 3 0 1 4 0 2 3 0 2 4 0 3 4 1 2 3 1 2 4 1 3 4 2 3 42. 재귀를 이용해서 구현해보기! def nCr(n, r, s): # n개의 원소에서 r개를 순서없이 뽑늗다. s는 시작하는 범위 if r == 0: print(*comb) else: for i in range(s, n-r+1): comb[r-1] = A[i] #n-1Cr-1 (A의 i번째 원소를..