[이것이 코딩테스트다] 1. 출제 경향 분석 및 파이썬 문법

1. 온라인 코딩테스트 vs 오프라인 코딩테스트 : 인터넷 검색 허용 / 허용 불가의 경우가 많음. 온라인 합격 다음에 오프라인 식으로 진행하기도 함.

 

2. 온라인 저지 : 프로그래밍 대회나 코딩 테스트에서 나올 법한 문제를 시험해보는 온라인 시스템

- 백준 온라인 저지, 코드업, 프로그래머스

 

3. 코테 언어 : 주로 C++, 파이썬을 코테 응시에 사용함. 프로그램 개발 방식 코테에서 가장 유리한 프로그래밍 언어는 파이썬, 자바.

 

4. 팀노트 만들어서 비슷한 유형의 코딩 테스트에 대비하기.

 

---

<코딩테스트 출제 경향>

1) 그리디

2) 구현

3) BFS/DFS

 

<알고리즘 성능평가>

1) 복잡도 : 시간 복잡도(수행 시간 분석), 공간 복잡도(메모리 사용량 분석) 낮을 수록 더 좋은 알고리즘.

- 빅오 표기법 : 가장 빠르게 증가하는 항만 고려하는 표기법. 함수의 상한만을 나타내게 됨. 3N^3 + 5N^2 의 빅오 표기법은 O(N^3).

2) 알고리즘 설계시 유의사항

- CPU 기반 컴퓨터의 연산 횟수가 5억 이상인 경우: C언어는 1~3초, Python은 5~15초 걸릴 수 있음.

- 코딩테스트 문제에서 시간제한은 통상 1~5초 가량이라는 점에 유의할 것.

+ N의 범위에 따른 시간 복잡도 제한. (시간제한 1초)

  - N의 범위가 500인 경우 : O(N^3)

  - N의 범위가 2000인 경우 : O(N^2)

  - N의 범위가 100,000인 경우 : O(NlogN)

  - N의 범위가 10,000,000인 경우 : O(N)

 

3) 문제 해결 과정

(1) 지문 읽기 및 컴퓨터적 사고

(2) 요구사항(복잡도) 분석

(3) 문제 해결을 위한 아이디어 찾기

(4) 소스코드 설계 및 코딩

 

4) 수행 시간 측정 소스코드

import tiome
start_time = time.time()





end_time = time.time()
print("time:", end_time - start_time)

 

---

 

<자료형>

- 정수형 : int

- 실수형 : float : 실수형을 저장하기 위해 고정된 크기의 메모리를 할당해 실수 표현시 정확도에는 한계가 있음. = round 함수를 이용해서 자리를 고정해야함.

+ 지수 표현 방식 : 유효숫자 e 지수 = 유효숫자 * 10^지수

+ 수 자료형의 연산 : 나누기 연산자는 나눠진 결과를 실수형으로 반환함. 그래서 나머지 연산자와 몫 연산자를 사용함.

 

- 리스트 자료형 : 일반적인 배열과 유사한 기능. 배열 혹은 테이블이라고 부른다.

+ 리스트 컴프리헨션 : 조건문과 반복문 등을 이용해서 리스트 초기화 

Ls=[i for i in range(10)] 
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Ls=[i for i in range(10) if i % 2 == 1]
# [1, 3, 5, 7, 9]

 

- 문자열 변수 " ", ' ' :  \ 백슬레시를 활용해서 특수기호를 포함시킬 수 있음.

+ 문자열 연산 : 덧셈과 곱셈 가능. 문자열은 특정 인덱스 값을 변경할 수 없음.

 

- 튜플 자료형 : 한번 선언된 값을 변경할 수 없음.

+ 튜플 사용시 좋은 경우 

 1) 서로 다른 성질의 데이터를 묶어서 관리해야 할 때

 2) 데이터의 나열을 해싱의 키 값으로 사용해야 할 때

 3) 리스트보다 메모리를 효율적으로 사용해야 할 때

 

- 딕셔너리 : 키와 값을 쌍으로 가지는 자료형. 해시 테이블을 이용하므로 데이터의 조회 및 수정에 있어서 O(1)의 시간에 처리할 수 있다.

 

- 집합 : 중복을 허용하지 않고, 순서가 없음. {} 

+ 합집합 |, 교집합 &, 차집합 - 으로 수행할 수 있음.

+ add()로 추가, update([1,2])로 여러개 원소 추가, remove()로 특정값 원소 삭제

 

 

<기본 입출력>

1) 입력

a=input() 
#한 줄의 문자열 입력

b=map()
#리스트 형식으로 입력된 값들 각각 자료형 변환

Ls=map(int, input().split())

- 입력을 최대한 빠르게 받아야 하는 경우 (속도 제한)

import sys

sys.stdin.readline().rstrip()
# 입력 후 엔터가 줄 바꿈 기호로 변환되기 때문에 .rstrip() 사용

 

2) 출력

- print 함수. 출력 이후에 줄바꿈을 원하지 않는다면 end=' '로 끝을 설정해줄 수 있음.

 

+) f-strint : print(f"{name}")

 

---

<조건문>

- if문

+ 한줄 쓰기 : true실행문 if 조건 else false실행문

 

<반복문>

- while문 : 특정 조건을 만족할 때 반복 실행. 무한루프 발생 가능하므로 탈출할 수 있는지 확인해야함.

- for문 : for i in range(시작값, 끝값+1) : 시작값부터 끝값까지 순차적 수행

+ 반복문 탈출하기 위해서 break 쓸 수 있음.

+ 특정 조건은 넘어가기 위해 continue 함수를 쓸 수 있음.

- 중첨 반복문 : 바깥 반복문 실행시 안 반복문도 매번 실행됨.

 

---

<함수> 

- 내장함수와 사용자 정의 함수

 def 함수명(매개변수):

     실행할 소스코드

     return 반환값  #반환값을 여러개 값을 가질 수 있음

+ global 키워드로 함수 바깥에 선언된 변수를 활용할 수 있음.

a = 1

def func():
	global a
    a += 1
    print(a)
    
func()

- 람다 표현식 (이름 없는 함수)

lambda a,b : a+b

print(sorted(array, key=lambda x: x[1]) : 정렬 기준을 [1]에 위치한 것을 기준으로 정렬하라

 

---

<실전에서 유용한 표준 라이브러리>

 - 내장 함수

  + sum(), min(), max(), sorted(,reverse=True 내림차순)

 - itertools 파이썬에서 반복되는 형태의 데이터를 처리하기 위한 유용한 기능들 제공. 순열과 조합 라이브러리 자주 사용됨.

  + 내부 원소가 몇번 등장했는지 알려주는 함수 Counter

  + 순열과 조합

#순열

from itertools import permutations

data = ['A', 'B', 'C']

result = list(permutation(data, 3))
print(result)


#조합

from itertools import combinations

data = ['A', 'B', 'C']

result = list(combinations(data, 2))
print(result)

 - 중복순열과 중복조합

#중복순열

from itertools import product

data = ['A', 'B', 'C']

result = list(product(data, repeat=2)) #2개 뽑는 순열 구하기(중복허용)
print(result)

#중복조합

from itertools import combinations_with_replacement

data = ['A', 'B', 'C']

result = list(combination_with_replacement(data, 2)) #2개 뽑는 조합 구하기(중복허용)
print(result)

 

 - heapq : 힙 자료구조를 제공. 우선순위 큐 기능을 구현하기 위해 사용됨.

 - bisect : 이진 탐색 기능을 제공.

 - collections : 덱, 카운터 등의 유용한 자료구조를 포함.

 

 - math : 필수적인 수학적 기능을 제공. (팩토리얼, 제곱근 등)

  + 최대 공약수 : math.gcd(5, 10)

  + 최소 공배수 : 5 * 10 // math.gcd(5, 10)