본문 바로가기

두두의 알고리즘

 (145)
[탐욕법] 프로그래머스 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))
[재귀함수] 백준 10829번 '이진수 변환' (Python) https://www.acmicpc.net/problem/10829 10829번: 이진수 변환 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000,000,000,000) www.acmicpc.net 10진수를 2진수로 바꿔주는 bin() 메서드 사용 bin() 메서드는 앞에 0b가 붙으므로 replace() 메서드로 제거 ''' 53 ''' n = int(input()) k = bin(n) print(k.replace("0b","")) 재귀 함수로도 풀어보기 10진수에서 2진수로 바꿀 때 지수 말고 몫, 나머지 활용하기
[알고리즘] 재귀함수 - (팩토리얼(Factorial) / 피보나치 수열(Fibonacci)) 재귀 함수란? 메서드/함수의 내부에서 자기 자신의 메서드/함수를 다시 호출하는 함수 Fractal 구조. Sierpinski Triangle 재귀 함수의 특징 재귀 함수 초반에 등장하는 조건문이 종료 조건 역할을 수행 재귀 함수는 내부적으로 스택 자료구조와 동일함 재귀 함수는 최대 1000번까지 가능 코드의 간결화 및 변수 사용 최소화를 위해 사용함 재귀 함수의 예 [인덱스의 모든 합] 성분들의 합으로 표현할 수 있는 숫자의 경우의 수는? #8 → 부분집합의 개수 2en → 3,5,8이 선택이 되느냐 안되느냐니까 각 수마다 2가지 경우가 있다 → 단, 3+5 = 8이므로 중복됨 #반복문 data = [3,5,8] result = set() for i in range(2): for j in range(2)..
[해시] 프로그래머스 L2 '전화번호 목록' (Python) https://programmers.co.kr/learn/courses/30/lessons/42577 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 한 번호가 다른 번호의 접두어인 경우를 확인하면 되므로 정렬시켜서 바로 앞, 뒤만 비교 #1차시도 - 테스트 13 실패, 효율성 1,2,3,4 실패 def solution(phone_book): answer = True dic = dict() for idx,i in enumerate(sorted(phone_book)): dic[i] = idx for i in..
[해시] 프로그래머스 L1 '완주하지 못한 선수' (Python) https://programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 동명이인을 구분하기 위해 참가자의 이름별로 1씩 더한다. (동명이인이라면 2가 되니까) 완주자 명단에 있는 이름은 1을 뺀다. 완주하지 못한 사람은 한 명뿐이므로 값이 1인 이름을 출력한다. #1차시도 - 정확성 1,3,4,5 효율성 1,2,3,4,5 실패 def solution(participant, completion): answer = ..
[해시] 백준 15829번 'Hashing' (Python) https://www.acmicpc.net/problem/15829 15829번: Hashing APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이의 출력을 내보내는 함수로 정 www.acmicpc.net 아스키코드를 정수로(ord), 정수를 아스키코드로(chr) 변환하는 함수 사용 문제에 나와있는 공식대로 코딩 ''' 5 abcde 3 zzz 1 i ''' import sys input_data = sys.stdin.readline().rstrip() L = int(input_data.split()[0]) S = input_data.split()[1] hash = dict() for idx, i..
LIST

티스토리툴바