코딩묻은 디자이너

https://www.acmicpc.net/problem/2562

문제

9개의 서로 다른 자연수가 주어질 때, 이들 중 최댓값을 찾고 그 최댓값이 몇 번째 수인지를 구하는 프로그램을 작성하시오.

예를 들어, 서로 다른 9개의 자연수

3, 29, 38, 12, 57, 74, 40, 85, 61

이 주어지면, 이들 중 최댓값은 85이고, 이 값은 8번째 수이다.

입력

첫째 줄부터 아홉 번째 줄까지 한 줄에 하나의 자연수가 주어진다. 주어지는 자연수는 100 보다 작다.

출력

첫째 줄에 최댓값을 출력하고, 둘째 줄에 최댓값이 몇 번째 수인지를 출력한다.

arr = []
max_num = 0
idx = 0

for tc in range(9):
    arr += [int(input())]

for i in range(len(arr)):
    if arr[i] > max_num:
        max_num = arr[i]
        idx = i
print(max_num)
print(idx+1)

max_num과 idx를 미리 선언해두고 리스트를 순환하며 앞에 저장된 수보다 크면 값을 바꿔가며

큰 값과 인덱스 값을 찾아주었다.

인덱스는 0부터 시작하기 때문에 +1 하여 출력하였다.

https://www.acmicpc.net/problem/10818

문제

N개의 정수가 주어진다. 이때, 최솟값과 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다.

출력

첫째 줄에 주어진 정수 N개의 최솟값과 최댓값을 공백으로 구분해 출력한다.

N = int(input())
num = list(map(int, input().split()))

print('{} {}'.format(min(num), max(num)))

내장함수 max min을 활용하여 빠르게 끝냈다

아래 코드는 버블소트를 이용해 풀어보려고 했는데 시간초과가 나왔다

버블소트가 아닌 다른 소트방식을 사용했다면 시간초과까지는 나오지 않았을 것 같지만... 그냥 내장 함수로 끝을 냈다.

N = int(input())
num = list(map(int, input().split()))

for i in range(N-1, -1, -1):
    for j in range(0, i):
        if num[j] > num[j+1]:
            num[j], num[j+1] = num[j+1], num[j]

print('{} {}'.format(num[0],num[-1]))

버블소트 사용한 코드,,, 시간초과

2021.08.22 - [분류 전체보기] - [알고리즘] 버블 정렬 이해하기_python

https://www.acmicpc.net/problem/1110

문제

0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다. 먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다. 그 다음, 주어진 수의 가장 오른쪽 자리 수와 앞에서 구한 합의 가장 오른쪽 자리 수를 이어 붙이면 새로운 수를 만들 수 있다. 다음 예를 보자.

26부터 시작한다. 2+6 = 8이다. 새로운 수는 68이다. 6+8 = 14이다. 새로운 수는 84이다. 8+4 = 12이다. 새로운 수는 42이다. 4+2 = 6이다. 새로운 수는 26이다.

위의 예는 4번만에 원래 수로 돌아올 수 있다. 따라서 26의 사이클의 길이는 4이다.

N이 주어졌을 때, N의 사이클의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. N은 0보다 크거나 같고, 99보다 작거나 같은 정수이다.

출력

첫째 줄에 N의 사이클 길이를 출력한다.

cnt = 0

new_num = int(input())
N = new_num

while True:
    if cnt > 0 and new_num == N:
        break
    else:
        second = new_num//10 + new_num % 10
        new_num = (new_num%10)*10 + (second%10)
        cnt += 1

print(cnt)

생각보다도 생각할게 많았던 문제,

문자열을 활용해서도 풀 수 있을 것 같다.

https://www.acmicpc.net/problem/10951

문제

두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스는 한 줄로 이루어져 있으며, 각 줄에 A와 B가 주어진다. (0 < A, B < 10)

출력

각 테스트 케이스마다 A+B를 출력한다.

while True:
    try:
        A, B = map(int, input().split())
        print(A + B)
    except:
        break

문제

두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스는 한 줄로 이루어져 있으며, 각 줄에 A와 B가 주어진다. (0 < A, B < 10)

입력의 마지막에는 0 두 개가 들어온다.

출력

각 테스트 케이스마다 A+B를 출력한다.

while True:
    A, B = map(int, input().split())
    if A + B == 0:
        break
    print(A + B)

1. 2739 구구단

N = int(input())

for i in range(1, 10):
    print('{} * {} = {}'.format(N,i,N*i))

2. 10950 A+B -3

T = int(input())

for tc in range(1, T+1):
    A, B = map(int,input().split())
    print(A + B)

3. 8393 합

n = int(input())
add = 0

for i in range(n+1):
    add += i

print(add)

4. 15552 빠른 A+B

문제를 이해하지 못해 풀지 않았다...

5. 2741 N 찍기

N = int(input())

for i in range(1, N+1):
    print(i)

6. 2742 기찍 N

N = int(input())

for i in range(N,0, -1):
    print(i)

7. 11021 A+B -7

T = int(input())

for tc in range(1, T+1):
    A, B = map(int, input().split())

    print('Case #{}: {}'.format(tc, A+B))

8. 11022 A+B -8

T = int(input())

for tc in range(1, T+1):
    A, B = map(int,input().split())

    print('Case #{}: {} + {} = {}'.format(tc, A, B, A+B))

9. 2438 별 찍기 - 1

N = int(input())

for i in range(1, N+1):
    print('*'*i)

10. 2439 별 찍기 -2

N = int(input())

for i in range(1,N+1):
    print('',end=' '*(N-i))
    print('*'*i)

11. 10871 X보다 작은 수

N, X = map(int, input().split())
num = list(map(int, input().split()))

for i in num:
    if i < X:
        print(i,end=' ')

1. 1330 두 수 비교하기

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

if A > B:
    print('>')

elif A < B :
    print('<')

else:
    print('==')

2. 9498 시험 성적

test = int(input())

if test >= 90:
    print('A')
elif test >= 80:
    print('B')
elif test >= 70:
    print('C')
elif test >= 60:
    print('D')
else:
    print('F')

elif 는 순서의 영향을 받기 때문에 순서에 주의해야한다

3. 2753 윤년

year = int(input())
if year % 400 == 0:
    print(1)

elif year % 4 == 0:
    if year % 100 != 0:
        print(1)
    else:
        print(0)

else:
    print(0)

4. 14681 사분면 고르기

x = int(input())
y = int(input())

if x > 0 and y > 0:
    print(1)
elif x < 0 and y > 0:
    print(2)
elif x < 0 and y < 0:
    print(3)
else:
    print(4)

5. 2884 알람 시계

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

if m < 45 :
    m = m + (60 - 45)
    if h != 0:
        h -= 1
    else:
        h = 23
else:
    m = m - 45

print('{} {}'.format(h, m))

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를 반환한다

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