Devlog

DFS (Depth First Search, 깊이 우선 탐색) 시작 정점으로부터 연결 된 노드를 따라 마지막 노드까지 탐색하는 알고리즘 특징 - 모든 노드를 탐색해야할 때 사용 - 재귀적 장점 - 구현이 BFS보다 간단하다. - 저장 공간이 비교적 적다. - 목표 노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다. 단점 - 단순 검색 속도가 BFS보다 느리다. - 목표까지의 경로가 여러 개인 경우 구한 해가 최적이 아닐 수 있다. - 해가 없는 경로에 깊이 빠질 가능성이 있다. -> 임의의 깊이까지 탐색할 때까지 목표를 찾지 못한다면 다음 경로를 찾을 수도.. Python 구현 코드 check = [0 for i in range(N)] # 방문 여부를 확인 s = [[0, 1, 1, 1], [1, ..

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/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..

https://programmers.co.kr/learn/courses/30/lessons/81301 코딩테스트 연습 - 숫자 문자열과 영단어 네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다. 다음은 숫자의 일부 자 programmers.co.kr def solution(s): answer = '' eng = { 'one': '1', 'two': '2', 'three': '3', 'four': '4', 'five': '5', 'six': '6', 'seven': '7', 'eight': '8', 'nine': '9', 'zero': '0' } num = '' for word in s: if wo..

https://programmers.co.kr/learn/courses/30/lessons/72412 0: left, right = 0, len(scores) # lower bound 이용해서 인덱스 찾기 while left = point: right = mid else: left = mid + 1 answer.append(len(scores) - left) else: answer.append(0) return answer

www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net import sys N = int(sys.stdin.readline()) strings = [] for _ in range(N): word = input() strings.append((word, len(word))) strings = list(set(strings)) strings = sorted(strings, key = lambda x:(x[1], x[0])) for string in strin..

programmers.co.kr/learn/courses/30/lessons/42862# 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr def solution(n, lost, reserve): answer = 0 students = [1] * n for i in lost: students[i-1] -= 1 for i in reserve: students[i-1] += 1 for i in range(n): if students[i] == 0: if i != 0 and students[i-1] >= 2: stud..