빠르게 성장하는 개발자

단순한 BFS 문제였다.처음에 생각을 잘못한 부분은 → NxN 에서 가장 큰 마른모는 N일때 발생한다고 생각했는데,N+1 일때 발생한다는 것이 key 였다. (그것때문에 49/50 개 pass 였다. 😿) 실제로 예시의 사진을 보면, 3x3 배열이 쏙 들어가는건 마름모가 k=4 일때임을 알 수 있다!앞으로 이런 디테일에 더 주의해서 문제를 풀어야 겠다.from collections import deque dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] # BFS 함수를 입력 def BFS(i, j, k): global house q = deque() q.append((i, j)) cnt = 1 if homes[i][j] == 1: house += 1 while cnt < k: for ..

1. DP (Dynamic Programming)?큰 문제를 작은 문제로 ‘쪼개어’ 생각하는 것크게 위에서부터 아래로 문제를 쪼개서 내려가는 Top-down 방식과, 아래에서부터 더해 올라가는 Bottom-up방식이 있다.DP의 전형적인 유형이 몇 가지 있고, 평범한 배낭문제도 그 중 하나에 속한다.2. 평범한 배낭문제생각하기가 힘들어서 검색의 힘을 빌렸다. 그런데 검색을 안했으면, 내 머리로는 절대 생각해 내지 못했을 것 같다.DP에서 알고리즘의 벽을 느끼고 있다.완전히 이해하고 작성하는 글이다.문제는 백준 12865 평범한 배낭 글의 예제를 사용하도록 하겠다. 3. 준비과정이차원 배열이 필요하다. 이차원 배열에는 각 상황에 대한 가치의 최대값을 저장한다.예를 들어 배낭에 들어갈 수 있는 총 무게가 7..

1. 문제는 이쪽으로https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do 2. bfs처음에는 수업시간에 배운 다익스트라를 이용해서 풀이해 보려고 했지만,시간복잡도 때문인지 자꾸 시간초과가 나서 bfs를 변형한 방법으로 풀이하였다.from collections import deque di = [-1, 1, 0, 0] dj = [0, 0, -1, 1] def bfs(i, j): # s는 시작지점 q = deque() q.append((i,j)) money[i][j] = 0 # 시작지점의 가격 처리 while q: l = len(q) for _ in range(l): si, sj = q.popleft() for d in range(4): ..

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. 서로소..?중학교 수학시간에 ‘서로소’ 라는 개념을 들어본 적이 있는가?영어로 (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으로 설정하면?? → 최악의 경우가 발생하여 문제 풀이시에 시간초과를 경..