https://programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr def solution(s): answer = 1001 if len(s) == 1: return 1 for size in range(1, len(s)//2 + 1): compression = '' piece = s[:size] cnt = 1 for i in range(size, len(s), size): if piece == s[i:i+size]: cnt..
https://programmers.co.kr/learn/courses/30/lessons/83201 코딩테스트 연습 - 2주차 [[100,90,98,88,65],[50,45,99,85,77],[47,88,95,80,67],[61,57,100,80,65],[24,90,94,75,65]] "FBABD" [[70,49,90],[68,50,38],[73,31,100]] "CFD" programmers.co.kr def grade(score): if score >= 90: return 'A' elif score >= 80 and score = 70 and score = 50 and score < 70: ret..
DFS (Depth First Search, 깊이 우선 탐색)
DFS (Depth First Search, 깊이 우선 탐색) 시작 정점으로부터 연결 된 노드를 따라 마지막 노드까지 탐색하는 알고리즘 특징 - 모든 노드를 탐색해야할 때 사용 - 재귀적 장점 - 구현이 BFS보다 간단하다. - 저장 공간이 비교적 적다. - 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 단점 - 단순 검색 속도가 BFS보다 느리다. - 목표까지의 경로가 여러 개인 경우 구한 해가 최적이 아닐 수 있다. - 해가 없는 경로에 깊이 빠질 가능성이 있다. -> 임의의 깊이까지 탐색할 때까지 목표를 찾지 못한다면 다음 경로를 찾을 수도.. Python 구현 코드 check = [0 for i in range(N)] # 방문 여부를 확인 s = [[0, 1, 1, 1], [1, ..
BFS (Breadth First Search, 너비 우선 탐색)
BFS (Breadth First Search, 너비 우선 탐색) 시작 정점으로부터 거리가 가까운 정점 순(너비 우선)으로 인접한 노드를 탐색하는 알고리즘 특징 - 최단 경로를 찾을 때 사용 - 일반적으로 큐(Queue) 사용 (선입선출 방식을 사용해야 함) - 재귀적 x - 시간복잡도 : 인접 리스트로 구현된 경우 O(|V|+|E|), 인접 행렬로 구현했을 경우 O(|V|^2) - 입력 : 노드의 갯수 n, 그래프 graph, 시작 노드 v 장점 - 최단 경로를 보장 - 단순 검색 속도가 DFS보다 빠르다. 단점 - 경로가 긴 경우 많은 메모리를 필요로 한다. Python 구현 코드 n = 6 graph = {1: [3, 2], 2: [3, 1, 4, 5], 3: [6, 4, 2, 1], 4: [3, ..
https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr from collections import deque def solution(n, edge): answer = 0 graph = {i:[] for i in range(1, n+1)} for i, j in edge: graph[i].append(j) graph[j].append(i) visited = [0] * (n+1) visited[1] = 1 queue = deque([[1, 0]]) while(queue): node, dept..
https://programmers.co.kr/learn/courses/30/lessons/77485 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr def solution(rows, columns, queries): answer = [] s = [] i = 1 for _ in range(rows): tmp = [] for _ in range(columns): tmp.append(i) i += 1 s.append(tmp) for query in queries: num = 10001 x1, y..
https://programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr def solution(n, times): answer = 0 left = 1 right = max(times) * n while left = n: right = mid else: left = mid + 1..