2주차

1) 문제풀이

2178번: 미로 탐색 (acmicpc.net)

2178번: 미로 탐색

from collections import deque
n, m = map(int,input().split())
array = []
for _ in range(n):
    array.append(list(map(int,input())))
q = deque()
startX = 0 # Row
startY = 0 # Column
q.append((startX,startY))
visited = [[0 for _ in range(m)] for _ in range(n)]
visited[startX][startY] = 1
dx = [-1,0,1,0] # 북 동 남 서
dy=  [0,1,0,-1] # 북 동 남 서

while q:
    x, y = q.popleft()
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<n and 0<=ny<m:
            if array[nx][ny] == 1 and visited[nx][ny] == 0:
                #visited가 0이라는 것은 아직 방문하지 않음을 의미
                q.append((nx,ny))
                visited[nx][ny] = visited[x][y] + 1

print(visited[n-1][m-1])

많은 문제를 풀어본 결과 a라는 위치에서 b라는 위치에 도달하기 위한 알고리즘은 DFS보다 BFS가 더 낫다. 이 문제는 (0,0)의 위치에서 (n-1,m-1)라는 위치로 가야하므로 BFS 알고리즘을 사용했다.

BFS알고리즘은 queue를 이용하는데, 파이썬에는 deque라는 좋은 라이브러리가 있다. deque는 왼쪽, 오른쪽 양쪽의 방향에서 삽입, 삭제가 가능하다. 우선 초기 위치 (0,0)을 deque에 넣어준 다음에 이를 빼서 BFS를 한다. 함수로 구현해도 되지만 while문 전체가 bfs와 같은 의미라서 따로 구현하진 않았다. 방문하지 않았을경우 (visited값이 0인경우) 현재 위치의 vistied값에서 1을 더한다. (한 칸을 더 움직였다는 것을 의미)

 

전형적인 BFS 알고리즘이므로 별다섯개!

 

 

11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net)

11053번: 가장 긴 증가하는 부분 수열

n = int(input())
array = list(map(int,input().split()))
result = [array[0]]

def binary_search(start,end,target):
    if start>end:
        return start
    
    mid = (start+end) // 2
    if result[mid] > target:
        return binary_search(start,mid-1,target)
    elif result[mid] == target:
        return mid
    else:
        return binary_search(mid+1,end,target)

for i in range(1,len(array)):
    if array[i] > result[-1]:
        result.append(array[i])
    else:
        idx = binary_search(0,len(result)-1,array[i])
        result[idx] = array[i]

print(len(result))

위 방법은 binary_search라는 이분탐색 함수를 이용해서 array안에 있는 원소가 result 리스트의 어느 부분에 들어가야 하는지를 찾고, 해당 위치에 값을 넣는다.

풀이 방법에 대한 이해를 먼저하자면

길이가 6이고 array = [10,20,5,6,7,8] 이라고 해보자! 가장 긴 수열은 [5,6,7,8]이 될 것이고 길이는 4이다.

이 [5,6,7,8]을 찾는 과정을 생각해보자. (이 문제에선 길이가 4라는 것이 중요하지 [5,6,7,8]이라는 것이 중요하진 않다. [5,6,7,8]이라는 것을 완벽히 찾는 문제는 플레5 문제에 있다.)

 

for을 돌기에 앞서서 result 리스트 안에 array[0] 값을 넣어놨다. array[1]부터 for문을 도는 과정을 나타내보면

1) result = [10] 

2) result = [10,20]

3) result = [5,20]

4) result = [5,6]

5) result = [5,6,7]

6) result = [5,6,7,8]

이 된다. 이런 방식으로 할 경우 최대길이를 구할 수 있다.

 

다른 예제로 길이가 7이고 array = [10,11,15,5,6,3,20] 일 경우 답은 [10,11,15,20]로 최대 길이는 4이다.

1) result = [10]

2) result = [10,11]

3) result = [10,11,15]

4) result = [5,11,15]

5) result = [5,6,15]

6) result = [3,6,15]

7) result = [3,6,15,20]

결과적으로 result의 값은 다르지만 최대 길이가 4인 것은 유효하다.

 

 

5567번: 결혼식 (acmicpc.net)

5567번: 결혼식

 

n = int(input())
m = int(input())
member = [[] for _ in range(n+1)]
#member[0] 리스트는 사용하지 않음 idx값을 맞추기 위해서 n+1개 호출함
for _ in range(m):
    friend1, friend2 = map(int,input().split())
    member[friend1].append(friend2)
    member[friend2].append(friend1)
deepMember = [0 for _ in range(n+1)]
for i in member[1]:
    deepMember[i] = 1
    for j in member[i]:
        deepMember[j] = 1

deepMember[1] = 0
print(deepMember.count(1))

우선 이 문제는 DFS와 BFS 두 개의 방법으로 풀 수 있다. DFS는 다중포문하고 같은 성질이 있다. 깊이가 4일 경우 4중포문 깊이가 3일 경우 3중포문을 사용한다면 문제를 풀 수 있다. 이 문제에선 친구의 친구까지만 초대하기 때문에 깊이가 2가 된다. 따라서 2중포문이면 문제를 해결할 수 있다.

deepMember라는 친구 or 친구의 친구까지 체크하는 리스트를 만들고 이중 포문을 통해 해결하였다.

본인이 초대되는 경우는 제외하므로 deepMember[1]의 값은 0으로 초기화하였다.

 

밑은 BFS로 푼 방법이다.

from collections import deque
n = int(input())
m = int(input())
member = [[] for _ in range(n+1)]
for _ in range(m):
    a,b = map(int,input().split())
    member[a].append(b)
    member[b].append(a)
q = deque()
q.append(1)
deepMember = [0 for _ in range(n+1)]
while q:
    idx = q.popleft()
    for i in member[idx]:
        if deepMember[i] == 0:
            q.append(i)
            deepMember[i] = deepMember[idx] + 1
cnt = 0
deepMember[1] = 0
print(deepMember.count(1) + deepMember.count(2))

여기서 deepMember 리스트에서 1은 친구, 2는 친구의 친구를 의미한다.

 

코딩테스트 연습 - 숫자 게임 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 숫자 게임

def solution(A, B):
    answer = 0
    total = []
    for i in A:
        total.append([i,1])
    for i in B:
        total.append([i,0])
    total.sort(reverse=True)
   
    CountB = 0
    for i in total:
        if i[1] == 1:
            if CountB > 0:
                CountB -= 1
                answer += 1
        else:
            CountB += 1
            
    return answer

우선 이 문제는 A와 B를 합친 List를 만드는게 중요했다. List를 합치면서 A와 B가 구분이 될 수 있도록 A라면 1을 B라면 0을 함께 동봉? 해서 total이라는 List에 넣어줬다.

나는 이 문제를 접근할 때 어떻게 하면 틀릴까? 라고 먼저 생각해보았고 틀리는 대표적인 유형은 B의 제일 큰 점수가 A의 제일 작은 점수를 이기면 틀릴 것이라고 생각했다. 그 후 풀이방법을 생각했고 두 개의 리스트를 하나의 리스트로 만들어서 내림차순으로 정렬하는 것을 생각했다.

A에는 1을 B에는 0을 넣었으므로 역순으로 정렬하면 같은 수라면 A가 앞에 기록될 것이다. total을 하나하나 살피면서 B가 나오면 CountB 변수에 1을 더해주고 A가 나오면 CountB 값이 0보다 클 경우 1을 감소시키고 answer은 1을 더하는 방법으로 풀었다.