1920 수 찾기
전형적인 binary search 문제였고, 이분탐색을 위해 먼저 정렬을 해주었다. 정렬 후 각 숫자들에 대해 모두 binary search 알고리즘을 적용해주었다. 이때, 한가지 다른 점은 flag를 각 숫자마다 0으로 설정해놓고 숫자를 찾으면 flag = 1, 없으면 그대로 0으로 설정을 해서 마지막에 flag 값에 따라 숫자 유무를 검사해서 1 혹은 0을 출력해주는 형식으로 진행해주었다.
binary search에 대해 간단히 설명하면, 반씩 쪼개서 탐색을 하는 알고리즘인데 탈출 조건은 start와 end가 서로 엇갈리는 순간이다. 즉, start <= end 까지만 탐색을 하는데, 참고로 이때 사람에 따라 start는 left로, end는 right로 쓰기도 한다. 매 탐색마다 mid를 설정해주는데, 말 그대로 가운데 인덱스를 말한다. 따라서 left + right를 반으로 나눈 몫을 할당해주고, 만약 인덱스가 mid일 때 값이 target과 같다면 값을 찾은 것이므로 출력해준다.
값이 target과 다를 때가 중요한데, 만약 target보다 mid에서의 값이 더 크다면, 정렬이 되어있는 상태이기 때문에 내가 찾는 target은 반드시 mid에서의 값보다 왼쪽에 있다고 말할 수 있으므로 반으로 잘랐을 때 왼쪽 부분을 검사해야한다. 따라서, end를 mid - 1로 설정해줌으로써 전체를 다시 부분으로 한정해서 생각해주게 된다. 쉽게 말해서 30cm짜리 토막에서 10cm 지점을 찾는다고 하면, 이분탐색에서 맨 처음에 15cm지점을 탐색하게 되고 10cm는 15cm보다 작으므로 토막의 왼쪽 부분을 탐색해야만 하고 그러므로 0~30 cm 토막이 아니라 이제는 0~14cm 토막을 탐색하면 된다. 딱 15cm지점을 탐색하지 않는 이유는 이미 15cm 가 target과 같은지 비교했을 때 다르다고 판별했기 때문에 포함시키지 않아도 되는 것이다.
만약 target이 mid에서의 값보다 크다면? 위에서와는 반대로 end = mid - 1이 아니라 이제는 start 지점을 앞으로 당겨줘야 하므로 mid + 1 = start로 설정해주면 된다.
이런식으로 반절씩 탐색하면 값이 있을 때 값을 반환하고 없다면 결국 나중에 start와 end가 서로 엇갈리는 지점이 나와서 while문을 빠져나오게 된다.
n = int(input())
A = list(map(int, input().split()))
m = int(input())
B = list(map(int, input().split()))
A.sort()
length = len(A)
for i in range(m):
target = B[i]
flag = 0
left = 0
right = length - 1
while left <= right:
mid = (left + right) // 2
if A[mid] == target:
flag = 1
print(1)
break
elif A[mid] > target:
right = mid - 1
else:
left = mid + 1
if flag == 0:
print(0)
15649 N과 M (1)
처음에는 permutation 문제인줄 알고 itertools에서 permutation 함수를 import 해서 사용했는데, 백트래킹 파트이므로 문제의 의도가 그것이 아니었을 것이라 그렇게 풀면 안된다고 생각한다. 그래서 사용한 방법이 스택을 사용하는 건데, 아래에서 서술하는 두가지 알고리즘은 서로 거의 같은데 살짝 다르다.
일단 알고리즘 자체는 재귀 형태로, stack 을 이용한다. 탈출 조건은 길이를 충족했을 때인데, 예를 들어 이렇다. 입력값이 4 2라고 하면 4P2를 구해야하는데, 이때 탈출 조건은 길이가 2가 됐을 때이다. 처음에 1을 넣으면 [1]이 되고 탈출 못하므로 다시 들어가서 [1,2]를 만든다. 이때 탈출 가능하므로 [1,2]를 출력하고 탈출한다. 탈출하면 s.pop()으로 넘어가므로 2가 pop된다. 그럼 다시 [1]이 되고, 그 다음 [1,3]이 된다. 그럼 탈출 가능하므로 출력하고 3을 pop시킨다. [1,4]도 마찬가지이고, for문을 다 돌아서 [1,4]까지 출력하고 나면 마지막에 [1]도 pop돼서 빈 리스트가 된다. 그 다음 for문에서 i=2로 넘어가고, [2]로 시작해서 위와같은 형태를 반복한다. 핵심 포인트는 [1]로 시작해서 1,2 / 1,3 / 1,4를 모두 다루고 [2]로 시작하고 다시 쭉 다룬다는 것이었다.
# 첫 번째 방법
n, m = list(map(int, input().split()))
s = []
def dfs():
if len(s) == m:
print(' '.join(map(str, s)))
return
for i in range(1, n + 1):
if i not in s:
s.append(i)
dfs()
s.pop()
dfs()
두번째 방법은, 위와 맥락은 같은데 s = []를 선언하지 않는다는 것이 포인트였다. 이게 가능한 이유는 재귀라는 것 자체가 stack형태였기 때문이었다. 그래서 dfs2를 부를 때마다 리스트를 새로 만들어주는 것이다. 위와같이 예시를 입력값 4 2라고 하자. 첫번째에는 빈리스트가 만들어질 것이고, 두번째에는 [1]리스트가, 그 다음에는 [1, 2] 리스트가 만들어진다. 그리고 [1,2]는 탈출조건을 만족하므로 return으로 없애주고, 다시 [1]로 돌아온다. 그럼 여기서 [1,3]이 만들어지고, 출력하고 탈출한다. [1]로 돌아가서 [1,4]가 되고 출력하고 탈출하고를 반복한다. 그리고 [2]로 넘어가서 이 과정을 반복한다.
정리하자면, 알고리즘 자체는 첫번째 방법과 같았는데 다른 점은 s = []를 선언하지 않고 함수에 직접 리스트를 넘겨준다는 것과, 재귀로 불러올 때 리스트+리스트를 이용해서 [1]을 [1,2]로 만드는 과정이 포인트였다.
함수에 빈 리스트를 넘겨준다는 생각 자체를 안해봐서 좋은 풀이를 배웠다고 생각한다. 또한, 리스트 + 리스트라는 코드 자체를 잘 안써서, 생각해볼법한 시간이었다.
# 두 번째 방법
n, m = map(int, input().split())
def dfs2(arr):
if len(arr) == m:
print(' '.join(map(str, arr)))
return
for i in range(1, n + 1):
if i in arr:
continue
dfs2(arr+[i])
dfs2([])
