benjykim

[알고리즘] BFS(너비 우선 탐색) 정리 아래와 같이 그래프가 있을 때 BFS 구현 방법에 대해 작성한다. 그래프 graph = [ [], [2,3,8], # [1]번 노드와 연결된 노드: 2, 3, 8번 노드 [1,7], # [2]번 노드와 연결된 노드: 1, 7번 노드 [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7] ] BFS for graph 큐를 사용하는 BFS - deque사용 from collections import deque # BFS 메서드 정의 def bfs(graph, start, visited): queue = deque([start]) visited[start] = True while queue: # 큐에서 원소 하나를 뽑아서 출력 v = queue...

[오픽] 거주지 스크립트 선택 사항: 일 경험 없음 / 학생 아니다(수강 후 5년 이상 지남) / 가족과 함께 거주 / 영화보기, 공원가기, 해변가기, 카페/커피 전문점 가기 / 음악 듣기 / 조깅 및 걷기, 하이킹/트레킹 / 운동 전혀 하지 않음 / 집에서 보내는 휴가 / 국내 여행 / 해외 여행 난이도: 5 선택 성적: IH 참고 자료: 오픽 노잼 및 2주 만에 끝내는 해커스 오픽(Advanced 공략) 스크립트 정리 사는 곳 Please tell me about your house. What’s your favorite room? What does it look like? Why do you like that room? Answer: Um… about my house.. you know, I liv..

[Spring-Boot] 코드로 배우는 스프링 부트, 웹 MVC, DB 접근 기술(2) 외부 라이브러리 앞에서 언급한 Gradle 혹은 Maven 과 같은 툴들은 모두 의존 관계를 관리해준다. 뷰 설정 resources/static에 index.html 파일 추가 스프링 부트가 제공하는 Welcome Page 기능 static에 index.html을 올려두면 Welcome Page 를 볼 수 있다. 다시 말하면, 스프링 부트는 resources/static에서 index.html파일을 검색한 뒤 이를 웹 브라우저에게 그대로 넘겨준다. resources/template에 hello.html 파일 추가 템플릿 엔진을 사용하면 프로그래밍을 통해 동적 페이지를 생성(?)가능하다. 즉, 렌더링을 통해 동적으로 여..

[Spring-Boot] 코드로 배우는 스프링 부트, 웹 MVC, DB 접근 기술(1) 프로젝트 생성 프로젝트 빌드 도구는 Gradle, Maven로 2가지가 있고, Gradle이 대세다. 프로젝트 생성 시 Group에는 회사명, artifact는 결과물을 명시한다. Dependencies는 어떤 라이브러리를 사용할 지를 결정하기 위한 놈이다. 기본적으로 Spring Web과 thymeleaf를 추가한다. spring.io를 통해 내려 받은 프로젝트 압축 파일을 풀고 인텔리제이(Intellij)로 build.gradle파일을 오픈하여 프로젝트를 열자. 프로젝트 구조 build.gradle 파일: 버전 설정 및 라이브러리 관련 내용 포함 프로젝트 실행하면 바로 localhost:8080에 접근가능 내장 톰..

[알고리즘] 위상정렬 위상정렬: 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용 가능한 알고리즘 다시 말하면, 방향 그래프의 모든 노드를 *방향성에 거스르지 않도록 순서대로 나열하는 것 위상 정렬 동작 과정 진입차수가 0인 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거 새롭게 진입차수가 0이 된 노드를 큐에 삽입 주의할 점 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단 다시 말해, 원소가 V(노드의 개수)번 추출되기 전에 큐가 비어버리면 사이클이 발생한 것임 위상 정렬의 답안은 여러 가지가 될 수 있다. 위상 정렬 소스코드 입력 예시 # 노드 및 간선 개수 7 8 # a 노드에서 b로 이동..

[알고리즘] 크루스칼(Kruskal) 알고리즘 신장 트리: 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 최소 신장 트리 알고리즘: 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘 대표적인 최소 신장 트리 알고리즘: 크루스칼 알고리즘 알고리즘 동작 과정 간선 데이터를 비용에 따라 오름차순으로 정렬 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인 사이클이 발생하지 않는 경우 최소 신장 트리에 포함 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않음 모든 간선에 대해 2번의 과정을 반복 크루스칼 알고리즘 소스코드 입력 예시 # 노드 7개, 간선 9개 7 9 # 1번 노드에서 2번 노드로 가는 비용: 29 1 2 29 1 5 ..

[알고리즘] 유니온 파인드(Union-find) 알고리즘 유니온 파인드 알고리즘: 서로소 집합, 상호배타적 집합(Disjoint-Set)알고리즘이라고도 불린다. 여러 노드가 있을 때, 선택한 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다. 입력 예시 6 4 1 4 2 3 2 4 5 6 경로 압축 기법을 사용하지 않은 풀이 # 특정 원소가 속한 집합 찾기 def find_parent(parent, x): if parent[x] != x: return find_parent(parent, parent[x]) return x # 두 원소가 속한 집합 합치기 def union_parent(parent, a, b): a = find_parent(parent, a) b = find_parent(pare..

[알고리즘] 플로이드 워셜(Floyd-Warshall) 알고리즘 플로이드 워셜 알고리즘: 모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야 하는 경우 사용할 수 있는 알고리즘 입력 예시 # 노드 개수(n) 4 # 간선 개수(m) 7 # a, b, c: a 노드에서 b 노드로 가는 비용 c 1 2 4 1 4 6 2 1 3 2 3 7 3 1 5 3 4 4 4 3 2 소스코드 INF = int(1e9) n = int(input()) m = int(input()) graph = [[INF] * (n+1) for _ in range(n+1)] # 자기 자신에서 자기 자신으로 가는 비용 0으로 초기화 for a in range(1, n+1): for b in range(1, n+1): if a == b: gr..

[알고리즘] 다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘: 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우에 사용할 수 있는 최단 경로 알고리즘 입력 예시 # 6개의 노드(1~6), 11개의 간선 6 11 # 시작 노드 1 # a, b, c: a 노드에서 b 노드로 가는 비용 c 1 2 2 1 3 5 1 4 1 2 3 3 2 4 2 3 2 3 3 6 5 4 3 3 4 5 1 5 3 1 5 6 2 우선순위 큐(heapq)를 이용한 풀이 import heapq import sys input = sys.stdin.readline INF = int(1e9) n, m = map(int, input().split()) start = int(input()) graph = [[] for i..

[알고리즘] 2020 KAKAO BLIND RECRUITMENT - 문자열 압축 url: https://programmers.co.kr/learn/courses/30/lessons/60057 문제 설명 데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 aabbaccc의 경우 2a2ba3c(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압..