백준 알고리즘 15650 - python Python

[문제] 백준 알고리즘 15650 - python (N과 M(2))

N과 M(1)에서 중복되는 수열을 출력하지 않는 조건과 오름차순 출력이 추가된 문제.

그래서 N과 M(1)의 내용을 조건에 맞게 수정해서 풀었다.


1. 중복 제거를 위해, 순열을 담은 list를 오름차순으로 정리한 후(sorted()), 문자열로 만든다.

2. 출력용 list에 그 문자열이 없다면, append한다.

3. 출력용 list를 한 줄씩 출력한다.

[Code]
N, M = map(int, input().split())
visited = [False] * N
out, out_all = [], []

def solve(depth, N, M):
if depth == M:
out_str = ' '.join(map(str, sorted(out)))
if out_str not in out_all:
out_all.append(out_str)
return
for i in range(N):
if not visited[i]:
visited[i] = True
out.append(i+1)
solve(depth+1, N, M)
visited[i] = False
out.pop()
solve(0, N, M)

for i in out_all:
print(i)

답은 맞았지만 중간에 Sort를 사용해서 효율적이지 않고, 시간이 꽤 오래 걸렸다.

다른 사람들의 풀이 방식을 참조해보니, 더 효율적이고 간단한 방식으로 풀어놓았다.

바로, 이전의 idx 값을 넘겨주어, idx 이하는 진행하지 않는 것이다.

마치 1차원 배열 A의 모든 두 요소를 비교할 때, 아래의 방식으로 시간복잡도를 줄이는 것과 비슷하다는 느낌을 받았다.

for i in range(len(A)-1):
for j in range(i+1, len(A)):
if A[i] < A[j]:
....

효율적인 힌트를 얻고 내 방식에 맞춰서 다시 풀어보았다. N과 M(1)에서 달라질 것은 거의 없다.

[Code]
N, M = map(int, input().split())
visited = [False] * N
out = []

def solve(depth, idx, N, M):
if depth == M:
print(' '.join(map(str, out)))
return
for i in range(idx, N):
if not visited[i]:
visited[i] = True
out.append(i+1)
solve(depth+1, i+1, N, M)
visited[i] = False
out.pop()
solve(0, 0, N, M)

그런데.. Python... 이것조차 itertools의 combinations로 만들어 놓았다고 한다... 리스펙...

[Code]
from itertools import combinations
N, M = map(int, input().split())
C = combinations(range(1, N+1), M) # iter(tuple)
for i in C:
print(' '.join(map(str, i))) # tuple -> str

백준 알고리즘 10250 - python Python

[문제] 백준 알고리즘 10250 - python (ACM 호텔)


호텔의 H(층의 수), W(호의 수)와 N 번째 손님이 주어진다. (사실상 W의 의미는 H*W가 N보다 크기만 하면 된다.)

N번째 손님이 채워지는 방법은 간략하게 표현하면, H명이 차면 1호씩 늘어나는 셈이다.

따라서, 최대 호수는 N /H를 올림한 수이고, N % H가 마지막 호수에 남는다.


원래 올림은 math.ceil()을 써야하는데, N, H의 몫과 나머지만으로 해결 가능할 것 같아서 굳이 쓰지 않았다.

N%H가 0일 때만 N/H의 올림을 해도 값이 변함이 없는 것을 이용했다.

나머지가 0이 아닌 모든 경우는 N//H에 +1한 결과가 올림이다.


그래서 간편하게 divmod()를 이용해 div(=N//H)와 mod(=N%H)를 구한 다음,

mod가 0일때는 H와 div를 출력(mod가 0이므로 H로 출력), 그 외에는 mod와 div+1을 출력했다.

이렇게 구상했더니 코드는 아주 간단해졌고, 쉽게 풀렸다.


[Code] 
T = int(input())
for _ in range(T):
H, W, N = map(int, input().split())
div, mod = divmod(N, H)
if mod == 0:
print('{}{:02d}'.format(H, div))
else:
print('{}{:02d}'.format(mod, div+1))

백준 알고리즘 15649 - python Python

[문제] 백준 알고리즘 15649 - python (N과 M(1))

1~N을 이용해서 M개 요소의 조합을 순서대로 만드는 문제.

DFS(Depth First Search)를 구현하는 법을 정확하게 모르는 상태라 한참을 고전했다.

그래서 이번 구현 시에 쓰일 사항들을 간단히 정리해야겠다.

1. visited (탐사 했는지 여부)

2. out (탐사 내용)

3. 재귀 함수 시
- 탈출 조건 : Depth가 M일 때
- 탐사를 안했을 경우 진행
- Depth 탐색 전 : 탐사 시작, 탐사 내용 append
- Depth 탐색 후 : 다음 탐사 준비, 탐사 내용 pop


개인적으로 어려웠기 때문에 이해한 내용을 코드에 적용하느라 주석 처리가 좀 많다.

[Code]
N, M = map(int, input().split())
visited = [False] * N # 탐사 여부 check
out = [] # 출력 내용

def solve(depth, N, M):
if depth == M: # 탈출 조건
print(' '.join(map(str, out))) # list를 str으로 합쳐 출력
return
for i in range(len(visited)): # 탐사 check 하면서
if not visited[i]: # 탐사 안했다면
visited[i] = True # 탐사 시작
out.append(i+1) # 탐사 내용
solve(depth+1, N, M) # 깊이 우선 탐색
visited[i] = False # 탐사 완료
out.pop() # 탐사 내용 제거

solve(0, N, M)


Python 내부 함수 itertools의 permutations를 이용해서 순열을 찾아주는 방법도 있다고 한다.

[Code]
from itertools import permutations
N, M = map(int, input().split())
P = permutations(range(1, N+1), M) # iter(tuple)
for i in P:
print(' '.join(map(str, i))) # tuple -> str

진실 Christianity


하나님은 존재하십니다. 

세상이 진실을 모르고 

부정한다고 해서 

진실이 거짓으로 

바뀌지는 않습니다. 

by Think_why 

백준 알고리즘 2869 - python Python

[ 문제 ] 백준 알고리즘 2869 - python (달팽이는 올라가고 싶다)

낮에 A만큼 올라가는데 밤에 B만큼 미끄러지고, V에 도달하면 종료

     1일               2일           2.x일  => 3일째에 도달한다.

이러한 방식으로 하면 While문을 사용하는 떠올랐지만, 마지막 날은 낮만 올라가도 어짜피 하루를 쓰게 된다.

그래서 뒤에서부터 생각했다. V에서 마지막 B를 빼면 매일 (A-B)만큼씩 올라가게 된다.

수식을 정리하면, (V-B) / (A-B)일 동안 올라가게 된다.

이 때, 이 수식 결과 값이 소수점일 수도 있으니 올림을 해주면 된다. 2.x일은 결국 3일로 취급되기 때문이다.


구현 코드에서 올림을 사용한 방식이 2가지가 있다.

1. Python 내장함수 : math.ceil

2. 그냥 구현이지만 그나마 Python스럽게

[Code1]
import math
A, B, V = map(int, input().split())
crawl = math.ceil((V-B) / (A-B))
print(crawl)

[Code2]
A, B, V = map(int, input().split())
crawl = (V-B) / (A-B)
print(int(crawl)+1 if crawl % 1 > 0 else int(crawl))

추가 설명: A = 1.x일 때, A % 1 = 0.x가 나온다.

1 2 3 4 5