코딩묻은 디자이너

1. 2557 Hello World

print('Hello World')

생각 외로 정답 비율이 낮아서 누가 틀리지? 했는데 내가 틀렸다

문자열을 출력할 때 ''에 주의하자

2. 10718 We love krill

for i in range(2):
    print('강한친구 대한육군')

3. 10171 고양이

print('\\    /\\')
print(" )  ( ')")
print('(  /  )')
print(' \\(__)|')

역슬래쉬(\)를 출력하기 위해선 (\\)를 입력해주어야 한ㄷ

4. 10172 개

print('|\\_/|')
print('|q p|   /}')
print('( 0 )"""\\')
print('|"^"`    |')
print('||_/=\\\\__|')

5. 1000 A+B

A, B = map(int, input().split())

print(A+B)

6. 1001 A-B

A, B = map(int, input().split())

print(A-B)

7. 10998 AxB

A, B = map(int, input().split())

print(A*B)

8. 1008 A/B

A, B = map(int, input().split())

print(A/B)

9. 10869 사칙연산

A, B = map(int, input().split())

print(A+B)
print(A-B)
print(A*B)
print(A//B)
print(A%B)

10. 10430 나머지

A, B, C = map(int, input().split())

print((A+B)%C)
print(((A%C)+(B%C))%C)
print((A*B)%C)
print(((A%C)*(B%C))%C)

11. 2588 곱셈

N1 = int(input())
N2 = int(input())

print(N1*(N2%10))
print(N1*((N2%100)//10))
print(N1*(N2//100))
print(N1*N2)

1. 카운팅정렬이란

요소의 계수를 세고 정렬하는 알고리즘

리스트의 값의 범위가 크지 않을 때 효율적이다

지금까지 많은 알고리즘을 배우진 않았지만(버블 정렬, 카운팅 정렬, 선택정렬... 정도) 가장 이해가 힘들었던 정렬 중 하나로, 몇번이나 손코딩을 해야했다

2. 선택정렬 파이썬 코드

# 카운팅 정렬

nums = [1, 5, 8, 9, 1, 3, 4, 6, 5, 7, 6, 1, 1, 3, 2]

sort_nums = [0] * len(nums)         #요소들을 정렬해줄 배열을 선언한다
big_num = -1                        #big_num은 요소들 중 가장 큰 값을 의미
for i in nums:
    if big_num < i:
        big_num = i

counts = [0] * (big_num + 1)        #가장 큰 값까지 카운팅 해줄 배열을 선언한다


for i in range(len(nums)):
    counts[nums[i]] += 1            #각 요소의 자리에 (해당 코드의 경우 9까지) 요소의 갯수를 더해준다
print(counts)                       #[0, 4, 1, 2, 1, 2, 2, 1, 1, 1]


for i in range(1, len(counts)):
    counts[i] += counts[i - 1]      # 배열에 누적값 표현
print(counts)                       #[0, 4, 5, 7, 8, 10, 12, 13, 14, 15]

for i in range(len(nums) - 1, -1, -1): # 뒤에서 부터 시행하는 이유는 안정정렬을 위해서
    n = nums[i]
    counts[n] -= 1
    idx = counts[n]
    sort_nums[idx] = n

print(sort_nums)

시간복잡도는 O(NM) N이 큰 경우 O(N), M이 큰 경우 O(M)이라고,,, 생각했는데 다른 블로그들을 보아 O(N) 인 것 같다

1. 이진 검색 알고리즘이란

정렬되어있는 리스트에서 특정한 값의 위치를 찾는 알고리즘으로

찾고자 하는 값이 중간 값보다 크면 중앙값(또는 중앙값 +1)이 새로운 최솟값이 되어 다시 값을 찾는다

검색이 반복될 때마다 목표값을 찾을 확률이 두 배가 된다.

업다운 게임과 알고리즘의 형태가 비슷하다고 생각한다

2. python 코드

def binarySearch(a, key):
    start = 0
    end = len(a)-1

    while start <= end:
        middle = (start + end) // 2
        if a[middle] == key:
            return True
        elif a[middle] > key:
            end = middle - 1
        else:
            start = middle + 1
    return False

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 13, 15]

print(binarySearch(arr, 4))
print(binarySearch(arr,12))

True
False

4는 배열 안에 있기 때문에 True 12는 배열에 존재하지 않기 때문에 False를 반환한다

이진탐색 코드는 반드시 '정렬된 리스트'에서 실행되어야 한다.