전체글397

• 

  파이썬: 반복문(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.