[sw 사관학교 정글] [WEEK01] WIL 01주차 개발일지

[WEEK01] WIL 개발일지

 

[정수론, 배열, 문자열, 재귀함수, 정렬, 완전탐색, 시간복잡도]

 

입력

 

input.txt 파일에 입력값을 저장 후 읽어들인다

💡 import sys

    sys.stdin= open(”input.txt”, “rt”)

    input = sys.stdin.readline: 일반적으로 input() 사용시 발생하는 시간 초과 오답처리 해결

 

💡 input 과 sys.stdin.readline 차이

input() 내장 함수: parameter로 prompt messange를 받을 수 있다. 입력받은 값의 개행 문자를 삭제시켜 리턴한다.

∴ input() 내장 함수는 sys.stdin.readline()과 비교해서 prompt message를 출력하고, 개행문자를 삭제한 값을 리턴하기 때문에 느리다.

 

리스트 개행문자 제거

💡 myList = ['this\n', 'is\n', 'a\n', 'list\n', 'of\n', 'words\n'] print([l.strip() for l in myList])

• input().split(): 입력받는 것을 나누어 받는다
• list(map(int,input().split())): 입력받은 문자열을 나누어 받아서 정수로 바꿔준다.
• n, m = map(int,input().split()): 한줄에 두개 입력받은것 따로 n, m에 저장

A =[ ]

for i in range (n)

A.append(int(input())여러줄 입력 받아 리스트 만들기

 

ex)5 4

1 10 14 15 20 39

n, m = map(int,input().split())

for i in range(5):
	nums = list(map(int,input(),split())

 

출력

https://leedakyeong.tistory.com/entry/python-for문-if문-한-줄로-코딩하기

for i in range(n):
    OX_list = []
    OX_list.append(input())
    print(OX_list)

list_a = [i for i in range(10)]
print(list_a)

for i in range(n):
	OX_list = list(input())
print(OX_list)

리스트

list.append(값): 기존 리스트의 마지막에 값을 추가한다.

list.insert(인덱스, 값): 리스트에 인덱스로 지정한 위치에 값을 넣을 수 있다.

del a[i]: 리스트에서 인덱스 위치에 해당하는 값 삭제

a.remove(값): 리스트에서 값을 찾아 삭제(단, 삭제하고 싶은 값이 없을 경우 error발생)

list[시작 :끝 :스탭]

 

순열 조합

 

import itertools

순열(premutation)

• 순서를 고려하여 뽑는 경우의 수(두자리수만들기)

조합(combination)

• 순서를 생각하지 않고 뽑는 경우의 수(대표뽑기)

중복순열(premutation with repetition)

• 중복을 허용하는 순열(중복을 허용해  세 자리 수를 만들 수)

중복조합(combination with repetiton)

• 중복을 허용하는 조합(중복을 허용해 대표뽑기)

 

재귀함수

• 문제의 정의를 정확히 표기
• 종료조건
• 컬스택-호출의 흐름을 따라갈 줄 알아야함

 

 

꼬리재귀

 

 

분할정복(Divide and Conquer)

• 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
• 1 Divde: 문제가 분할이 가능한 경우, 2개 이상의 문제로 나눈다.

-2 Conquer: 나누어진 문제가 여전히 분할이 가능하면, 또 다시 Divide를 수행한다.

-3 Combine: Conquer한 문제들을 통합하여 원래 문제의 답을 얻는다

ex) merge sort, quick sort

 

 

완전탐색(전체탐색, 브루드포스, 키 전수조사)

• 구현이 쉬움
• 실행 시간이 오래 걸림
• 메모리 효율면에 비효율적임

선형구조(데이터를 순차적으로 나열): 순차 탐색

비선형 구조(트리, 그래프): 백트래킹, DFS, BFS

 

소수

• 소수 판별(에라토스테네스의 접근)

*제곱근 n 이하의 모든 소수로 나누었을 때 나누어 떨어지지 않는다

def isPrime(num):
    if num <= 1:
        return False
    else:
        for i in range(2, int(num**0.5)+1):
            if num % i == 0:
                return False
            return True

• 소수 판별(에라토스테네스의 체)

sieve = [False, False] + ([True] * (n - 1))
primes = []

for i in range(2, n + 1):
    if sieve[i]:
        primes.append(i)
    for j in range(i * 2, n + 1, i):
        sieve[j] = False

print(primes)

배열 ≠ 리스트

 

공통점

메모리에 주소를 저장한다

기타

#ord(): 문자 → 아스키 // chr(): 아스키 → 문자

 

#삼항연산자: [true_value] if [condition] else [false_value]

 

#n.3f: 반올림하여 소숫점 3자리 까지 표시

 

#sep=’\n’: 출력시 구분자를 ‘\n’로 바꿔줌

#end=""  : print 문을 이용해 출력을 완료한 뒤의 내용을 수정할 수 있음

                   기본 값으로는 개행(\n)이 들어가 있으며 이를 사용해 개행을 없애거나 원하는 문자를 입력할 수 있습니다.

 

#파이썬 math 모듈

 

(import math)

• math.ceil(): 올림하여 정수 반환
• math.floor(): 내림하여 정수 반환
• round(number, digit): number를 반올림하여 소숫점 digit 자리까지 보여준다

 

join 함수: 문자열 합치기

 

💡 ''.join(리스트)''.join(리스트)를 이용하면 매개변수로 들어온 ['a', 'b', 'c'] 이런 식의 리스트를 'abc'의 문자열로 합쳐서 반환해주는 함수인 것입니다.

 

💡 '구분자'.join(리스트)'구분자'.join(리스트)를 이용하면 리스트의 값과 값 사이에 '구분자'에 들어온 구분자를 넣어서 하나의 문자열로 합쳐줍니다.'_'.join(['a', 'b', 'c']) 라 하면 "a_b_c" 와 같은 형태로 문자열을 만들어서 반환해 줍니다.

 

중복제거 방법

set() : 집합자료형 변환 함수 -> 중복요소 제거

집합자료형

 

---

1 mb == 100000byte

영어, 숫자 = 1 byte

한글 = 2byte

시간복잡도는 n에 비례한다

 

(추가 정리 예정)