전체 글282 2109. 순회강연 (Python) 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 풀이 뒤에 날짜부터 앞으로 이동해가며 현재 날짜에 강연할 수 있는 강연 리스트 중 가장 높은 강연료를 받을 수 있는 강연을 선택하도록 구현하면 된다. 이를 위해 두 개의 최소힙을 사용하여 하나의 힙에는 모든 강연을 담아두고 뒤에 날짜에 있는 강연들을 하나씩 꺼내가며 현재 날짜에 강연이 가능한 강연들의 강연료에 대하여 또 다른 최소힙에 담아주고 날짜가 바뀔 때마다 해당 최소힙에서 가장 높은 강연료를 꺼내어 더해나간다. 코드 im.. 2022. 7. 3. 13023. ABCDE (Python) 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 풀이 dfs를 사용하여 깊이가 5인 경우가 있는지를 체크하면 된다. 방문체크 부분에서 주의할 건 재귀함수 내에서 방문했던 지점에 대해서 False 처리를 해줘야 한다는 것이다. 그렇지 않으면 모든 경로를 탐색할 수 없게 되어 깊이가 5인 경로가 있음에도 해당 경로를 찾지 못하는 반례가 생길 수 있다. 코드 import sys input = sys.stdin.readline # n: 현재 사람 번호, depth: 깊이 def dfs(n, depth): if depth == 5: # 깊이가 5인 지점에 도달하면 1출력하고 프로그램 종료 print('1') sys.exit.. 2022. 6. 30. 4386. 별자리 만들기 (Python) 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 풀이 모든 별들이 사이클이 없는 그래프로 연결되어 있으면 된다. 즉, N개의 별이 있을 때 N-1개의 간선을 사용하여 연결하는 최소 스패닝 트리를 구하면 된다. 최소 스패닝 트리를 만들기 위해서 사용되는 알고리즘에는 크루스칼 알고리즘과 프림 알고리즘이 있다. 일반적으로 크루스칼 알고리즘은 정점에 비해 간선의 개수가 적을 때 사용하면 좋고 프림 알고리즘은 정점에 비해 간선의 개수가 많을 때 사용하면 좋다. 해당 문제는 모든 별들끼리의 길이를 구한 후 최소 스패닝 트.. 2022. 6. 27. 4803. 트리 (Python) 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 풀이 dfs를 통해서 연결된 그래프에 사이클이 있는지를 판단한다. 현재 정점과 연결되어 있는 정점 중 이미 방문한 정점이 있다면 이는 사이클이 존재하는 그래프임을 의미하므로 트리가 될 수 없다. 한 가지 주의할 건 dfs 함수를 호출할 때 현재 정점으로 오기 전에 있었던 정점의 정보를 같이 전달해서 사이클 유무를 판단할 때 해당 정점을 제외하고 판별할 수 있게 해야 한다. 코드 import sys input = sys.stdin.readline.. 2022. 6. 26. 1719. 택배 (Python) 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 풀이 플로이드 워셜 알고리즘을 사용하여 해결할 수 있다. 기존의 플로이드 워셜 알고리즘에서 최단거리를 기록하는 graph 배열에 첫 번째로 방문하는 집하장 정보를 추가한다. i에서 j로 가는 경로가 k 집하장을 거쳐서 가는 경로의 길이로 갱신될 때 graph[i][k]에 기록되어 있는 첫 번째로 방문하는 집하장 정보를 graph[i][j]에 기록해주면 된다. 코드 import sys input = sys.stdin.readline INF = float('inf') if .. 2022. 6. 24. 16398. 행성 연결 (Python) 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 풀이 크루스칼 알고리즘을 사용하여 최소 스패닝 트리를 만들면 된다. 크루스칼 알고리즘에 대해서 간단히 설명하자면 입력으로 주어진 간선 정보를 비용을 기준으로 오름차순 정렬한다(우선수위 큐를 사용하면 된다). 비용이 낮은 순으로 간선을 꺼내어 해당 간선을 사용했을 때 그래프에 사이클이 발생하는지 체크한다. 사이클이 발생하지 않을때만 해당 간선을 사용하여 그래프를 완성해 나간다. 이를 반복하여 총 N개의 정점이 있을 때 N-1개의 간선을 사용했다면 모든 정점이 사이클.. 2022. 6. 23. [iOS] CGPoint, CGSize, CGRect 화면에 View를 그릴 때 필요한 정보에는 무엇이 있을까? 일단 View를 화면의 어느 위치에 놓을지를 결정해야 한다. 그리고 그 위치에서 크기를 어느 정도로 할지를 결정해야 한다. 정리하면, View를 그리기 위해 필요한 정보에는 View의 시작 위치에 대한 (x, y) 좌표가 필요하고 (x, y) 좌표에서 어느 크기만큼 그릴 건지 width, height에 대한 정보가 필요하다. View를 그릴 때 이러한 정보들을 담아두기 위한 구조체들을 살펴보자. CGPoint - View의 시작 위치 CGPoint 구조체는 2차원 좌표계의 점을 포함하는 구조체이다. CGPoint는 다음과 같의 정의되어 있다. CGPoint 구조체 안에는 x, y라는 변수가 선언되어 있다. 두 변수 안에 원하는 값을 넣어 View.. 2022. 6. 22. 2342. Dance Dance Revolution (Python) 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 풀이 3차원 dp를 사용하여 재귀 함수를 통해 답을 구할 수 있다. 3차원 배열인 dp에는 다음과 같은 정보가 저장된다. dp[left][right][idx] : idx번째 지시사항에서 왼발이 left에 오른발이 right 위치에 있을 때 사용되는 최소의 힘 왼발과 오른발을 모두 이동시켜가며 dp 배열에 최솟값이 저장되도록 구현해주면 된다. 다만 지시사항이 요구하는 위치가 왼발 또는 오른발과 같은 위치라면 두 발을 모두 이동시킬.. 2022. 6. 20. 9252. LCS 2 (Python) 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 LCS를 구하는 알고리즘(참고)을 그대로 적용하여 해결하면 된다. 추가적으로 최장 길이에 해당하는 문자열도 구해야 하는데 추가적으로 2차원 리스트를 하나 만들어서 문자열을 기록해 나가면 된다. 생각해 보니까 걍 2차원 리스트 하나만 써도 돼서 하나만 썼다. dp 배열 하나만 쓰고 여기에 문자열을 기록하고 길이는 len()을 사용했다. 두 문자열 A와 B가 있을 때 A의 i번째 문자와 B의 j번째 문자가 같다면.. 2022. 6. 20. 이전 1 2 3 4 5 ··· 32 다음
