분류 전체보기282 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 6 ··· 47 다음
