문제 https://school.programmers.co.kr/learn/courses/30/lessons/42577 My Solution Idea. any, startswith 이용 def solution(phone_book): ''' string 에서 subset 확인 ''' for phone in phone_book: if any(other_phone.startswith(phone) for other_phone in phone_book if other_phone != phone): return False return True 다른 전화부를 비교하는데 오버헤드 발생 Other’s Solution https://school.programmers.co.kr/learn/courses/30/lessons/..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42576 My Solution Idea 1. remove 사용 def solution(participant, completion): for person in completion: participant.remove(person) return participant[0] list의 remove()는 시간 복잡도가 O(1) ~ O(N) ⇒ 효율성 테스트 통과 불가 Idea 2. dict, counter 사용 from collections import Counter def solution(participant, completion): dict_participant = dict(Counter(partici..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42747 H-Index( 과학자의 생산성과 영향력을 나타내는 지표)를 구하는 문제 H-Index : 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값 Solution 중요 Idea 아무리 인용수(citations) 값이 크더라도 논문 편수가 작으면 H-index 는 작을 수 밖에 없다. ex. [312,521,1021] ⇒ H-index = 3 코드 1 def solution(citations): citations.sort(reverse=True) for h, citation in enumerate(citations, ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42746 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. My Solution (Time Out) Idea1 : Permutation 이용 모든 순열에 대해 시도 ⇒ Time Out from..

파이썬(일부분 코틀린)으로 구현한 알고리즘, 자료구조(이론, 알고리즘 테스트)를 한눈에 볼 수 있도록 유형별로 정리한 게시글입니다. 알고리즘과 자료구조 이론 알고리즘 정렬 파이썬으로 정렬 알고리즘 구현하기 검색 자료구조 정리본 : 파이썬으로 자료구조 구현하기 Hash (해시) Stack (스택) Queue (큐) Heap (힙) 알고리즘 테스트 문제 알고리즘 그리디 알고리즘 정렬 [Programmers] 정렬 - 가장 큰 수 찾기 [Programmers] 정렬 - H Index 자료구조 해시 Python 에서는 Dictionary, Set 이용 [Programmers] 해시 - 완주하지 못한 선수 [Programmers] 해시 - 전화번호 목록 ㅇ

/* 본 게시물은 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [백준] 11399번 - ATM : https://www.acmicpc.net/problem/11399 [백준] 1931번 - 회의실 배정 : https://www.acmicpc.net/problem/1931 1931번 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음..

/* 본 게시물은 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [백준] 13305번 - 주유소: https://www.acmicpc.net/problem/13305 문제 어떤 나라에 N개의 도시가 있다. 이 도시들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 km를 사용한다. 처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는 무제한이어서 얼마든지 많은 기름을 넣을 수 있다. 도로를 이용하여..

/* 본 게시물은 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [백준] 1541번 - 잃어버린 괄호: https://www.acmicpc.net/problem/1541 문제 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고..

/* 본 게시물은 ' 이것이 코딩 테스트다 with Python | 나동빈 ' 의 내용과 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ # 그리디 알고리즘 그리디 알고리즘은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미한다. 코딩 테스트에서 만나게 될 그리디 알고리즘의 문제 유형은 '사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형' 이라는 특징이 있다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시해준다. 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족 시킬 수 있으므로 그리디 알고리즘 문제는 자주 정..

/* 본 게시물은 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [백준] 11729번 - 하노이 탑 이동 순서 : https://www.acmicpc.net/problem/11729 문제 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다..

/* 본 게시물은 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [BoostCourse] 자바로 구현하고 배우는 자료구조 - 힙 정렬 : https://www.boostcourse.org/cs204 힙 정렬 힙 규칙에 맞게 숫자의 순서를 맞추는 과정을 힙 정렬 알고리즘이라고 한다. *힙에 대해 자세히 알고 싶다면 다음 글을 확인하면 된다. 만약 데이터가 힙 규칙에 따라 있다면, trickleDown을 반복하면 숫자들이 정렬된다. 이때 최대힙 이면 오름차순으로, 최소힙이면 내림차순으로 정렬된다. 코드는 다음과 같다. fun heapSort(): E{ val removeVal = array[1] as E if (arr..

/* 본 게시물은 참고자료를 토대로 작성되었습니다. */ /* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */ 참고 자료 [백준] 1436번 - 영화감독 숌 : https://www.acmicpc.net/problem/1436 문제 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다. 하지만 숌..