코딩하는 수학도

예제 시각 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다. 00시 00분 03초 00시 13분 30초 반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각이다. 00시 02분 55초 01시 27분 45초 입력 조건 첫째 줄에 정수 N이 입력된다. (0 ≤ N ≤ 23) 출력 조건 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다. 입력 예시 5 출력 예시 11475 소스코드 N = int(input()) count = 0 ..

코딩 테스트에서 구현(Implementation)이란? 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정을 의미한다. 완전 탐색 모든 경우의 수를 저저 없이 다 계산하는 해결 방법을 의미한다. 시뮬레이션 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 유형을 의미한다. 예제 상하좌우 : 시뮬레이션 여행가 A는 N x N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있다. 계획서에는 하나의 줄에..

최대공약수 최대공약수(gcd, greatest common divisor)란? 0이 아닌 두 개 이상의 정수의 공통되는 약수 중에서 가장 큰 수이다. 따라서 두 정수 a와 b의 최대공약수는 a의 약수인 동시에 b의 약수인 수, 즉 두 정수 a, b의 공약수 중에서 가장 큰 수를 의미한다. 약수와 최대공약수 두 정수 a = 12와 b = 30의 최대공약수를 구해보자. 12의 약수는 1, 2, 3, 4, 6, 12 이고, 30의 약수는 1, 2, 3, 5, 6, 10, 15, 30 이다. 따라서 12와 30의 공약수는 1, 2, 3, 6 이고, 공약수 중 가장 큰 수는 6이므로 두 수 12와 30의 최대공약수는 gcd(12, 30) = 6 이다. 파이썬에는 math 라이브러리에 최대공약수를 반환해주는 gcd..

10진법(decimal)이란? 우리는 일상생활에서 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 의 10개의 숫자를 사용하여 수를 나타내고 자리가 하나씩 올라감에 따라 자리의 값이 10배씩 커지도록 수를 나타내는 방법을 십진법이라고 한다. 십진법으로 나타낸 수 4321은 4321 = 4 x 1000 + 3 x 100 + 2 x 10 + 1 = 4 x 10^3 + 3 x 10^2 + 2 x 10 + 1 과 같이 나타낼 수 있다. 2진법(binary)이란? 0, 1 의 2개의 숫자를 사용하여 수를 나타내고, 자리가 하나씩 올라감에 따라 자리의 값이 2배씩 커지도록 수를 나타내는 방법을 이진법이라고 한다. 십진수를 이진수로 변환하기 십진수를 이진수로 변환하기 위해서는 우선 십진수를 2의 거듭제곱의 합으로..

최단 경로 (Shortest Path) 가장 짧은 경로를 찾는 알고리즘 '길 찾기' 문제라고도 불린다. 보통 그래프를 이용해 표현한다. 다익스트라 최단 경로 알고리즘 (Dijkstra) 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 다익스트라 최단 경로 알고리즘은 '음의 간선'이 없을 때 정상적으로 동작한다. 음의 간선이란 0보다 작은 값을 가지는 간선을 의미한다. 원리 다익스트라 최단 경로 알고리즘은 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정을 반복하기 때문에 기본적으로 그리디 알고리즘으로 구분된다. 출발 노드를 설정한다. 최단 거리 테이블을 초기화한다. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 ..

sorted() 파이썬은 기본 정렬 라이브러리인 sorted() 함수를 제공한다. sorted() 는 병합 정렬을 기반으로 만들어졌는데, 병합 정렬은 일반적으로 퀵 정렬보다 느리지만 최악의 경우에도 시간 복잡도 O(NlogN)을 보장한다는 특징이 있다. sorted() 함수는 정렬된 결과를 리스트 자료형으로 반환한다. 파이썬은 병합 정렬과 삽입 정렬의 아이디어를 더한 하이브리드 방식의 정렬 알고리즘을 사용하고 있다. sort() 리스트 객체의 내장함수인 sort() 는 리스트 변수가 하나 있을 때 내부 원소를 바로 정렬한다. 이를 이용하면 별도의 정렬된 리스트가 반환되지 않고 내부 원소가 바로 정렬된다. array = [ 7, 5, 9, 0, 3, 1, 6, 2, 4, 8] # sorted() 정렬 : ..

collections collections 라이브러리는 유용한 자료구조를 제공하는 표준 라이브러리다. 표준 라이브러리 : 특정한 프로그래밍 언어에서 자주 사용되는 표준 소스코드를 미리 구현해 놓은 라이브러리 대표적으로 deque, Counter 클래스가 포함되어 있다. deque 파이썬에서는 Queue 라이브러리가 아닌 deque를 사용해 큐를 구현한다. deque 는 스택과 큐의 장점을 모두 채택한 것이라, 데이터 삽입/삭제 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러리를 이용하는 것보다 더 간단하기 때문이다. 리스트 자료형 : 데이터 삽입/삭제 시 '가장 뒤쪽 원소'를 기준으로 수행하므로 리스트 앞쪽에 있는 원소를 삭제하거나 앞쪽에 새 원소를 삽입할 때 많은 시간이 소요됨 시간복잡도 비..

split 형식 : 문자열.split(구분자) split 함수는 문자열을 나누는 함수입니다. 매개변수로 구분자를 주면, 해당 구분자를 기준으로 문자열을 잘라 리스트 형식으로 반환합니다. 만약, 매개변수로 아무것도 주지 않으면 공백을 기준으로 문자열을 나눕니다. String1 = 'a b c d' String2 = 'a_b_c_d' String3 = 'azbzczd' result1 = String1.split() result2 = String2.split('_') result3 = String3.split('z') print(result1) print(result2) print(result3) # print 결과 ['a', 'b', 'c', 'd'] ['a', 'b', 'c', 'd'] ['a', 'b',..

itertools itertools 는 파이썬에서 반복되는 데이터를 처리하는 기능을 제공하는 라이브러리이다. 대표적으로, permutations(순열), combinations(조합) 클래스가 포함되어 있다. 경우의 수 경우의 수란 한 번의 시행에서 '일어날 수 있는 사건의 가지 수'를 의미한다. '동전 던지기' 시행에서 경우의 수는 {앞면, 뒷면} 이므로 2가지이다. '주사위 던지기' 시행에서 경우의 수는 {1, 2, 3, 4, 5, 6} 이므로 6가지이다. 순열 (Permutations) 순열이란 서로 다른 n개에서 r개를 선택하여 일렬로 나열하는 것을 의미한다. (순서를 고려함) 기호로 쓰면 nPr 이고, 경우의 수를 계산하는 공식은 nPr = n!/(n-r)! 이다. 예) 반장, 부반장 뽑기 [짱..