[백준] 준비운동 Part1. 튼튼한 기본기1

https://covenant.tistory.com/224

코딩테스트 대비를 위한 백준 문제 추천

원래 풀던 프로그래머스 연습 kit가 끝나서 백준으로 넘어가기로 했다.

위 글을 참고하여 순서대로 쭉 풀기로 결정했다.

이번 주는 준비운동part의 브론즈 문제만 풀기로 해서 쉬운 편이다.

 

1. 약수구하기

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

def f(a,b):
    n = 1
    cnt = 0
    while a >= n:
        if a % n == 0:
            cnt += 1
        if cnt == b:
            return n
        n += 1
    return 0

a, b = map(int, input().split())

print(f(a,b))

백준은 학교 oj처럼 함수로 입력이 들어오지 않기때문에 직접 입력을 받고 출력도 직접해주는 방식이다.

개인적으로 프로그래머스를 풀다오니 좀 불편하게 느껴졌다.

 

---

2. 이진수

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

def f(n):
    i = 1
    while n//i > 0:
        i *= 2

    i /= 2
    str = ''
    while n > 0:
        if n >= i:
            str += '1'
            n -= i
        else:
            str += '0'
        i /= 2

    while i >= 1:
        str += '0'
        i /= 2
    
    return str

a = int(input())

for i in range(a):
    n = int(input())
    for idx, i in enumerate(reversed(f(n))):
        if i == '1':
            print(str(idx) + ' ', end='')
    print()

내장함수 쓰지 말고 구현해보라고 해서 직접 해봤다.

별 생각 없이 수학시간때 하던 방식 그대로 구현했는데,, 아래처럼 n//2을 해서 구하는 방법이 훨씬 효율적이다.

t = int(input())

for _ in range(t):
    n = int(input())
    i = 0
    
    while n > 0:
        if n%2 == 1:
            print(i, end=' ')
        n = n//2
        i += 1

 

---

3. 최소, 최대

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

n = int(input())

data = list(map(int, input().split()))
min_ = max_ = data[0]

for i in range(1, n):
    a = data[i]
    if max_ < a:
        max_ = a
    if min_ > a:
        min_ = a

print(min_, max_)

 

---

4. 지능형 기차 2

https://www.acmicpc.net/status?user_id=cme10575&problem_id=2460&from_mine=1 

max_ = p = 0

for t in range(10):
    o, i = map(int, input().split())
    p -= o
    if p > max_:
        max_ = p
    p += i
    if p > max_:
        max_ = p
print(max_)

 

---

5. 피보나치 수 5

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

n = int(input())

if n == 0:
    print(0)
else:
    a = 0
    b = 1
    c = a + b
    for i in range(1, n):
        c = a + b
        a = b
        b = c

    print(c)

0일때 처리 안해줘서 틀렸었다.

 

---

6. 일곱 난쟁이

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

def comb(arr, n):
    result =[]

    if n == 0:
        return [[]]

    for i in range(0, len(arr)):
        elem = arr[i]
        rest_arr = arr[i + 1:]
        for c in comb(rest_arr, n-1):
            result.append([elem]+c)

    return result

arr = []
for i in range(9):
    arr.append(int(input()))
    
combs = comb(arr, 7)

for c in combs:
    if sum(c) == 100:
        c.sort()
        for i in c:
            print(i)
        break

itertools 을 사용하는 대신 직접 구현해보았다.

sort()도 사용하지 않고 직접 구현할까 고민하다가 그건 오바인거같아서 그만뒀다.

 

def dfs_comb(lst,n):
	ret = []
	idx = [i for i in range(len(lst))]

	stack  = []
	for i in idx[:len(lst)-n+1]:
		stack.append([i])
	
	while len(stack)!=0:
		cur = stack.pop()

		for i in range(cur[-1]+1,len(lst)-n+1+len(cur)):
			temp=cur+[i]
			if len(temp)==n:
				element = []
				for i in temp:
					element.append(lst[i])
				ret.append(element)
			else:
				stack.append(temp)
	return ret

이건 dfs로 조합을 구하는 코드이다.

(https://medium.com/@dltkddud4403/python-%EC%88%9C%EC%97%B4-%EC%A1%B0%ED%95%A9-%EA%B5%AC%ED%98%84-5e496e74621c)