Algorithm/Baekjoon117 1011. Fly me to the Alpha Centauri (Python) 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 풀이 간단한 규칙을 찾아서 적용하면 된다. 위의 그림을 보면 규칙을 찾을 수 있다. 4번 작동했을 때 최대로 움직일 수 있는 거리는 6이고, 5번 작동했을 때 최대로 움직일 수 있는 거리는 9이다. 그렇기 때문에 만약 입력으로 주어진 x와 y의 거리가 7~9일 경우에는 최소 5번의 공간이동 장치 작동으로 이동할 수 있음을 알 수 있다. 기준이 되는 거리를 보면 +1 +1 +2 +2 +3 +3 +4 +4 +5 +5..... 2022. 4. 5. 1765. 닭싸움 팀 정하기 (Python) 1765번: 닭싸움 팀 정하기 1번 학생 혼자 팀, 2, 4, 6번 학생 셋이서 팀, 3, 5번 학생 둘이서 팀일 때, 팀의 개수가 최대이다. www.acmicpc.net 풀이 유니온 파인드를 통해서 친구 사이인 학생끼리 유니온으로 묶어주는 작업을 해주면 된다. 첫 번째 조건인 '내 친구의 친구는 내 친구이다'의 경우는 친구 관계가 주어진 학생들을 유니온으로 묶어주면 간단히 해결할 수 있다. 두 번째 조건인 '내 원수의 원수도 내 친구이다'의 경우는 따로 원수 관계를 저장하는 2차원 배열을 만들고 모든 학생에 관하여 자신의 원수 관계를 저장해놓고 자신의 원수의 원수인 학생과 유니온을 해주면 친구 관계를 형성할 수 있다. 코드 import sys from collections import defaultdi.. 2022. 4. 5. 1800. 인터넷 설치 (Python) 1800번: 인터넷 설치 첫 번째 줄에 N(1 ≤ N ≤ 1,000), 케이블선의 개수 P(1 ≤ P ≤ 10,000), 공짜로 제공하는 케이블선의 개수 K(0 ≤ K < N)이 주어진다. 다음 P개의 줄에는 케이블이 연결하는 두 컴퓨터 번호와 그 가격이 차 www.acmicpc.net 풀이 이분탐색과 다익스트라를 결합하여 해결하는 문제다. 과정은 다음과 같다. 1. 먼저 이분탐색을 통해 기준이 되는 가격을 설정한다. 2. 그 후 다익스트라를 통해서 1번과 N번을 연결한다. 3. 이 때, 기존에는 dist 배열에 시작 지점부터 해당 지점까지의 최단 거리를 넣어줬는데 이번 문제에서는 기준 가격을 넘는 케이블을 몇 개 사용했는지를 담는다. 4. 마지막에 dist[N]의 값이 공짜로 제공되는 케이블선의 개수인.. 2022. 4. 4. 10159. 저울 (Python) 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 풀이 플로이드 워셜을 사용하여 구현할 수 있다. a > b, b > c일 경우 a > c라는 개념을 사용한다. 코드 import sys input = sys.stdin.readline INF = float('inf') if __name__ == '__main__': N = int(input()) # 물건의 개수 M = int(input()) # 미리 측정된 물건 쌍의 개수 # comparison[i][j] = 1 --------------.. 2022. 4. 2. 4256. 트리 (Python) 4256번: 트리 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 노드의 개수 n이 주어진다. (1 ≤ n ≤ 1,000) BT의 모든 노드에는 1부터 n까지 서로 다른 번호가 매겨져 있다. 다음 www.acmicpc.net 풀이 각 순회의 특징을 파악하여 문제를 해결하면 된다. 전위 순회는 부모 노드가 자식 노드의 앞에 출력되고 중위 순회는 부모 노드가 왼쪽 자식 노드와 오른쪽 자식 노드 사이에서 출력된다. 그렇기 때문에 전위 순회 결과의 앞부분을 기준으로 중위 순회 결과에서 재귀 함수를 사용하여 왼쪽과 오른쪽을 하나의 노드가 남을 때까지 쪼개주고 마지막에 출력 작업이 이뤄지도록 하면 된다. 문제의 예제를 통해 살펴보면 다음과 같다. 위와 같이 재귀 함수는 다음과 같은 .. 2022. 3. 26. 3745. 오름세 (Python) 3745번: 오름세 입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다. www.acmicpc.net 풀이 간단하게 최장 증가 부분 수열(Longest Increasing Subsequence, LIS)을 활용하여 해결하는 문제이다. 문제 알고리즘 자체는 어려울게 없으나 입력에 따로 종료하는 부분이 주어지지 않아 그 부분만 해결하면 된다. 파이썬에서는 try 구문을 사용하여 exception이 발생했을 때 입력이 종료되도록 해주면 된다. 코드 import sys from bisect import bisect_left input = sys.stdin.readli.. 2022. 3. 23. 이전 1 ··· 10 11 12 13 14 15 16 ··· 20 다음
