코딩혜영

1.시간복잡도

1억(10^8)번이 1초의 시간이 걸린다고 생각한다.

2. 2805 나무 자르기

[문제]

1.상근이는 나무 M미터가 필요하다.

2.상근이는 절단기에 높이 H를 지정해야한다. 높이를 지정하면 톱날이 땅부터 H미터 위로 올라간다. 그리고 한 줄의 연속된 나무(자를 수 있는 나무) 전체를 절단해버린다.

3.높이가 H보다 크면 H위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않는다.

4.절단기 설정 가능 높이 >= 0

5.적어도 M미터의 나무를 가져가기 위한, 설정 높이 H의 최댓값 구하기.

[입력]

1.첫째 줄에 나무의 수 N과 필요한 나무 길이 M이 주어진다. ex) 4 7

2.둘째 줄에 나무의 높이가 주어진다. 나무의 높이들은 항상 >=M(필요한 나무 길이) 따라서 항상 가져갈 수 있음.

ex) 20 15 10 17

[첫 번째 문제 풀이] - 틀린 코드

N, M = map(int, input().split())

trees=list(map(int, input().split()))

trees.sort(reverse=True)



if len(set(trees))==1:
  if M==0:
    height=0
  else:
    for i in range(1, len(trees)):
      if len(trees)*i == M:
        height=i
        break
else:
  step=0
  height=0

  for i in range(len(trees)-2):
    if M==0:
      break
    start = trees[i]
    end = trees[i+1]
    step+=1
    for j in range(start-end):
      if M==0:
        break
      M=M-step #이때 step은 획득되는 길이
      height+=1
print(trees[0]-height)

위 코드대로 써보면, 진행 과정도 찍혀서 이해하기 쉽다.

문제를 푼 순서 로직은 다음과 같다.

1.먼저 나무를 내림차순으로 정렬해준다.

2.나무 길이를 앞에서부터 반복문으로 start, end로 잡고, 비교 횟수를 step으로 잡아준다. 이 비교횟수는, 해당 구간에서 1cm 이동할 때마다 1*step cm 만큼씩 얻을 수 있다는 것을 의미한다.

나무 길이를 첫 번째 예시 케이스인 20, 17, 15, 10 으로 가정해보자.

[배운점]

1..sort(reverse=False)가 디폴트이다. 내림차순 정렬하려면, .sort(reverse=True) 해주면 됨.

2.하나하나 모든 케이스를 따지는 경우에는, 예외 사항을 처리하기가 굉장히 까다롭다ㅠㅠ...하 왜 틀리는건지 답답해 죽겠네. 

3.나의 잘못된 코드로 수많이 오류가 났고, 시간을 낭비했다. 물론 그 안에서 배우는 것은 많았으나, 시간을 들여서 푸는 것은 일단 어느정도 알고리즘 개념과 필수 부분들을 암기한 후에 그때 시간들여서 푸는 것으로 하자. 이론책 다 보고 문제 보려면 시간 너무 오래 걸린다. 일단 개념부터 알자.

분할정복

거듭제곱을 1억번 이상하기엔 너무 계산이 오래 걸린다. 이때, 거듭제곱을 이진수를 활용하여 계산할 수 있다.

시간복잡도, 공간복잡도 

C+에서는 int보다는 long long, Java에서는 int 대신 long 쓰는게 둘 다 메모리가 4Bytes -> 8Bytes 2배이기 때문에 그냥 이것 쓰는게 마음 편하다. 부동 소수형도 float말고 double 쓰는게 마음 편하다. 실제 코딩 테스트 등에서는 이 점 반드시 지켜서, 어이없게 탈락하는 일 없게 하자. 단, overflow만 주의하고, 자신없으면 long을 쓰자.

동적계획법 계산할 때

첫 항이 반드시 하나가 아니다. 두 개, 세 개 일 수도 있으니 유의할 것.

top-down으로 먼저 연습하고, 익숙해지면 bottom-up으로 연습하자.

메모이제이션 - 동적계획법 코드 짜는 법

1) 기저 조건

2) 점화식 : 점화식을 찾는 것이 어렵고, 알고리즘 공부를 하지 않아도 풀 수 있다. 식을 찾아내는 것이 어렵다.ㅁ

3) 메모이제이션으로 저장해 줌

2517 달리기

merge sort(합병 정렬)은 분할 정복 알고리즘 중 하나입니다.

분할 정복은 문제를 작은 2개의 문제로 분리하고, 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략입니다. 

자료구조

List vs Linked List

Linked List의 경우에는 반드시 암기해줘야함.

java할 때는 배열 잡을 때, 10만 100만 작은 것을 앞으로 두기.

int[][] arr1 = new int[100][10000];

int[][] arr2 = new int[10000][100];

앞에가 작은 것이 훨씬 더 효율적이다. 정답여부까지 바뀔 수 있으니 조심하기!

트리 구조 코드를 짤 때, 사향 이진 트리(연결리스트처럼 한 줄로 연결되어 있는 트리)인지 확인이 필요하다.

-이진 트리를 표현하는 두 가지 방법

1) 연결 자료 구조 : 연결 리스트로 class 를 통해 구현 가능

2) 연속 구조 : 일차원 배열 활용하여 표현 가능(교재 참고하기, 40페이지)

문제에서 N이 10~30만이다 => NlogN 선형로그형

N이 5천정도면 2차형 알고리즘

N이 30정도다 => 팩토리얼형 등이다.

N의 수에 따라서 알고리즘 유추 가능!

이진트리 굉장히 중요하고, 이진트리는 4가지 형태가 있다.(교재 참고)

정 이진트리, 포화 이진트리, 완전 이진 트리, 사항 이진 트리

1.sort() 정복하기

-리스트 안에 담긴 것들은 모두 기본으로 오름차순 정렬이 된다.(숫자, 문자, 문자열 전부 상관없이)

-아스키코드 기반으로 정렬하는 것이므로, 대문자가 소문자보다 먼저 오게 된다.

-내림차순을 하고 싶으면, reverse=True 를 속성으로 넣어주면 된다.

-2차원 배열부터는 어떤 것을 기준으로 배열할지 기준을 정해줘야한다. 이때 람다 함수를 사용한다.

c = sorted(a, key = lambda x: x[0]
#[(0, 1), (1, 2), (3, 0), (5, 1), (5, 2)]

d = sorted(a, key = lambda x : x[1])
# [(3, 0), (5, 1), (0, 1), (1, 2), (5, 2)]

#비교할 아이템이 요소가 복수 개일 경우, 튜플로 우선순위를 정해준다.
#게다가 -를 붙이면, 현재와 반대차순으로 정렬된다.

e = sorted(a, key= lambda x : (x[0], -x[1]))
#[(0, 1), (1, 2), (3, 0), (5, 2), (5, 1)]

f = sorted(a, key = lambda x : -x[0])
#[(5, 1), (5, 2), (3, 0), (1, 2), (0, 1)])

-sort(key=len) 이라고 하면, 문자열을 알파벳 순서대로 정렬해준다.

python 1181 단어정렬(실버5)

 #1181 단어 정렬

N = int(input())
words=[input() for _ in range(N)]
words=set(words)
word_tuples=[]
for word in words:
  word_tuples.append([word,len(word)])
word_tuples.sort(key= lambda x : (x[1], x[0]))

for word in word_tuples:
  print(word[0])

n = int(input())
lst = []

for i in range(n):
    lst.append(input())

lst.sort()	## 괄호 안에 아무 값도 넣지 않으면 알파벳 순서대로 정렬을 해 준다.
lst.sort(key = len)	## 문자열 길이 순으로 정렬.

for i in lst:
    print(i)

조합은 파이썬에서 라이브러리를 제공해주는 것으로 알고 있다.

import math

# nCr 계산
n = 5
r = 3
result = math.comb(n,r)

Q1.숫자를 list()로 감싸는 것은 에러가 나는가?

O. 에러가 난다. 주의할 것.

따라서 문제에 대한 답 코드는 다음과 같이 작성하였다.

import math, sys

def input():
    return sys.stdin.readline().rstrip()

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

result = math.comb(n,m)
result_list=list(str(result))
cnt=0

for i in reversed(result_list):
    if i=='0':
        cnt+=1
    else:
        break
print(cnt)

하지만 리스트 연산이 많아서 그런지 시간 초과가 떴다.

import math, sys

def input():
    return sys.stdin.readline().rstrip()

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

result = math.comb(n,m)
cnt=0

for i in str(result)[::-1]:
    if i=='0':
        cnt+=1
    else:
        break
print(cnt)

흠.. 이렇게 했는데도 시간 초과가 뜬다. 그러면 어떻게 하지?

일단 개선 방안을 생각해보았을 때, math.comb(n,m) 이 함수가 생각보다 시간이 오래걸리는 듯하다.

직접 만들어서 쓰는게 훨씬 효과적일 듯 하다.

일단 팩토리얼 함수 만들어보자.

def factorial(num):
    result=1
    for i in range(2,num+1):
        result *=i
    return result

조합 식은 다음과 같은데, 

우선 조합을 코드로 표현해보겠다.

def combination(n,k):
    #예외 처리
    if k > n:
        return 0
    if k == 0 or k==n:
        return 1
    
    #팩토리얼 계산
    def factorial(num):
        result=1
        for i in range(2,num+1):
            result *=i
        return result
    
    #이때 조합의 계산은 항상 정수이기 때문에, 정수 계산을 위해서 /가 아니라 //를 사용한다.
    result = factorial(n)//(factorial(n-k)*factorial(k))

    return result

이때 k!과 n-k!에서 중복되는 부분이 상당히 생긴다.

이 부분을 한 번 메모이제이션으로 해결해보자.

열심히 아래와 같이 코드를 제작하였다.

import sys

def input():
    return sys.stdin.readline().rstrip()

def comb(n,k):
    if k > n:
        return 0
    if k==0 or n==k:
        return 1
    
    #k가 n/2보다 큰 경우, nCk=nC(n-k)와 같음. 더 작은 수로 바꿔주는 과정
    if k > n/2 :
        k = n-k

    result=1
    for r in range(k): #r-1까지 돌 것임
        result = result * (n-r) // (r+1)

    return result

n, r = map(int, input().split())
print(comb(n, r))

하지만 여전히 에러가 났다 ^_^ 한 단계 더 가야하나보다.

파스칼의 삼각형을 이용하는 방법도 생각하였으나, 정답을 보니 0의 개수는 2와 5의 개수로 판단하는 것 같다.

팩토리얼에서 특정 소인수의 개수를 계산하는 방법

1.모든 2의 배수를 카운트한다.

: n을 2로 나눈 몫은 n 이하의 모든 수 중 2의 배수의 개수를 의미한다.

몫 = n이하의 2의 배수들의 개수

이게 잘 이해가 안됐었는데, 나열해놓고 세어보면 결국 그렇다. 그냥 외우자.

예를 들어, n=10이면 10//2=5로, 2 4 6 8 10 총 5개의 숫자가 하나 이상의 2를 갖고 있다.

이때 코드는 두 가지 관점에서 짤 수 있다. 결국 결과는 같다.

1) 나누는 수를 2, 4, 8 ...로 높인다.

2) 주어진 n을 2로 나눠가면서 반복 계산한다.

원리를 이해하기에는 1번이 더 쉽지만 코드 짜기에는 2번이 더 쉬운 듯 하다.

드디어 정답 코드

import sys

def input():
    return sys.stdin.readline().rstrip()

def cnt(s,n):
    if n < s:
        return 0
    cnt=0
    while n>=s:
        cnt +=n//s
        n=n//s
    return cnt

n,m = map(int,input().split())
two_cnt = cnt(2,n) - cnt(2,n-m) - cnt(2,m)
five_cnt = cnt(5,n) - cnt(5,n-m) - cnt(5,m)

print(min(two_cnt,five_cnt))

+) sys.stdin.readline()과 sys.stdin.read()의 차이

이때 sys.stdin.readline()과 sys.stdin.read()의 차이가 궁금해서 찾아봤다.

-read()

: 여러 줄 입력을 처리할 때 사용된다. 따라서 메모리 사용량이 많아질 수 있으나, 빠르게 많은 양의 데이터 읽기 가능하다.

-readline()

: 한 줄씩 입력을 처리한다. 따라서 메모리 사용량이 상대적으로 적으나, read()보다 느리다.