Python

1. 그래프의 개념 - 인접 행렬 / 인접 리스트그래프: 노드(vertex)와 간선(edge)을 이용한 비선형 데이터 구조보통 그래프는 데이터 간의 관계를 표현하는 데 사용데이터를 노드로, 노드 간의 관계나 흐름을 간선으로 표현하며, 간선은 방향이 있을 수도 있고 없을 수도 있음만약 관계나 흐름에서 정도를 표현할 필요가 있다면 가중치(weight)라는 개념을 추가하여 표현그래프의 구현 방식에는 인접 행렬(adjacency matrix)과 인접 리스트(adjacency list)가 있음 인접 행렬은 배열을 활용하여 구현하는 경우가 많음이때 배열의 인덱스는 노드, 배열의 값은 노드의 가중치로 생각하고, 인덱스의 세로 방향을 출발 노드, 가로 방향을 도착 노드로 생각하면 자연스럽게 그래프를 표현할 수 있음예:..

** 이것이 취업을 위한 코딩테스트다 with 파이썬 서적을 바탕으로 작성한 글입니다. - 코딩테스트에서의 구현(Implementation) : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 어떤 문제를 풀든지 소스코드를 작성하는 과정은 필수이므로 구현 문제 유형은 모든 범위의 코딩테스트 문제 유형을 포함하는 개념이다. 흔히 구현 유형의 문제는 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 의미한다. [구현하기 어려운 문제 유형]- 알고리즘은 간단하지만 코드가 지나치게 길어지는 문제- 특정 소수점까지 출력해야하는 문제- 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야하는 파싱 문제등 사소한 조건 설정이 많은 경우에 코드로 구현하기 까다롭다고 볼 수 있다. [구현 ..

먼저 기존에 무게 limit에 포커스를 두었던 방식으로 풀었다가 틀린 버전의 코드를 보면서 분석을 작성해보겠다. [1차 시도 (실패)]def solution(people, limit): boat = 0 people.sort() # 오름차순 : [50, 50, 70, 80] temp = limit for man in people: if limit >= man: # 태울 수 있는 경우 limit -= man else: # 태울 수 없어서 새 보트 필요 boat += 1 # 지금까지 태운 사람들 용 보트 +1 limit = temp # limit 다시 초기화 ..

[문제 분석]1. 부서별 신청 금액 배열 d를 오름차순 정렬2. d금액이 높은 부서부터 한 번씩 할당하고 다음 부서로 넘어간다.3. 과정 2를 budget의 한계가 될 때까지 수행한다. 문제에서 "최대한 많은 부서를 지원"하는 것이 목적이라고 명시했으므로 그리디 알고리즘이라고 볼 수 있다.다만 그동안의 기본 배낭 문제와 같은 문제들에서는 '가치' 혹은 여기서는 '지원 금액'이 많은 것을 목표로 했기에 입력 시퀀스를 내림차순 정렬하여 진행했었지만, 해당 문제에서는 금액에 포커스를 두는 것이 아닌 최대한 많은 부서를 지원하는 것이 목표이므로 오름차순 정렬을 진행하겠다. 또 하나의 포인트는 "물품을 구매할 때는 각 부서가 신청한 금액 만큼은 모두 지원"해야 한다는 부분인데, 이를 통해 0/1 배낭 문제와 같이..

** '코딩테스트 합격자 되기 파이썬편' 서적을 바탕으로 작성한 글입니다. ** 1. 그리디 알고리즘의 개념 '그리디(greedy)'란 '탐욕스러운/욕심이 많은' 이라는 의미이다.그리디 알고리즘은 문제 해결 과정에서 결정 순간마다 눈 앞에 보이는 최선의 선택을 하며 선택은 번복하지 않는다.이에 따라 그리디 알고리즘은 "지역 최적해"를 추구한다고 말하기도 한다. 즉, 부분벅으로는 최적해를 구한다고 할 수 있어도 전체적으로 최선의 해라고는 말할 수 없다는 특징을 갖고 있다. 손님에서 8원을 거슬러 줘야 하는데 계산원이 보유한 동전의 종류가 5, 4, 1뿐이라고 가정해보자.이때 '동전의 개수를 가장 적게' 만들기 위한 task에서 그리디 알고리즘을 활용해보자. 그리디 알고리즘은 "현재 상황에서 가장 최선의..

엡실론(Epsilon)이란, 컴퓨터에서 부동소수점 숫자 연산의 '정확도 한계'를 나타내는 개념이다.이 값은 매우 작은 숫자로, 두 부동소수점 숫자가 실제로는 같아야 하지만 컴퓨터에서 계산된 값에 오차가 있을 때 그 오차의 크기를 측정하는 데 사용된다. 파이썬에서는 sys.float_info.epsilon 을 통해 이 값을 확인할 수 있으며, 이는 64비트 부동소수점에서 가장 작은 양의 숫자이다.import sysprint(sys.float_info.epsilon) # 2.220446049250313e-16 예를 들어 10.0 % 3.2 를 하면 0.4가 아니라 0.39999999999999947 이 나오는데, 그 이유는 다음과 같다. 1. 부동 소수점 표현의 한계- 컴퓨터는 소수를 이진수로 변환하여 저..