문제설명

대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개의 나선 모양처럼 점점 큰 타일을 붙인 형태였다. 타일 장식물의 일부를 그리면 다음과 같다.

그림에서 타일에 적힌 수는 각 타일의 한 변의 길이를 나타낸다. 타일 장식물을 구성하는 정사각형 타일 한 변의 길이를 안쪽 타일부터 시작하여 차례로 적으면 다음과 같다. [1, 1, 2, 3, 5, 8, …] 지수는 문득 이러한 타일들로 구성되는 큰 직사각형의 둘레가 궁금해졌다. 예를 들어, 처음 다섯 개의 타일이 구성하는 직사각형(위에서 빨간색으로 표시한 직사각형)의 둘레는 26이다.

타일의 개수 N이 주어질 때, N개의 타일로 구성된 직사각형의 둘레를 return 하도록 solution 함수를 작성하시오.

제한 사항

N은 1 이상 80 이하인 자연수이다.

입출력 예

풀이

이 문제는 동적프로그래밍으로 차근차근 작은 거 부터 실행해나가며 된다. 

def solution(N):
    #메모이제이션
    dp = [0] * int(N+2)
    
    if N == 1:
        return 4
    if N == 2:
        return 6
    dp[0], dp[1], dp[2] = 0, 1, 1
    
    for i in range(3, N+2):
        dp[i] = dp[i-1] + dp[i-2]

    return 2*dp[N-1] + 4*dp[N]

문제

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

#BFS로 미로 탈출 알고리즘 정의
def bfs(maze, i, j, N, M):
    visited = [] #방문한 노드
    queue = [[i, j]] #BFS로 사용될 큐
    distance = [[0 for _ in range(M)] for _ in range(N)] #해당 지점까지의 거리를 담는 리스트
    distance[0][0] = 1 #첫 시작은 1
    
    while queue: 
        [i, j] = queue.pop(0) #BFS 큐에 넣어줌
        visited.append([i, j]) #방문 리스트에 쌓아줌
        
        #상하좌우 탐색
        if i < N-1 and maze[i+1][j] == 1 and [i+1, j] not in visited and [i+1, j] not in queue:
            queue.append([i+1, j])
            distance[i+1][j] = distance[i][j] + 1
        if j < M-1 and maze[i][j+1] == 1 and [i, j+1] not in visited and [i, j+1] not in queue:
            queue.append([i, j+1])
            distance[i][j+1] = distance[i][j] + 1
        if j > 0 and maze[i][j-1] == 1 and [i, j-1] not in visited and [i, j-1] not in queue:
            queue.append([i, j-1])
            distance[i][j-1] = distance[i][j] + 1
        if i > 0 and maze[i-1][j] == 1 and [i-1, j] not in visited and [i-1, j] not in queue:
            queue.append([i-1, j])
            distance[i-1][j] = distance[i][j] + 1
            
    return distance[N-1][M-1] #마지막 도착지의 거리를 반환

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

예제 입력 1

7

6

1 2

2 3

1 5

5 2

5 6

4 7

예제 출력 1

4

n = int(input())
m = int(input())
adj = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
count = 0

for _ in range(m):
    x, y = map(int, input().split())
    adj[x].append(y)
    adj[y].append(x)

    
def dfs(now_pos):
    global count
    count += 1
    visited[now_pos] = True
    for next_pos in adj[now_pos]:
        if not visited[next_pos]:
            dfs(next_pos)
dfs(1)
print(count - 1)

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력 1

5 17

예제 출력 1

4

from collections import deque
MAX = 100001
n, k = map(int, input().split())
array = [0] * MAX

def bfs():
    q = deque([n])
    while q:
        now_pos = q.popleft()
        if now_pos == k:
            return array[now_pos]
        for next_pos in (now_pos - 1, now_pos + 1, now_pos * 2):
            if 0 <= next_pos < MAX and not array[next_pos]:
                array[next_pos] = array[now_pos] + 1
                q.append(next_pos)


>>>print(bfs())

생각해봤는데 dfs 랑 bfs를 언제쓸까라는 생각을 해보았다

결론적으로

• DFS :  방문해야하는 노드의 수가 많고 / 모든 노드의 수를 방문해야할 때
• BFS : 최단 거리 등 내가 원하는 노드만 방문해야할 때

이렇게 나눠서 쓰는게 맞는 거 같다 ㅎㅎ

1.이진 탐색 (Binary Search)

• 탐색할 자료 둘로 나누어 해당 데이터가 있을만한 곳 탐색
• 순차탐색과 비교해보면 이진탐색이 훨씬 더 효율적인 것을 알 수 있다

[저작자] by penjee.com

2. 분할정복 VS 이진 탐색

• 분할 정복 알고리즘(Divide and Conquer)
  • 분할 : 문제를 하나 또는 둘 이상으로 나눔
  • 정복 : 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결 , 그렇지 않다면 다시 나눔
• 이진 탐색
  • 이진 : 리스트를 2개의 서브 리스트로 나눔
  • 탐색
    • 검색할 숫자(search) > 중간값 이면, 뒷 부분의 서브 리스트에서 검색할 숫자 찾는다
    • 검색할 숫자(search) < 중간값 이면, 앞 부분 서브 리스트에서 검색할 숫자 찾는다

3. 코드 생성

-> 이미 정렬되어 있는 상태에서 진행해야 함

• [2,3,8,12,20] 일 때,
  • b_search(data_list , find_data) 함수 생성
    • find_data  : 찾는 숫자
    • data_list : 데이터 리스트
    • data_list의 중간값을 find_data와 비교
      • find_data < data_list[mid] 이면
        • 맨 앞부터  data_list[mid] 에서 다시 find_data 찾기
      • find_data > data_list[mid] 이면
        • data_list[mid] 부터 맨 끝까지 다시 find_data 찾기
      • 그렇지 않으면, data_list[mid] = find_data 이므로 
        • return data_list[mid]

4. 알고리즘 구현

def b_search(data, search):
	print(data)
    if len(data) == 1 and search == data[0]:
    	return True
    if len(data) == 1 and search != data[0]:
    	return False
    if len(data) == 0:
    	return False
    
    
    mid = len(data)//2
    
    if search == data[mid]:
    	return True
    else: 
    	if search > data[mid]:
        	return b_search(data[mid+1:], search)
        else:
        	return b_search(data[:mid], search)


import random
data_list = random.sample(range(100), 10)
>>>data_list.sort()
>>>[2, 5, 19, 21, 42, 47, 67, 72, 92, 98]

>>>b_search(data_list, 67)
>>>[2, 5, 19, 21, 42, 47, 67, 72, 92, 98]
>>>[67, 72, 92, 98]
>>>[67, 72]
>>>[67]
>>>True

5. 알고리즘 분석

-> n 개의 리스트를 매번 2로 나누어 1이 될 때까지 비교 연산 k회 진행하기 때문에

     k + 1 

1. 순차 탐색 이란?

• 데이터가 담겨있는 리스트를 앞에서 부터 하나씩 비교해서 원하는 데이터 찾는 방법

2. 연습

• data_list에 렌덤으로 10 개가 들어있을 때, 원하는 데이터의 위치를 리턴하는 순차탐색 알고리즘 작성
  • 원하는 데이터가 리스트에 없으면 -1 리턴

from random import *

data_list = list()
for num in range(10):
	data_list.append(randint(1,100))
    
>>>data_list
>>>[100, 87, 79, 14, 35, 84, 77, 88, 37, 61]

def sequencial(data_list, search_data):
	for index in rnage(len(data_list)):
    	if data_list[index] == search_data:
        	return index
    return -1


>>> sequencial(data_list, 77)
>>> 6

3. 알고리즘 분석

최악의 경우 리스트 길이가 n일 때, n번 비교해야 함

• O(n)

K번째 수

문제

수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다.

둘째에는 A1, A2, ..., AN이 주어진다. (-109 ≤ Ai ≤ 109)

출력

A를 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다.

예제 입력 1

5 2

4 1 2 3 5

예제 출력 1

2

<핵심>

• 시간 복잡도 : 𝑶(𝑵𝒍𝒐𝒈𝑵)

• 기본 정렬 라이브러리

• 병합 정렬, 퀵정렬, 힙정렬 등 이용하여 문제 해결

n, k = map(int, input().split())
array = list(map(int, input().split()))

array = sorted(array)

print(array[k - 1])

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1 

5 5 4 3 2 1

예제 출력 1 

1 2 3 4

분석하기

시간 복잡도 : 𝑶(𝑵𝒍𝒐𝒈𝑵)

고급 정렬 알고리즘(병합, 퀵, 힙) 이용하거나

파이썬 기본 정렬 라이브러리 이용

n = int(input())
array = []

for _ in range(n):
    array.append(int(input()))
    
array = sorted(array)

for data in array:
    print(data)