본문 바로가기

Archived(CSE Programming)/알고리즘(Python)

 (17)
프로그래머스 - 소수 찾기(파이썬, LV2, 완전탐색) https://programmers.co.kr/learn/courses/30/lessons/42839?language=python3# 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 풀이 파이썬의 itertools의 permutation을 통해서 쉽게 구현이 가능했다. 먼저 모든 순열을 다 고려하는데, 만들어진 순열 String을 Integer로 변경하고 해당 Integer가 소수 Prime 인지 체크해서 개수를 카운트해주면 된다. 이 때, 중복 값 방지를 위해 개수 카운트 시 집합을 활용한다...
커리큘럼(파이썬) / 위상 정렬(topology sort) 문제 온라인 컴퓨공학강의를 듣고 있다. 이 때, 각 온라인 강의는 선수강의가 있을 수 있다. 1번부터 N번 까지 강의가 주어지고 그에 따른 선수강의가 있을 경우, 각 강의를 듣는데 걸리는 시간을 모두 출력하라. 입력 첫째 줄에 동빈이가 듣고자 하는 강의 수 N이 주어진다(1 0 -> 3 일 경우 다시 0을 파싱하지 않아서 무한루프를 돈다. import sys from collections import deque sys.stdin = open("input/input_10-4.txt" ,"r") sys.stdout = open("ouput_10-2.txt", "w") # input n = int(input()) answer = [0] * (n) prev_list = [] visit = [] # main fo..
[백준 1647번] 도시 분할 계획(파이썬) / 크루스칼(MST) 문제 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 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다. 마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 각 길마다 길을 유지하는데 드는 유지비가 있다. 마을의 이장은 마을을 두 개의..
팀 결성(파이썬) / 사이클 체크 문제 학교에서 학생들에게 0번부터 N번까지 팀 번호를 부여ㅑ했다. 모든 학생이 다른 팀으로 시작하는데 이 때, 연산을 통해서 팀이 결성된다. 1. '팀 합치기' 연산은 두 팀을 합치는 연산이다. 2. '같은 팀 여부 확인' 연산은 특정한 두 학생이 같은 팀에 속하는지를 확인하는 연산이다. 선생님이 M개의 연산을 수행할 수 있을 때, '같은 팀 여부 확인' 연산에 대한 연산 결과를 출력해라. 입력 첫째 줄에 N, M(연산횟수) 이 주어진다(1
전보 (파이썬) / 최단경로(다익스트라) 문제 어떤 나라에 N개의 도시가 있다. X에서 Y로 향하는 통로가 있으면 X->Y는 보낼 수 있지만 Y->X로는 따로 통로가 있어야 한다. 특정 도시에서 다른 도시로 전부 전보를 보내기 위해서 필요한 시간은 얼마인지 계산하라. 입력 첫째 줄에 도시의 개수 N, 통로의 개수 M, 메세지를 보내고자 하는 도시 C가 주어진다. (1
미래 도시(파이썬) / 최단경로 그래프 문제 방문원 A는 1에 있는데 K번에 있는 사람과 소개팅을 한다고 한다. 그리고 방문원 A는 X 회사로 가야한다. 즉, 소개팅을 할 K번 회사를 방문 후에 X 회사에 최종 도착해야 한다. 이 때, 총 N개의 도시와 M개의 도로가 주어질 경우 A가 갈 경로의 최단 거리를 구하라 입력 첫째 줄에 전체 회사의 개수 N과 경로의 개수 M이 공백으로 구분되어 차례대로 주어진다(1= INF: print(-1) else: print(graph[1][k] + graph[k][x])
효율적인 화폐 구성 (파이썬) / DP(다이나믹 프로그래밍) 문제 N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 화폐는 몇 개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 예를 들어 2원, 3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다. "INPUT" 2 15 2 3 "OUTPUT" 5 "INPUT" 3 4 3 5 7 "OUTPUT" -1 입력 첫째 줄에 N,M이 주어진다(1
떡볶이 떡 만들기(파이썬) / 이진탐색 문제 오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다 절단기에 높이(H) 를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다 예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm이다. 손님은 6cm만큼의 길이를 가져간다 손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을..

티스토리툴바