갬미의 성장일기

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다. Chapter 7 이진탐색 오늘 풀이한 문제 - 이진탐색 예제 [이코테 197p] 부품찾기 문제 동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개의 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자. 예를 들어 가게의 부품이 총 5개일 때 부품 번호가 다음과 같다고 하자. N=5 [8, 3, 7, 9, 2] 손님은 총 3개의 부품이 있는지 확인 요청했는데 부품 번호는 다음과 같다. M=..

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다. Chapter 7 이진탐색 이진탐색을 학습하기 전, 순차탐색을 먼저 알아야한다. 순차탐색 리스트안에 있는 요소들을 하나씩 탐색하여 특정한 데이터를 찾는 탐색 방법 구현이 간단하고 자주 사용되는 탐색법이다. (파이썬 내장함수 count()도 순차탐색 방법 사용) data = [1,2,3,4,5,6,7,8,9] target = 3 def sequential_search(data, target): for i in range (len(data)): if data[i] == target : return i+1 순차탐색은 정렬과 관계없이 가장 앞의 원소부터 하나씩 확인하는 과정을 거치는 특징이 있다. 순차탐색의 시간 복잡도는 최악..

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다. Chapter 6 정렬 오늘 풀이한 문제 [백준 1715] 카드 정렬하기 문제 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (..

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다. Chapter 6 정렬 오늘 풀이한 문제 - 정렬 실전문제 1. [백준 10825] 국영수 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 문제 도현이네 반 학생 N명의 이름과 국어, 영어, 수학 점수가 주어진다. 이때, 다음과 같은 조건으로 학생의 성적을 정렬하는 프로그램을 작성하시오. 국어 점수가 감소하는 순서로 국어 점수가 같으면 영어 점수가 증가하는 순서로 국어 점수와 영어 점수가 같으면 수학 점수..

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다. Chapter 6 정렬 오늘 풀이한 문제 - 정렬 예제 1. 위에서 아래로 문제 하나의 수열에는 다양한 수가 존재한다, 이러한 수는 크기에 상관없이 나열되어 있다. 이수를 큰수부터 작은수의 순서로 정렬해야한다. 수열을 내림차순으로 정렬하는 프로그램을 만드시오 Data = [15, 27, 12] data = sorted(Data, reverse = True) for d in data: print (d, end = ' ') 2. 성적이 낮은 순서대로 학생 출력하기 문제 N명의 학생 정보가 있다. 학생 정보는 학생의 이름과 성적으로 구분된다. 각 학생의 이름과 성적 정보다 주어졌을때, 성적이 낮은 순서대로 학생의 이름을 출력..

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다. Chapter 6 정렬 정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다 데이터를 가공할때 데이터를 오름차순이나 내림차순으로 정렬하는 과정을 거치는 경우가 많아 정렬 알고리즘은 프로그램을 작성할때 가장 많이 사용되는 알고리즘 중 하나이다. (이진 탐색의 전처리 과정이기도 함!) 이 책에서는 다음 네가지 정렬 알고리즘을 학습한다. 1. 선택 정렬 2. 삽입 정렬 3. 퀵 정렬 4. 계수 정렬 문제에서 요구하는 조건에 따라 적절한 정렬 알고리즘을 사용하지 않으면 프로그램이 비효율적으로 동작하게 되고 자연스럽게 정렬을 공부하다 보면 알고리즘의 효율의 중요성을 쉽게 이해할 수있다. 정렬 종류 ..