갬미의 성장일기

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다. 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. 위에서 아래로 문제 하나의 수열에는 다양한 수가 존재한다, 이러한 수는 크기에 상관없이 나열되어 있다. 이수를 큰수부터 작은수의 순서로 정렬해야한다. 수열을 내림차순으로 정렬하는 프로그램을 만드시오 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. 계수 정렬 문제에서 요구하는 조건에 따라 적절한 정렬 알고리즘을 사용하지 않으면 프로그램이 비효율적으로 동작하게 되고 자연스럽게 정렬을 공부하다 보면 알고리즘의 효율의 중요성을 쉽게 이해할 수있다. 정렬 종류 ..

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다. Chapter 5 DFS/BFS 오늘 풀이한 문제 1. [백준 14888] 연산자 끼워넣기 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제 설명 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는..