개발자 꿈나무의 블로그

코딩테스트 연습 - 순위 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr * 문제 설명 n명의 권투선수가 권투 대회에 참여했고 각각 1번부터 n번까지 번호를 받았습니다. 권투 경기는 1대1 방식으로 진행이 되고, 만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다. 심판은 주어진 경기 결과를 가지고 선수들의 순위를 매기려 합니다. 하지만 몇몇 경기 결과를 분실하여 정확하게 순위를 매길 수 없습니다. 선수의 수 n, 경기 결과를 담은 2차원 배열 results가 매개변수로 주..

* 개요 플로이드-워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용할 수 있는 알고리즘이다. 플로이드-워셜 알고리즘은 단계마다 '거쳐 가는 노드'를 기준으로 알고리즘을 수행한다. 하지만 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾을 필요가 없다. 노드의 개수가 N개일 때, 알고리즘 상으로 N번의 단계를 수행하며, 단계마다 O(N^2)의 연산을 통해 '현재 노드를 거쳐 가는' 모든 경로를 고려한다. 따라서 폴로이드-워셜 알고리즘의 총 시간 복잡도는 O(N^3)이다. 다익스트라 알고리즘은 출발 노드가 1개이므로 다른 모든 노드까지의 최단 거리를 저장하기 위해서 1차원 리스트를 이용했다. 반면에 플로이드 워셜 알고리즘은 다익스트라 알고리즘과는 다..

* 개요 위상정렬은 정렬 알고리즘의 일종이다. 위상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 조금 더 이론적으로 설명하자면, 위상 정렬이란, 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'이다. 위상 정렬 알고리즘을 알기 위해서는 먼저 진입 차수(Indegree)를 알아야 한다. 진입 차수란 특정한 노드로 들어오는 간선의 개수를 뜻한다. 방향 그래프에서 위상 정렬을 수행하는 절차는 다음과 같다. 진입 차수가 0인 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다.(3 -> 4, 3 -> 4, ...) 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. 새롭게 진입 차수가 0이 된 노드를 큐에..

코딩테스트 연습 - 가장 먼 노드 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr * 문제 설명 n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도..

* 개요 다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 다익스트라 최단 경로 알고리즘은 '음의 간선'이 없을 때 정상적으로 동작한다. 음의 간선이란, 0보다 작은 값을 가지는 간선을 의미하는데, 현실 세계의 길(간선)은 음의 간선으로 표현되지 않으므로 다익스트라 알고리즘은 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다. 다익스트라 최단 경로 알고리즘은 기본적으로 그리디 알고리즘으로 분류된다. 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문이다. 알고리즘의 원리를 간략히 설명하면 다음과 같다. 출발 노드를 설정한다. 최단 거리 테이블을 초기화한다. 방문하지 않은..

* 개요 IntelliJ IDEA는 JetBrains 사에서 개발한 통합 개발 환경이다. 이클립스보다 여러 면에서 뛰어나다고 평가된다. 파일 시스템과 용어가 다른 IDE와는 좀 다르기 때문에 사전 학습이 많이 필요하다. 따라서 필자도 인텔리제이에 대해 학습하고자 먼저 단축키에 대해 포스팅해보고자 한다. 해당 단축키는 윈도우에 적용되는 단축키이다. * 단축키 CTRL + SHIFT + T Test 클래스 쉽게 만들기 ALT + INSERT 코드 삽입(Constructor, get/setter, toString 등) CTRL + ALT + SHIFT + T refactoring CTRL + ALT + V 변수 추출 ALT + ENTER 1. implement methods(인터페이스 메소드 불러오기) 2. ..

* 개요 BFS 알고리즘은 너비 우선 탐색이라는 의미를 가진다. 쉽게 말해 가까운 노드부터 탐색하는 알고리즘이다. DFS는 최대한 멀리 있는 노드를 우선으로 탐색하는 방식으로 동작하는데, BFS는 그 반대라고 할 수 있다. BFS의 구현은 선입선출 방식인 큐 자료구조를 이용하는 것이 정석이다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다. BFS 알고리즘의 정확한 동작 방식은 다음과 같다. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. ..

* 개요 DFS는 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS를 설명하기 전에 먼저 그래프의 기본 구조를 알아야 한다. 그래프는 노드와 간선으로 표현되며, 이 때 노드를 정점이라고 말한다. 그래프 탐색이란, 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 또한 두 노드가 간선으로 연결되어 있다면, '두 노드는 인접한다.'라고 표현한다. * 인접 행렬 먼저 인접 행렬 방식은 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다. 위와 같이 연결된 그래프를 인접 행렬로 표현할 때 파이썬에서는 2차원 리스트로 구현할 수 있다. 연결이 되어 있지 않은 노드끼리는 무한의 비용(INF)이라고 작성한다. 실제 코드에서는 논리적으로 정답이 될 수 없는..

* 개요 Binary Search(이진 탐색)은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다는 특징이 있다. 또한 이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있다. 이진 탐색은 위치를 나타내는 변수 3개를 사용하는데, 탐색하고자 하는 범위의 시작점(start), 끝점(end), 그리고 중간점(mid)이다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는게 이진 탐색 과정이다. 순차 탐색의 시간복잡도가 O(N)인 것에 비해, 이진 탐색의 시간복잡도는 O(logN)이다. 따라서 데이터의 양이 많은 경우에는 이진 탐색을 활용..

* 개요 파이썬으로 코테, 자료구조, 알고리즘 공부를 진행하다보니, 리스트 선언의 중요성이 더욱 와닿는다는 것을 느꼈다. 오늘 소개할 List Comprehension(리스트 컴프리헨션)은 리스트를 초기화하는 방법 중 하나이다. 리스트 컴프리헨션은 간단히 0부터 19까지의 수 중에서 홀수만 포함하는 리스트를 만들고자 할 때는 다음과 같이 리스트를 초기화할 수 있다. 이 경우 한 줄의 소스코드로 리스트를 초기화할 수 있어 매우 간편하다. # 0부터 19까지의 수 중에서 홀수만 포함하는 리스트 array = [i for i in range(20) if i % 2 == 1] print(array) # [1, 3, 5, 7, 9, 11, 13, 15, 17, 19] 참고로 위 소스코드를 일반적인 소스코드로 작성..