본문 바로가기

알고리즘문제

 (14)
[소수의 판별] 프로그래머스 L1 '소수 찾기' (Python) https://programmers.co.kr/learn/courses/30/lessons/12921 코딩테스트 연습 - 소수 찾기 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.) 제한 조건 n은 2이상 programmers.co.kr 1. 에라토스테네스의 체 공식으로 소수 구하기 def solution(n): answer = 0 # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주) sieve = [True] * (n+1) # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사 m = int(n ** 0.5) for i in ran..
[기타] 프로그래머스 L1 '약수의 합' (Python) https://programmers.co.kr/learn/courses/30/lessons/12928 코딩테스트 연습 - 약수의 합 정수 n을 입력받아 n의 약수를 모두 더한 값을 리턴하는 함수, solution을 완성해주세요. 제한 사항 n은 0 이상 3000이하인 정수입니다. 입출력 예 n return 12 28 5 6 입출력 예 설명 입출력 예 #1 12의 약수 programmers.co.kr 1. n이 0 또는 1일 때 약수는 0과 1뿐이다. 2. 2이상 약수는 1을 반드시 포함하므로, 1부터 반복문을 돌린다. 3. n//i이 i보다 작을 때 반복문을 멈춘다. (ex. 12//4 < 4) 4. n//i이 i와 같고, n/i==0일 때 i 값을 더하고 반복문을 멈춘다. (ex. 4/2==2) 5. ..
[동적계획법] 난이도2, 이취코 220p '개미 전사' (Python) 개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 되어 있다. 각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이때 메뚜기 정찰병은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 예를 들어 식량창고 4개가 다음과 같이 존재한다고 가정하자. {1, 3, 1, 5} 이때 개미 전사는 두 번째 식량창고와 네 번째 식량 창고를 선택했을 때 최댓값인 8개의 식량을 빼앗을 수 있다..
[다익스트라] 난이도2, USACO '숨바꼭질' (Python) 동빈이는 숨바꼭질을 하면서 술래로부터 잡히지 않도록 숨을 곳을 찾고 있습니다. 동빈이는 1~N번까지의 헛간 중에서 하나를 골라 숨을 수 있으며, 술래는 항상 1번 헛간에서 출발합니다. 전체 맵에는 총 M개의 양방향 통로가 존재하며, 하나의 통로는 서로 다른 두 헛간을 연결합니다. 또한 전체 맵은 항상 어떤 헛간에서 다른 어떤 헛간으로 도달이 가능한 형태로 주어집니다. 동빈이는 1번 헛간으로부터 최단 거리가 가장 먼 헛간이 가장 안전하다고 판단하고 있습니다. 이때 최단 거리의 의미는 지나야 하는 길의 최소 개수를 의미합니다. 동빈이가 숨을 헛간의 번호를 출력하는 프로그램을 작성하세요. 첫째 줄에는 N과 M이 주어지며, 공백으로 구분합니다. (2
[플로이드워셜] 백준 11404번 '플로이드' (Python) https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 모든 도시에 대한 비용을 구해야 하므로 플로이드 워셜 알고리즘 활용 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있으므로, 최소비용인 노선을 그래프에 입력 노선이 없으면 비용을 0으로 처리 '''입력 예시 5 14 1 2 2 1 3 3 1 4 1 1 5 10 2 4 2 3 4 1 3 5 1 4 5 3 3 5 10 3 1 8 1 4 2 5 1 7 3 4 2 5 2 4 ''' n = in..
[탐욕법] 프로그래머스 L2 '구명보트' (Python) https://programmers.co.kr/learn/courses/30/lessons/42885 코딩테스트 연습 - 구명보트 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 5 programmers.co.kr people이 정렬이 되어있지 않으므로 정렬 시킴 3~5 반복 해당 몸무게가 limit의 반 값보다 작고 people의 마지막 몸무게라면 answer에 1을 더하고 반복문 종료 해당 몸무게와 people의 마지막 몸무게를 합한 값이 limit보다 작으면 answer에 1을 더하고 마지막 몸무게 삭제 해당 몸무게와 people의 마지막 ..
[재귀함수] 프로그래머스 L2 '괄호 변환' (Python) https://programmers.co.kr/learn/courses/30/lessons/60058 코딩테스트 연습 - 괄호 변환 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 programmers.co.kr 균형 잡힌 괄호 문자열과 올바른 괄호 문자열을 확인하는 함수를 각각 생성한다. 결괏값을 도출할 수 있는 조건이 문제에 자세히 쓰여 있으므로 하나씩 코드를 짠다. #1차시도 - 테스트 2,4,6,7,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25 def solution(p): answer = '' w="" for i in p..
[재귀함수] 백준 10872번 '팩토리얼' (Python) https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net N! = 1*2*3*...(N-1)*N n이 1 또는 0일 때 1을 반환함 for문 보다 효율적인 재귀 함수 사용 ''' 10 0 ''' n = int(input()) def fac(n): if n==1 or n==0: return 1 return n * fac(n-1) print(fac(n))
LIST

티스토리툴바