본문 바로가기

알고리즘

 (113)
[탐욕법] 프로그래머스 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진수로 바꿀 때 지수 말고 몫, 나머지 활용하기
[해시] 프로그래머스 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..
[자료구조/알고리즘] 해시(Hash) - 해시 테이블, 파이썬 딕셔너리(Python Dictionary) 해쉬 테이블 (Hash Table) 1. 해쉬 구조 * Hash Table: 키(Key)에 데이터(Value)를 저장하는 데이터 구조 - Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 획기적으로 빨라짐 - 파이썬 딕셔너리(Dictionary) 타입이 해쉬 테이블의 예: Key를 가지고 바로 데이터(Value)를 꺼냄 - 보통 배열로 미리 Hash Table 사이즈만큼 생성 후에 사용 (공간과 탐색 시간을 맞바꾸는 기법) - 단, 파이썬에서는 해쉬를 별도 구현할 이유가 없음 - 딕셔너리 타입을 사용하면 됨 2. 알아둘 용어 해쉬(Hash) 임의 값을 고정 길이로 변환하는 것 데이터를 다루는 기법 중 하나로 검색과 저장이 아주 유용한 구조 key와 value 쌍으로 데이터를 저장한다. * 해쉬 테..
LIST

티스토리툴바