빠르게 성장하는 개발자

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. 합병 정렬의 기본적인 idealist가 주어지면 → 길이가 1일 때까지 나눈다 분할 → 병합 merge ! 2. 분할 → python 으로 구현하기def merge_sort(unordered_list): if len(unordered_list)

🍨 제목은 귀엽지만 풀이과정은 사악했던 디저트 카페 문제를 데려왔다.https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5VwAr6APYDFAWudfs 라는 것은 알겠는데 도저히 생각나지 않아서 약간 검색의 힘을 빌렸다. 1. 문제의 특징이동할 수 있는 방향의 순서가 정해져 있다. 직사각형을 이루려면 시계방향 혹은 반시계방향으로 돌면서 탐색이 이뤄저야 한다. 지금 내가 갈 수 있는 방향은 이전의 방향, 그리고 시계방향으로 돌아간 방향 2가지로 제한되어있다는 뜻이다.⇒ 함수의 인자에 방향을 나타내는(d)를 추가하여 기존에 오고 있는 방향으로 이동할 수 있다면 이동하고, 그렇지 않다면 그 다음 방향으로 탐색하는 코드를 ..

1. 완전 탐색의 기본기억하자 for 문을 돌려야 될 수도? → 언제나 for 문에 대한 열린 생각!!2. 기본적인 순열 & back-tracking 문제완전 탐색을 하면 ⇒ 시간초과 에러가 발생하였다!back-tracking을 통해서 중간까지의 합이 현재의 최솟값보다 크면(앞으로는 더해야 하므로 가망이 없기 때문에) 리턴하는 방식으로 가지치기를 진행해주었다.→ 이를 위해서 함수에 tmp 라는 인자를 가지고 다닌다.이 테크닉을 이후에 유용하게 잘 써먹고 있다!# 각 줄에 대해서 하나씩 선택하는 함수를 만든다 def select(i, k, tmp): global min_V if tmp > min_V: return if i == k: min_V = min(min_V, tmp) return else: for ..