전체 글397

• [백준/BOJ] 10423번: 전기가 부족해 문제 https://www.acmicpc.net/problem/10423 10423번: 전기가 부족해 첫째 줄에는 도시의 개수 N(1 ≤ N ≤ 1,000)과 설치 가능한 케이블의 수 M(1 ≤ M ≤ 100,000)개, 발전소의 개수 K(1 ≤ K ≤ N)개가 주어진다. 둘째 줄에는 발전소가 설치된 도시의 번호가 주어진다. 셋째 www.acmicpc.net 해설 크루스칼 알고리즘을 응용하여 해결할 수 있는 문제이다. 발전소의 개수가 한개라면, 기본적인 크루스칼 알고리즘으로 최소 비용을 구할 수 있다. 하지만 이 문제에서는 발전소의 개수가 여러 개일 수도 있다. 또한 모든 간선이 연결되어야 하는 것이 아니고, 발전소를 통해 전기를 공급받기만 하면 된다. 나는 미리 발전소의 위치를 -1로 해주었다. 이처럼.. PS(Problem Solving)/BOJ 2022. 7. 29.

• [백준/BOJ] 16236번: 아기 상어 문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 해설 bfs를 사용하여 현재 상어의 위치에서 모든 물고기들의 위치까지 거리를 구하고, 그 중 가장 거리가 가까운 물고기를 찾는다. 나는 우선 먹을 수 있는 물고기들을 전부 찾아 ArrayList에 위치와 상어와의 거리를 저장해주었다. 저장이 끝났다면 위쪽 좌표부터 시작하여 검사하여 가장 가까운 물고기가 정해지지 않는다면, 왼쪽 좌표를 검사하여 먹으러 갈 물고기를 정한다. 이제 그 위치.. PS(Problem Solving)/BOJ 2022. 7. 29.

• [백준/BOJ] 6497번: 전력난 문제 https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 해설 문제를 보면 MST 알고리즘을 사용해야 한다는 것을 알아야 한다. 최소 신장 트리를 구해 총 비용에서 최소 비용을 빼어 절약할 수 있는 최대 액수를 구한다. 어떠한 정점에서 시작해야 된다와 같은 조건이 없으므로, 크루스칼 알고리즘을 사용하였다. 이 문제에서 주의할 점은 입력에 있다. 처음 제출했을 때, 런타임 에러가 나 무엇이 문제인지 고민하다 질문 검색에 들어가 나랑 같은 케이스인 사람들이 있는.. PS(Problem Solving)/BOJ 2022. 7. 28.

• [백준/BOJ] 14950번: 정복자 문제 https://www.acmicpc.net/problem/14950 14950번: 정복자 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재 www.acmicpc.net 해설 모든 도시를 정복하는데 드는 최소 비용을 구하는 문제이다. 이 문장을 보고 MST 알고리즘을 떠올려야 한다. MST를 떠올렸다면, 이를 크루스칼 알고리즘과 프림 알고리즘 중 어떤 알고리즘으로 해결할지 정해야 한다. 이 문제는 1번 도시부터 시작해서 이와 연결된 도시를 정복해나가야 한다. 따라서 프림 알고리즘이 더 적절하다 생각했다. 문제를 보면 "한 번 도시가 정복되면, 모든 도시는 경계를.. PS(Problem Solving)/BOJ 2022. 7. 28.

• 

  파이썬: 함수(Function) 함수란? 카페에서 음료를 시키는 과정을 생각해보자. 우리는 키오스크 또는 직원에게 원하는 음료를 주문할 것이다. 이는 "입력값"이 된다. 또한 주문한 음료가 준비되서 나온다면, "출력값"으로 볼 수 있다. 카페에서 이러한 일이 일어나므로 카페라는 "함수"가 있다고 생각하면 된다. 중고등학교 때도 함수에 대해 배웠을 것이다. 예를 들어 y = x + 3도 함수이다. 이를 직선 그래프로만 배웠지, 프로그래밍의 함수와 연관지을 생각은 못했을 거싱다. 하지만 이 수식도 x의 값이 입력됨에 따라 y값이 출력되는 입력값과 출력값이 있는 함수이다. 함수를 사용하는 이유 프로그래밍을 하다보면 같은 내용을 반복해서 사용해야 할 때가 있다. 이 때 반복되는 부분을 한 뭉치로 묶어 "어떠한 입력값이 주어졌을 때, 어떤 결과.. Programming/Pyhton 2022. 7. 28.

• [백준/BOJ] 21924번: 도시 건설 문제 https://www.acmicpc.net/problem/21924 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net 해설 최소 신장 트리(MST)에 대해 알고 있다면, 굉장히 쉬운 문제이다. 모든 간선의 비용을 합한 값에서 최소 신장 트리를 구해 그만큼의 비용을 빼주면 된다. 나는 크루스칼 알고리즘을 이용하였다. 주의할 점으로는 입력 범위가 크므로 int형을 사용한다면 틀리게 된다. .. PS(Problem Solving)/BOJ 2022. 7. 27.

• [백준/BOJ] 4386번: 별자리 만들기 문제 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 해설 처음 입력으로 별의 개수와 별의 좌표를 입력받는다. 이번 문제에서는 기본적인 수학의 개념도 필요하다. 두 점 사이의 거리를 구해야하기 때문이다. 두 점 사이의 거리를 구하는 공식은 다음과 같다. √(x2-x1)2 + (y2-y1)2 두 별 사이의 거리를 구하는 방법을 알았다면, 별 거 없다는 것을 다들 알 수 있다. 이제 크루스칼 알고리즘을 이용하여 최소 비용을 구하면 된다. 이 때 소수.. PS(Problem Solving)/BOJ 2022. 7. 27.

• [백준/BOJ] 1647번: 도시 분할 계획 문제 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 해설 1. 마을의 이장은 마을을 두 개의 분리된 마을로 분할할 계획을 가지고 있다. 2. 마을에는 집이 하나 이상 있어야 한다. 3. 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 4. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 위는 문제에서 .. PS(Problem Solving)/BOJ 2022. 7. 27.

• 

  파이썬: 반복문(for문, while문) 반복문 for문과 while문이 존재한다. 파이썬에서 이들이 어떻게 쓰이는지에 대해 알아보자. for문 파이썬의 직관적인 특징을 가장 잘 대변해 주는 것이 for문이다. for문의 기본 구조 for 변수 in 리스트(또는 튜플, 문자열 등): 수행할 문장1 수행할 문장2 ... 이는 리스트나 튜플, 문자열 등의 첫 번째 요소부터 마지막 요소까지 변수에 대입되고, 수행할 문장을 수행한다. >>> test = ['cat', 'dog', 'cow'] >>> for i in test: ... print(i) ... cat dog cow >>> test2 = [(1, 2), (3, 4), (5, 6)]: >>> for (first, second) in test2: ... print(first + second) ... Programming/Pyhton 2022. 7. 27.

• 

  [알고리즘] 동적 프로그래밍(Dynamic Programming): 메모이제이션(Memoization), 테뷸레이션(Tabulation) 동적 프로그래밍(Dynamic Programming) 전에 분할 정복에 대해 다뤘던 적이 있 분할 정복은 큰 문제를 여러 개의 소문제로 나눠 해결해나가는 알고리즘이다. 이 작은 문제들을 매번 재계산하지 않고, 기억해두었다가 재사용하는 알고리즘이 동적 알고리즘이다. 동적 프로그래밍의 핵심은 소문제를 정의하는 것이다. 소문제를 정의하고, 이 소문제를 이용하여 다음 크기의 무제를 해결하는 방법을 제시할 수 있어야 한다. 또한 부분 문제들의 답이 중복되지 않게 최적의 방법으로 구해야 한다. 최적 부분 구조(Optimal Substructure) 어떤 문제가 최적 부분 구조로 이루어져 있을 때, 부분 문제들의 최적의 답을 구해 기존 문제의 최적의 답을 구할 수 있다. 동적 프로그래밍의 기본 기법으로는 메모이제이션.. Algorithm 2022. 7. 26.

• [백준/BOJ] 13418번: 학교 탐방하기 문제 https://www.acmicpc.net/problem/13418 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1 ≤ N ≤ 1,000)과 도로의 개수 M(1 ≤ M ≤ N(N-1)/2) 이 주어진다. 입력의 두 번 www.acmicpc.net 해설 MST는 최소 신장 트리이다. 즉, 가중치가 가장 낮은 트리를 구하는 것이다. 이는 크루스칼 알고리즘과 프림 알고리즘으로 구할 수 있다. 그렇다면 반대로 신장 트리 중 최악의 경우도, 크루스칼 알고리즘과 프림 알고리즘으로 구할 수 있다는 얘기가 된다. 이 문제에서는 (최악일 경우의 피로도 - 최소일 경우의 피로도)를 구해야 한다. 나는 입구에서 시작을.. PS(Problem Solving)/BOJ 2022. 7. 26.

• 

  파이썬: 조건문(if, elif, else) if문의 기본 구조 if 조건문: 수행할 문장1 수행할 문자2 ... else 수행할 문장A 수행할 문장B ... 조건문을 테스트하며 참이면 if문에 있는 문장을 수행하고, 거짓이면 else로 넘어가 그 안의 문장들을 수행한다. if문은 else문 없이 사용이 가능하나, else문은 if문 없이 사용이 불가능하다. 조건문 다음에 콜론(:)을 잊어선 안된다. 다른 언어에서는 if(조건문) { }의 구조를 가져 콜론이 필요하지 않다. 하지만 파이썬에서는 괄호를 쓰지 않고 콜론(:)을 쓰는 구조를 가지고 있으니, 빼먹지 않도록 주의해야 한다. 들여쓰기도 중요하다. if check: print("a") print("b") print("c") 다음과 같이 들여쓰기가 제대로 되있지 않다면, 이처럼 빨간 줄을 띄우며.. Programming/Pyhton 2022. 7. 26.

• [백준/BOJ] 14621번: 나만 안되는 연애 문제 https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 해설 연결그래프에서 최소 신장 트리를 찾는 문제이다. 고려할 점은 다음과 같다. 연결된 두 노드가 남초, 여초 학교여야 한다. 두 노드가 모두 남초거나, 여초라면 연결되지 않는다. 만약 두 노드가 같다면, 우선순위 큐에 넣을 필요가 없다. 두 노드간 한 개의 간선만 있는 것이 아니라 여러 개의 간선이 있을 수 있고, 이들 간 거리는 다를 수 있다. 이.. PS(Problem Solving)/BOJ 2022. 7. 25.

• [백준/BOJ] 16398번: 행성 연결 문제 https://www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 해설 최소 신장 트리를 이용하여 푸는 문제이다. 특정 노드부터 시작하라는 말이 없기에 크루스칼 알고리즘을 사용하였다. (꼭 저 말이 있어야만 프림 알고리즘을 사용할 수 있는 것은 아니지만, 크루스칼 알고리즘의 성능이 더 좋다.) 보통의 크루스칼 알고리즘 문제들은 연결되는 두 노드와 간선의 비용을 입력하도록 한다. 하지만 이 문제에서는 모든 행성이 연결되어 있고, 각각의 행성마다 비용을 입력하.. PS(Problem Solving)/BOJ 2022. 7. 24.

• 

  [알고리즘] 프림 알고리즘(Prim Algorithm) 프림 알고리즘 무방향 연결 그래프가 주어졌을 때, 최소 신장 트리를 찾기 위한 알고리즘이다. 크루스칼 알고리즘과의 목적은 같지만, 언제 어떻게 사용하느냐에 따라 효율성이 달라질 수 있다. 크루스칼 알고리즘에 관해서는 크루스칼 알고리즘을 참고하면 된다. 크루스칼 알고리즘과 마찬가지로 프림 알고리즘도 그리디 알고리즘(Greedy Algorithm)의 일종이다. 크루스칼 알고리즘은 간선의 가중치를 오름차순으로 정렬해서 가장 작은 가중치를 가진 간선부터 선택해나갔다. 프림 알고리즘은 임의의 시작 정점에서 정점을 추가해가며 단계적으로 트리를 확장시키는 기법이다. 프림 알고리즘의 동작 위에서도 말했듯이, 프림 알고리즘은 그리디 알고리즘의 일종이다.' 즉, 탐색 정점과 연결된 인접 정접들 중 가중치가 가장 적은 간선.. Algorithm 2022. 7. 24.

• [백준/BOJ] 11725번: 트리의 부모 찾기 문제 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 해설 DFS를 이용하여 해결할 수 있는 문제이다. 트리 상에 연결되는 두 정점이 부모-노드 구분이 없기 때문에 양방향으로 넣어줘야한다. 또한 문제에서 트리의 루트를 1이라고 정했기 때문에, 1은 먼저 방문처리 해준 후, DFS를 실행시킨다. 소스 코드 private lateinit var arr: Array private lateinit var parent: IntArray private lateinit var visited: BooleanArray fu.. PS(Problem Solving)/BOJ 2022. 7. 23.

• [백준/BOJ] 1197번: 최소 스패닝 트리 문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 해설 최소 신장 트리의 기본적인 문제이다. 크루스칼 알고리즘과 프림 알고리즘으로 해결이 가능한데, 나는 우선 크루스칼 알 고리즘을 이용하여 해결하였다. 크루스칼 알고리즘은 가중치가 가장 작은 간선부터 선택해 나가는 알고리즘이다. 자세한 설명은 아래를 참고하면 된다. https://jjunsu.tistory.com/221 [알고리즘] 크루스칼 알고.. PS(Problem Solving)/BOJ 2022. 7. 22.

• 

  파이썬: 딕셔너리(dictionary), 셋(set) 딕셔너리(dirtionary) 딕셔너리는 리스트와 비슷하다. 다른 점은 항목의 순서를 따지지 않고, 오프셋을 이용해서 항목을 선택할 수 없다. 대신 값에 상응하는 고유한 키를 지정한다. 딕셔너리는 다른 언어들의 맵(map)과 같다. 맵과 같이 "키(key) - 값(value)" 쌍을 요소로 갖는 컬렉션이다. 딕셔너리 생성하기: { } 딕셔너리를 생성하기 위해서는 중괄호({ }) 안에 콤마로 구분된 키 : 값 쌍을 지정한다. { } 안에 아무 값도 없다면 빈 딕셔너리이다. >>> empty_dict = {} >>> empty_dict {} >>> dict = {1: 2, 2: 4, 4: 8} >>> dict {1: 2, 2: 4, 4: 8} 딕셔너리로 변환하기: dict( ) dict() 함수를 사용하면 .. Programming/Pyhton 2022. 7. 22.

• [백준/BOJ] 1922번: 네트워크 연결 문제 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 해설 최소 비용을 구하는 문제로 최소 신장 트리를 이용하면 된다. 최소 신장 트리를 구현하는 방법으로는 크루스칼 알고리즘과 프림 알고리즘이 있는데, 나는 이 중 크루스칼 알고리즘을 이용하여 문제를 해결하였다. 크루스칼 알고리즘에 대해서는 밑의 글을 확인해보는 것을 추천한다. https://jjunsu.tistory.com/221 [알고리즘] 크루스칼 알고리즘(Kruscal Algorithm) 크루스칼 알고리즘(Kruskal Algorithm) 크루스칼 알고리즘은 그리디 알고리즘(G.. PS(Problem Solving)/BOJ 2022. 7. 22.

• 

  [알고리즘] 크루스칼 알고리즘(Kruscal Algorithm) 크루스칼 알고리즘(Kruskal Algorithm) 크루스칼 알고리즘은 그리디 알고리즘(Greedy Algorithm)의 일종이다. 크루스칼 알고리즘은 가중치가 가장 작은 간선으로부터 시작한다. 위에서 보았던 연결 그래프를 예시로 크루스칼 알고리즘의 과정을 보자. 우선 간선을 가중치 오름차순 순으로 정렬시킨다. 1-2 간선부터 선택을 한다. 다음으로 2-4 간선을 선택한다. 다음으로는 1-4 간선이다. 하지만 1-4 간선을 연결하게 되면 사이클이 이루어진다. 따라서 이 간선은 건너뛴다. 다음으로는 1-3 간선을 선택한다. 3-4를 선택하면 사이클이 되므로 종료한다. 사이클 판단하기: Union-Find 위의 과정을 보면, 사이클이 발생해 패스했던 부분이 있다. 이를 구현할 때 사용하는 거이 Union-F.. Algorithm 2022. 7. 21.