구현문제 - 구현문제 : 머릿 속에 있는 알고리즘을 소스코드로 바꾸는 과정 : 풀이를 떠오르는 것은 쉽지만, 소스코드로 옮기기 어려운 문제 - 문제 유형 : 실수 연산, 특정 소수점 출력 문제 : 코드가 길어지는 문제 : 문자열 끊어서 처리하는 문제 : 라이브러리 찾아서 사용해야 하는 문제 상하좌우 문제 여행가 A는 N x N 크기의 정사각형 공간 위에 서 있습니다. 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있습니다. 가장 왼쪽 위 좌표는 (1, 1) 이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당합니다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1) 입니다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있습니다. 계획서에는 하나의 ..

그리디 알고리즘 - 그리디 알고리즘 (탐욕법) : 현재 상황에서 지금 당장 좋은 것만 고르는 방법 : 정당성 분석이 중요! 거스름돈 문제 당신은 음식점의 계산을 도와주는 점원입니다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정합니다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수입니다. [아이디어] - 가장 큰 화폐 단위부터 돈 거슬러주기 (500원 → 100원 → 50원 → 10원 순) [정당성 분석] - 큰 단위가 항상 작은 단위의 배수가 되기 때문에, 가장 큰 화폐 단위부터 거슬러주는 것이 최적의 해 [코드] n = 1260 count = 0 # co..

실전에서 유용한 표준 라이브러리 - 내장 함수 : 기본 입출력 ~ 정렬 함수까지 기본적인 함수들 제공 : import 구문 없이 사용 가능한 함수들 (print, input, ... 등등) : 없어서는 안되는 필수적인 기능들을 포함 - itertools : 파이썬에서 반복되는 형태의 데이터 처리하기 위한 유용한 기능들 제공 : 순열과 조합 라이브러리(완전 탐색 문제) 자주 사용 (모든 경우의 수를 고려해야 할 때 효과적으로 사용) - heapq : 힙(Heap) 자료구조를 제공 : 우선순위 큐 기능을 구현하기 위해 사용(다익스트라 와 같은 최단경로 문제) - bisect : 이진 탐색 기능을 제공 - collections : 덱(deque), 카운터(counter) 등의 유용한 자료구조를 포함 - mat..

함수 함수(Function) : 특정한 작업을 하나의 단위로 묶어 놓은 것을 의미 : 함수를 사용함으로써 코드의 반복을 줄일 수 있다. 함수의 종류 - 내장 함수 : 파이썬이 기본적으로 제공하는 함수 ex) input, print ... - 사용자 정의 함수 : 개발자가 직접 정의하여 사용할 수 있는 함수 함수 정의하기 - 매개변수 : 함수 내부에서 사용할 변수 - 반환 값 : 함수에서 처리된 결과를 반환 - 기본 형태 def 함수명 (매개변수) : 실행할 소스코드 return 반환 값 cf.) def = define의 약자 = 정의하겠다 라는 의미 cf.) 매개변수와 반환 값은 없을 수도 있다. ex) 더하기 함수 예시 def add(a, b): return a+b print(add(3,7)) cf.)..

반복문 반복문 : 특정 코드를 반복적으로 실행할 때 사용하는 문법 → 종류) while문, for문 cf.) for문이 더 간결한 경우가 많다. ex) 1부터 9까지 모든 정수의 합 구하기 (while문) a = 1 result = 0 while a = 80: print(i+1, "번 학생은 합격입니다.") ex) 특정 번호의 학생은 제외하고 학생들의 합격 여부 판단 예제 → 조건) scores = [90, 85, 77, 65, 97] / 합격 커트라인 : 80점 이상 / 2번과 4번 학생은 제외 scores = [90, 85, 77, 65, 97] cheating_students = {2, 4} for i in range(0, 5): if i+1 in cheating_students: continue ..

조건문 조건문 : 프로그램의 흐름을 제어하는 문법 : if를 붙여서 비교연산자를 통해 값들을 비교할 수 있다. cf.) 파이썬에서는 코드의 블록(Block)을 들여쓰기로 지정한다. cf.) tab 사용 vs space 사용 → space 사용 시, 4개 사용하는 것이 표준 조건문의 기본 형태 : if ~ elif ~ else ex) 성적 구간에 따른 학점 출력 예제 score = 95 if score >= 90: print("학점 A") elif score>=80: print("학점 B") elif score>=70: print("학점 C") else: print("학점 F") 비교연산자 : 특정한 두 값을 비교할 때 사용 → 종류) ==, !=, >, =, =80: result = "Success" e..

표준 입력 방법 자주 사용되는 표준 입력 방법 - input() 함수 : 한 줄의 문자열을 입력 받는 함수 - map() 함수 : 리스트의 모든 원소에 각각 특정 함수를 적용할 때 사용 ex) 공백을 기준으로 구분된 데이터를 입력 받을 때 list(map(int, input().split())) → map() 함수를 쓰지 않고 input().split()을 하게 되면 문자열 리스트가 만들어지게 된다 ex) 공백을 기준으로 구분된 데이터의 개수가 많지 않을 때 a, b, c = map(int, input().split()) → map(int, input().split()) 이렇게 묶어주는 것을 '패킹(packing)' 이라고 한다 → print(a, c, c, d) 를 해주게 되면 오류가 발생하게 된다 빠..

사전(딕셔너리) 사전(딕셔너리) 자료형 : 키(key) 와 값(value)의 쌍을 데이터로 가지는 자료형 cf.) 리스트와 튜플처럼 순차적으로 값을 저장하는 자료형들과는 다르다 : 변경 불가능한 자료형을 키로 사용 (해당 키 값으로 원소에 접근 가능) : 해쉬 테이블을 사용하므로, 데이터 조회 및 수정에 있어서 O(1)의 시간에 처리할 수 있다 data = dict() data['사과'] = 'Apple' data['바나나'] = 'Banana' data['코코넛'] = 'Coconut' print(data) #딕셔너리 객체에 특정 키가 존재하는 지 확인 if '사과' in data: print("'사과'를 키로 가지는 데이터가 존재합니다.") #결과 #{'사과':'Apple', '바나나':'Banana..

문자열 문자열 자료형 - 문자열 변수 초기화 : "(큰따옴표) or '(작은따옴표) 이용 - 문자열 안에 " or ' 이 포함되어야 하는 경우 : 전체 문자열을 " 로 구성하는 경우, ' 를 포함할 수 있다 : 전체 문자열을 ' 로 구성하는 경우, " 를 포함할 수 있다 : 백슬래시(\) 를 사용하여 " or ' 를 원하는 만큼 포함시킬 수 있다 #백슬래시를 사용하여 "를 나타내기 data = "Don't you know \"Python\"?" print(data) #결과 #Don't you know "Python"? 문자열 연산 : 문자열 변수에 + 를 이용하면 문자열끼리 연결된다 : 문자열 변수를 특정 양의 정수와 곱하면, 그 만큼 여러 번 더해진다 : 문자열도 인덱싱 / 슬라이싱 이 가능하다 (단,..

리스트 리스트 자료형 : 데이터를 연속적으로 담아 처리하기 위해 사용하는 자료형 : 배열 및 연결 리스트와 유사 : 리스트 대신 배열 or 테이블 이라고 부르기도 한다 리스트 초기화 : 대괄호( [] ) 안에 원소를 넣어 초기화 : 쉼표(,)를 통해 원소 구분 : 비어있는 리스트 선언 : list() or [] : 인덱스로 리스트 원소에 접근 (인덱스는 0부터 시작) #크기가 N, 모든 값이 0인 1차원 리스트 초기화 n = 10 a = [0]*n print(a) #결과 [0, 0, 0, 0, 0, 0, 0, 0, 0,0] 리스트의 인덱싱과 슬라이싱 - 인덱싱(Indexing) : 리스트의 특정한 원소에 접근하는 것 : 인덱스 값은 양의 정수, 음의 정수 모두 사용 가능 : 음의 정수를 넣으면 원소 거꾸..

파이썬의 자료형 종류 자료형 종류 : 정수형, 실수형, 복소수형, 문자열, 리스트, 튜플, 사전(딕셔너리) 등... • 정수형 : 정수를 다루는 자료형 : 양의 정수, 음의 정수, 0 • 실수형 : 소수점 아래의 데이터를 포함하는 자료형 : 변수에 소수점 붙인 수를 대입하면 바로 실수형 변수로 처리 : 소수부/정수부 가 0인 소수는 0 생략해서 작성 가능 ex) a = 5. → 5.0 / b = -.7 → -0.7 지수 표현 방식 : e나 E를 사용하여 지수 표현 방식을 이용할 수 있다 : e나 E = 10의 지수부 ex) 1e9 = 1 x 10^9 : 최단 경로 알고리즘에서 도달할 수 없는 노드에서 최단 거리를 무한(INF)로 설정 : 가능한 최댓값이 10억 미만일 때, 무한(INF)의 값으로 1e9를..

시간 / 공간 복잡도 시간 복잡도 : 알고리즘의 수행 시간 분석 공간 복잡도 : 알고리즘의 메모리 사용량 분석 (복잡도↓ → 알고리즘 Good) cf.) 복잡도 : 성능적인 측면에서의 복잡도 - 시간 복잡도가 높다 = 수행 시간이 길다 - 시간 복잡도가 낮다 = 수행 시간이 짧다 - 공간 복잡도가 높다 = 많은 메모리가 필요하다 - 공간 복잡도가 낮다 = 많은 메모리가 필요하지 않다 빅오 표기법 빅오 표기법 : 복잡도를 표기하는 방식 : 가장 빠르게 증가하는 항만을 고려하는 표기법 : 극한의 개념으로 생각하면 쉽다 ex) 3N^3 + 5N^2 → O(N^3) 빅오 표기법 성능 순서 (← Good) (Bad →) O(1) - O(logN) - O(N) - O(NlogN) - O(N^2) - O(N^3) -..