문제 출처 : www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 1 . 문제 접근 방식 - 그리디 알고리즘의 대표적인 방법이라고 할 수 있다. 그리디 알고리즘이란 경우의 수가 많은 경우 가장 최적의 답을 선택해서 진행하는 방식을 말한다. 먼저, 기름값을 가장 핵심으로 생각했다. 출발 시에는 어쩔수 없이 주유를 하고 출발해야하지만 분명 기름값이 더 싼 곳은 존재할 것이다. 이를 이용하여 기름값의 배열을 돌며 작아질 경우에는 기름값을 재할당하며 거리..
파이썬3에서 입력받는 방법은 두 가지가 있다. 첫 번째는 가장 흔히 쓰이는 input()을 이용하는 것이다. 간단하게 알아보자. # 정수를 입력받고 싶을 때 N = int(input()) # 두 개의 정수를 입력받고 싶을 때 a, b = int(input().split()) # map함수를 이용하여 정수형태로 입력 받아 list에 저장 A, B = list(map(int, input().split())) 위와 같은 방법처럼 하나의 정수를 입력받을 수도 있고 여러 개의 정수를 입력받는 방법이 있다. 하지만 이러한 방법만 있는 것이 아니라는 말을 듣고 그에 대해 알아보려 한다. 새롭게 알게 된 방법은 두 번째로 sys.stdin.readline()을 이용하는 방법이다. 이 방식을 이용하기 위해서는 코드 첫 ..
Chapter2 - 재귀 2.1 재귀 알고리즘 재귀(Recursion) : 문제에 대한 해결을 할 때 일부만 답하고 나머지는 또 다른 문제로 남겨두는 것 재귀 호출(Recursive Call) : 알고리즘이 자기 자신을 호출하는 것 Alg sum(n) 1. if (n = 1) {base case} return 1 else {recursion} return n + sum(n-1) 재귀 케이스(recursive case) : 재귀호출은 반드시 원래 문제보다 작은 문제들을 대상으로 해야함 베이스 케이스(base case) : 부문제들이 작아지면 직접 해결 2.2 재귀의 작동원리 재귀와 관련된 내부 처리는 컴퓨터 내부에서 자동 수행 대기중인 호출들은 시스템 Stack에 저장되었다가 꺼내짐 2.3 재귀의 기본 규..
Chapter1 - 알고리즘 분석 1.1 실행시간 알고리즘(Algorithm) : 주어진 문제를 일정 시간내에 해결하는 단계적 절차 자료구조(Data Structure) : 데이터를 효율적으로 관리하기 위한 구조 좋은 알고리즘 : 실행 시간이 짧고 메모리를 적게 요구하는 알고리즘 1.1.1 평균 실행 시간과 최악 실행 시간 실행 시간의 종류 최선 실행 시간(best-case running time) 평균 실행 시간(average-case running time) 최악 실행 시간(worst-case running time) : 분석이 용이하고 유용성을 평가하는 가장 결정적인 요소 1.1.2 실행 시간 구하기 실험적 방법 실제 알고리즘을 구현하고 입력 값을 다양화 하며 측정하는 방법 모든 데이터를 입력할 수..
