👾

문제 링크: programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 문제 설명 4번 선수가 2번 선수에게 이기고 2번 선수가 5번 선수에게 이긴다면, 4번 선수는 결국 5번 선수에게도 이깁니다. 4번 > 2번, 2번 > 5번 → 4번 > 5번 이런 식으로 모든 선수의 경기 결과를 종합해서 결과의 개수가 (n - 1)개라면 순위를 확정 지을 수 있습니다. 경기 결과를 저장할 win, lose 딕셔너리 초기화 results에 있는 경기 결과를 입력 (선수가 겹치지 않게 set 자료형 이용) n명의 선수들의 경기 결과 합치기 1) 만약 A가 ..

문제 링크: 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 문제 설명 1번 노드로부터 가장 멀리 떨어진 노드의 개수를 출력하는 문제입니다. 1번 노드부터 BFS를 수행하며 1번 노드와의 distance를 저장한 뒤, distance가 가장 큰 값을 갖는 원소의 개수를 반환하도록 코드를 작성했습니다. 인접 노드 정보를 저장할 graph와 1번 노드로부터의 거리를 저장할 distance 초기화 주어진 edge 정보를 graph에 저장 1번 노드의 distance를 0으로 하고, 1번 노드를 큐에..

문제 링크: programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 문제 설명 DFS를 이용해 모든 티켓을 사용하는 경로를 탐색합니다. 이때 DFS의 순서를 스택에 저장했다가 스택 top에서 갈 수 있는 경로가 없을 경우에 answer에 추가합니다. 갈 수 있는 경로가 없다는 것은 그 공항이 제일 마지막 방문지라는 의미입니다. 즉, answer에는 공항을 방문하는 순서가 거꾸로 저장되게 됩니다. ..

문제 링크: programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 문제 설명 각 단어가 한 글자씩만 차이 나는 경우(ex. hot과 hit) 단어 변환이 가능합니다. 단어들을 정점들로, 변환이 가능한 경우를 간선으로 표시해서 BFS를 이용해 문제를 해결했습니다. begin을 포함해서 그래프를 만들기 위해 words에 begin 단어를 삽입 그래프를 표현하는 인접 리스트 초기화 이때 두 ..

문제 링크: programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 문제 설명 BFS를 이용해 연결된 모든 컴퓨터를 탐색하는 방법으로 문제를 해결했습니다. 방문하지 않은 컴퓨터 중 작은 번호부터 BFS 수행 BFS가 끝나면 네트워크 개수 1 증가 (answer++) 방문하지 않은 컴퓨터가 없을 때까지 1~2번을 반복 수행 소스코드 from collections import deque def solution(n, compute..

문제 링크: www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 설명 시간 내에 문제를 풀기 위해선 동적 계획법(Dynamic Programming)을 이용해 문제를 해결해야 한다. 1로 만들기 위한 연산 횟수를 저장하는 dp테이블을 만들고 dp[1]부터 dp[n]까지를 계산한다. dp[1] = 0 dp[2] = dp[1] + 1 // 2로 나누거나 1을 빼기 dp[3] = dp[1] + 1 // 3으로 나누기 dp[4] = dp[2] + 1 = dp[3] + 1 // 2로 나누거나 1을 빼기 dp[5] = dp[4] + 1 // 1을 빼기 dp[6] = dp[2] + ..

문제 링크: www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 문제 설명 사이트의 개수는 항상 동쪽이 많으므로 (N

문제 링크: www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 문제 설명 BFS를 이용하여 도시를 모두 방문하는 방법을 이용하였다. BFS를 하는 중 만약 현재 도시의 최단 거리 값이 k 보다 클 경우, 이 뒤에 방문하는 도시들의 최단 거리는 모두 k보다 크므로 BFS를 중지한다. solution 함수 설명 최단 거리가 k인 도시들을 담을 리스트 answer 초기화 출발 도시를 큐에 삽입..

목차 다익스트라 알고리즘 소개 알고리즘 동작 과정 알고리즘 구현(파이썬) 다익스트라(Dijkstra) 최단 경로 알고리즘 특정 정점에서 출발하여 다른 모든 노드로 가는 최단 경로 계산 Single-Source Shortest Paths 문제에 사용될 수 있음 매 상황에서 가장 비용이 적은 노드 선택을 반복(그리디 알고리즘) 알고리즘 동작 과정 출발 정점 선택 최단 거리 테이블을 INF로 초기화 방문하지 않은 정점 중에서 최단 거리가 가장 짧은 정점 선택 해당 정점을 거쳐 다른 정점으로 가는 비용을 계산하여 최단 거리 테이블 갱신 3~4번 과정 반복 알고리즘 구현 방문하지 않은 정점 중에 최단 거리가 가장 짧은 정점을 빠르게 찾기 위해 우선순위 큐 사용 import heapq import sys input..

목차 BFS의 개념 BFS의 장단점 BFS의 시간 복잡도 BFS의 구현 BFS(너비 우선 탐색)이란? BFS(Breadth First Search) 또는 너비 우선 탐색이라고 함 시작 정점으로부터 가까운 정점을 먼저 방문하는 그래프 탐색 방법 큐(queue)를 이용해 방문한 정점들을 차례로 저장하고 꺼냄 BFS의 동작 과정 탐색 시작 정점을 큐에 삽입하고 방문 처리를 합니다. 큐에서 정점을 꺼낸 뒤에 해당 정점의 인접 정점 중에서 방문하지 않은 정점을 모두 큐에 삽입하고 방문 처리를 합니다. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복합니다. BFS의 장단점 장점 시작 정점에서 목표 정점까지의 최단 길이 경로를 보장한다. 단점 경로가 매우 길 경우, 탐색 가지가 급격히 증가함에 따라 많은 기억 공..