수학과의 개발자 도전기

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42890

Lv2 문제다!

풀이 아이디어는 쉽게 떠올랐는데, 이를 구현하는데 약간 번거로웠던 문제였다.

문제 이해 

후보키는 테이블 컬럼 중에 유일성과 최소성을 만족하는 컬럼 또는 컬럼의 집합을 의미한다.

유일성은 해당 컬럼 또는 집합으로 모든 튜플을 식별할 수 있어야 한다는 것이고

최소성은 (내가 이해한 바로는) 부분 집합으로도 모든 튜플을 식별할 수 있어야 한다는 것이다. 

유일성 원소를 구하는 건 어렵지 않았다.

itertools의 combinations를 이용해서 컬럼 인덱스를 조합한 배열을 만들어 탐색하면서 해당 조합에 해당하는 값들을 모은 다음 거기서 중복이 없다면, 해당 조합은 유일성을 만족하는 것이라고 생각했다. 

문제는 최소성이었는데, 문제에서 언급된 정의로 이해하자면 유일성을 만족하는 컬럼 집합 중에서 임의의 조합을 만들었을 때 거기서도  모든 튜플을 식별할 수 있어야하는 것이었다. 그래서 유일성을 만족하는 집합중에서 또 임의의 조합을 구한 뒤 그 조합으로 모든 튜플을 식별할 수 있는지 확인한 후 이를 만족하는 집합들의 갯수를 반환하는 것이라고 이해했다. (아니다)

최소성은 (학번, 이름)으로도 모든 튜플을 식별할 수 있지만 (학번)만으로도 모든 튜플을 식별할 수 있기에 최소성을 만족하지 않는다. 

그래서 유일성을 만족하는 원소 중에서 다른 유일성 원소를  포함하는 걸 모두 없애면 최소성을 만족하는 원소들을 구할 수 있다.

풀이 이해

• itertools의 combinations를 이용해서 컬럼을 조합한 배열을 만든다. (원소가 i개인 임의의 배열을 생성한다. 1 <= i <= 7) 
• 유일성 
  • 조합 원소들을 탐색하면서 해당하는 테이블 값들을 리스트를 만든 후 each result를 temp에 누적한다
  • 결과가 모두 식별되었다면 temp에는 총 n개(전체 튜플 갯수)만큼의 원소가 있을 것이다. 따라서 len(temp) == n이면 유일성을 만족하는 조합이므로 uniqueness에 추가한다 
• 최소성
  • 유일성을 만족하는 원소 중 다른 유일성 원소를 포함하고 있다면 이는 최소성을 만족하지 못한다. 
  • 원소를 포함한다는 것은 A intersection B == A 라는 의미이므로, 이를 set()과 intersection()을 이용한다
  • i번째 원소와 j번째 원소의 교집합이 i번째 원소라면 j 원소를 uniqueness에서 제거한다 
• uniqueness의 원소 갯수를 반환하면 후보키의 최대 갯수다 

- 정답 풀이 :

참고한 블로그

from itertools import combinations

def solution(relation):
    n, m = len(relation), len(relation[0])
    
    candidates = []
    for i in range(1, m + 1):
        candidates.extend(combinations(range(m), i))
    
    uniqueness = []
    for candi in candidates:
        temp = [tuple([item[i] for i in candi]) for item in relation]
        if len(set(temp)) == n:
            uniqueness.append(candi)
            
    answer = set(uniqueness)
    for i in range(len(uniqueness)):
        for j in range(i + 1, len(uniqueness)):
            if len(uniqueness[i]) == len(set(uniqueness[i]).intersection(set(uniqueness[j]))):
                answer.discard(uniqueness[j])
                
    return len(answer)

- 내가 작성한 유일성 코드 + 정답 최소성 코드 ㅋ

유일성 코드 구현할 때 막혔던 부분은 combinations로 만든 조합들을 어떻게 candidates에 추가할 것인가였다.

combinations의 결과를 list로 변경하면 [[0,2], [1,2], ,,,] 같은 형태가 되는데 이를 candidates에 바로 append를 하면 

candiates는 [ [[],[],[],,], [,,,,,], ,,,] 과 같이 삼중 리스트를 가지는데 이는 전개함에 있어 편한 스타일이 아니라 

조합 결과를 어떻게하면 이중 리스트로 만들 수 있을까 고민했다. 

그래서 생각해낸 게 append가 아닌 +를 하자는 것이었다. 리스트 + 리스트 는 단일 리스트이므로 내가 원하는 형태가 나온다고 생각했다. 

위 고민을 끝에 나온 코드는 다음과 같다 

    temp = [i for i in range(m)]
    candidates = []
    for i in range(1, m + 1):
        candidates += list(combinations(temp, i))

from itertools import combinations

def solution(relation):
    n, m = len(relation), len(relation[0])
    
    temp = [i for i in range(m)]
    candidates = []
    for i in range(1, m + 1):
        candidates += list(combinations(temp, i))
        
    # 유일성 만족하는 조합 구하기 
    uniqueness = []
    for candidate in candidates:
        unique = []
        for i in range(n):
            temp = []
            for j in range(len(candidate)):
                temp.append(relation[i][candidate[j]])
            
            if temp not in unique:
                unique.append(temp)   
                
        if len(unique) == n:
            uniqueness.append(candidate)
            
    # 최소성 만족하는 원소 구하기         
    answer = set(uniqueness)
    for i in range(len(uniqueness)):
        for j in range(i + 1, len(uniqueness)):
            if len(uniqueness[i]) == len(set(uniqueness[i]).intersection(set(uniqueness[j]))):
                answer.discard(uniqueness[j])
                
    return len(answer)

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/81302

Lv2 문제다! bfs인 것 같은데 대각선에 있는 경우는 어떻게 처리해야할지 모르겠어서 일반 구현으로 풀었는데 테스트 하나에서 자꾸 틀려서 구글링 했다 

풀이 로직 

• places의 각 원소들을 탐색하다가 P를 만나면 해당 위치를 기준으로 bfs를 돌린다 
• bfs에서는 범위 내에서 상, 하, 좌, 우에 있는 원소 중 
  • 맨하탄 거리가 2이하이고, 방문하지 않았는데 P인 경우 false를 반환하고
  • 맨하탄 거리가 2이하이고, 방문하지 않았는데 O인 경우 bfs를 이어나간다 
• while문을 빠져나왔다는 것은 중간에 False를 한번도 만나지 않은 것이므로 True를 반환한다 

- 정답 풀이 :

특정 P마다 모두 확인해야하므로 bfs 안에 visit를 생성하는 것 같고 

시작한 P의 위치(sx,sy)에서 반경 2 안에 있는 것들에 대해서 탐색해야하므로 abs(nx - sx) + abs(ny - sy) <= 2가 되는 것 같고

탐색하다가 반경 내에서 P를 만나면 안되고

반경 내에서 O인 경우에만 이동할 수 있다 

----> 위 두줄만 이해가 안 간다 

참고한 블로그

from collections import deque

def bfs(places, sx, sy):
    queue = deque([(sx, sy)])
    
    visit = [[0] * 5 for _ in range(5)]
    
    dx = [1, -1, 0, 0]
    dy = [0, 0 , 1, -1]
    visit[sx][sy] = 1
    
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < 5 and 0 <= ny < 5 and (abs(nx - sx) + abs(ny - sy) <= 2) and not visit[nx][ny]:
                if places[nx][ny] == 'P':
                    return False
                if places[nx][ny] == 'O':
                    visit[nx][ny] = 1
                    queue.append((nx,ny))
    return True
    
def solution(places):
    answer = [1] * 5
    
    for t in range(5):
        for i in range(5):
            for j in range(5):
                if places[t][i][j] == 'P':
                    if not bfs(places[t], i, j):
                        answer[t] = 0
                        break
                        
                        
    return answer

- 시도해 본 풀이 :

30 / 31 테스트 통과한 풀이인데, 한 문제가 계속 틀린다.

edge case에 대한 처리가 부족한건가 싶은데 아직은 잘 모르겠다 

풀이 로직

• P의 위치를 location에 저장한다 ([i, j] 형태로)
• 맨하탄 거리를 안 지키는 두 P의 위치를 하나의 배열로 만들어 manhattan에 저장한다 
• manhattan에 있는 P중에서 거리두기를 지키는 경우 count로 센다
• 만약 manhattan에 있는 모든 쌍들이 거리두기를 지킬 경우 count와 len(manhattan)이 같기에 1을 반환하고,
• 아니라면 0을 반환한다
• places의 모든 행렬에 대해 위 과정을 반복한다 

거리두기가 허용되는 경우 

def distance(place):
    n, m = len(place), len(place[0])
    
    location = []
    for i in range(n):
        for j in range(m):
            if place[i][j] == 'P':
                location.append([i, j])
                
    location.sort()
    manhatan = []
    for i in range(len(location)):
        for j in range(i + 1, len(location)):
            x = abs(location[i][0] - location[j][0])
            y = abs(location[i][1] - location[j][1])
            if x + y <= 2:
                manhatan.append([location[i], location[j]])
                
    count = 0         
    for i in range(len(manhatan)):
        first, second = manhatan[i]
        
        if first[0] == second[0]:
            if place[first[0]][first[1] + 1] == 'X':
                count += 1
        elif first[0] + 2 == second[0]:
            if first[1] == second[1]:
                if place[first[0] + 1][first[1]] == 'X':
                    count += 1
        elif first[0] + 1 == second[0]:
            if first[1] + 1 == second[1]:
                if place[first[0]][first[1] + 1] == 'X':
                    if place[first[0] + 1][first[1]] in ['X', 'O']:
                        count += 1
                elif place[first[0]][first[1] + 1] == 'O':
                    if place[first[0] + 1][first[1]] == 'X':
                        count += 1
            elif first[1] == second[1] + 1:
                if place[first[0]][second[1]] == 'X' and place[second[0]][first[1]] == 'X':
                    count += 1
                    
    if count == len(manhatan):
        return 1
    else:
        return 0
    
    
def solution(places):
    
    answer = []
    for i in range(len(places)):
        answer.append(distance(places[i]))
        
    return answer

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12978

Lv2 문제이고, 다익스트라 문제다!

다익스트라 몇 번 들어봤는데 정확한 알고리즘은 이제 공부한다 

다익스트라 알고리즘은 일반적인 그래프 탐색에서 heap 자료구조를 사용하는 알고리즘이라고 이해했다 

풀이 이해 

• 주어진 간선들을 노드 중심인 그래프로 변경한다 (graph 행렬)
• 1번 노드부터 해당 노드가지의 최소 거리를 저장하는 float('inf')로 이루어진 result 배열을 생성한다(이렇게 안 하면 몇몇 테스트에서 실패한다) 
  • 이때 1번 노드에서 1번 노드의 거리는 0이므로 result[1] = 0 으로 설정한다 (이렇게 안 하면 몇몇 테스트에서 실패한다)
• 현재 노드를 x, 이전 노드를 a라고 한다면 (a 노드에서 x 노드의 누적 값) < result[x] (그동안 x까지의 최소 거리) 라면, result[x]를 해당 값으로 변경해주고, 힙에 경로를 추가한다 
• result에서 K 이하인 원소들의 개수를 answer에 저장 후 반환한다 

- 정답 풀이 :

import heapq

def solution(N, road, K):
    graph = [[] for _ in range(N + 1)]
    result = [float('inf')] * (N + 1) # 거리 누적 값이 2001보다 클 수 있으므로 inf
    result[1] = 0 # 1번노드에서 1번 노드 거리는 0이다 
    
    for x, y, z in road:
        graph[x].append([y,z])
        graph[y].append([x,z])  
        
    queue = []
    heapq.heappush(queue,[1, 0]) # 노드 번호, 1번부터의 거리
    
    # dijkstra 함수 시작 
    while queue:
        a, b = heapq.heappop(queue)       
        for x,y in graph[a]:
            if b + y < result[x]:
                result[x] = b + y
                heapq.heappush(queue, [x, b + y]) 
    # 함수 끝 
                        
    answer = 0
    for i in range(1, len(result)):
        if result[i] <= K:
            answer += 1
            
    return answer

- 시도해본 풀이 : 

나름 그래프 구현한다고 해봤는데 잘 안 풀렸던 풀이다!

그래프 탐색을 위해 [노드번호, 1번부터 해당 노드까지의 거리]를 queue에 추가한다

result에는 1번부터 i번째 노드까지의 최소 길이들을 누적한다 

queue로 탐색하면서 방문하지 않은 노드를 탐색하고, 거리를 계산해서 result의 값을 바꿔준다 

전체 거리 중에 K이하인 원소의 갯수를 세서 반환한다 

정답 풀이와 비교하자면

queue는 순차적으로 탐색하는 것이 아닌 거리가 짧은 순서대로 탐색을 진행한다. 이를 위해 heapq를 사용한다 

visit 배열을 사용하지 않는다

def solution(N, road, K):
    graph = [[] for _ in range(N + 1)]
    for x, y, z in road:
        graph[x].append([y,z])
        graph[y].append([x,z])
        
    queue = [[1, 0]] # 노드 번호, 1번부터의 거리 
    result = [2001] * (N + 1)
    visit = [0] * (N + 1)
    visit[0], visit[1], result[1] = 1, 1, 0
    
    while queue:
        a, b = queue.pop(0)       
        for x,y in graph[a]:
            if not visit[x]:
                visit[x] = 1
                result[x] = min(result[x], b + y)
                queue.append([x, result[x]])
                
    answer = 0
    for i in range(1, len(result)):
        if result[i] <= K:
            answer += 1
            
    return answer

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/77485

Lv2 문제고, 스스로 푼 문제다!

시간은 70분 걸렸다

주의해야할 점

• 2번 시계 방향으로 원소를 옮기면 해당 줄에서 중복된 값이 입력되므로, 각 진행 방향의 역방향으로 값을 옮겨야 원하는 행렬이 된다    (8, 9, 10을 왼쪽에서 오른쪽으로 옮기게 되면 8, 8, 10 -> 8, 8, 8로 변경되므로 8,8,9와는 다른 값이다)
• edge 값은 ni에 미리 저장한후 방향에 맞는 값으로 바꿔준다 

풀이 로직 

queries의 원소 갯수만큼 회전을 진행하는데, 각 회전마다 최솟값을 모아서 출력한다 

바로 떠오른 풀이 로직 순서는 다음과 같다. 

1. 문제에 해당하는 행렬 만들기 

: 행마다 나오는 숫자 바로 만들기 어려워서 그냥 전체 수를 하나의 배열로 만든 뒤, columns 길이 만큼씩 잘라서 rows만큼 반복해서 matrix를 생성했다 

2. queries에 주어진 위치들은 실제 행렬 위치 +1, +1 이므로 queries 각 원소에 -1을 해준다 

3. result에는 각 회전시 지나가는 모든 숫자들을 추가한다. (매번 최댓값을 비교하면 시간이 오래 걸릴 것 같아서, 해당 하는 숫자들 다 모아놓고 마지막에 최댓값을 출력하려고 했다)

4. 시계 방향으로 원소 옮기기 

첫 번째 주의해야할 점에서 언급한 것처럼 주어진 방향과 반대되는 방향으로 로직을 만들었다. 

range에 해당 값은 print(matrix) 해가면서 맞췄다 

3번째와 4번째 방향을 처리할 때 좀 어려웠다 

3. 옮길 때 edge 값 처리하는 방법 

회전을 진행하면서 가장 끝 위치에는 이전 값으로 덮어져서 따로 저장해야한다.

이는 n1 ~ n4로 미리 설정해서 원래 값을 보존한 뒤 경우에 맞춰서 추가하면 된다 

(각 방향에 대한 설명 구체적으로 필요할 것 같음)

- 정답 풀이 : 

def solution(rows, columns, queries):
    temp = [i for i in range(1, rows * columns + 1)]
    matrix = []
    index = 0
    for _ in range(rows):
        matrix.append(temp[index : index + columns])
        index += columns
         
    answer = []
    for query in queries:
        a1, a2, b1, b2 = query
        a1, a2, b1, b2 = a1 - 1, a2 - 1, b1 - 1, b2 - 1
        result = []
        n1, n2, n3, n4 = matrix[a1][b2], matrix[b1][b2], matrix[b1][b2], matrix[b1][a2]
        for i in range(b2, a2, -1):
            matrix[a1][i] = matrix[a1][i - 1]
            result.append(matrix[a1][i])

        for i in range(b1, a1, -1):
            if i == a1 + 1:
                matrix[i][b2] = n1
            else:
                matrix[i][b2] = matrix[i - 1][b2]
            result.append(matrix[i][b2])
                 
        for i in range(a2, b2):
            if i == b2 - 1:
                matrix[b1][i] = n3
            else:
                matrix[b1][i] = matrix[b1][i + 1]
            result.append(matrix[b1][i])
                
        for i in range(a1, b1):
            if i == b1 - 1:
                matrix[i][a2] = n4
            else:
                matrix[i][a2] = matrix[i + 1][a2]
            result.append(matrix[i][a2])
            
        answer.append(min(result))
            
            
    return answer