수학과의 개발자 도전기

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

스스로 푼 문제다!

문제 이해

처음엔 무슨 문제지 하면서 하나도 이해가지 않았다. 

예제를 기반으로 풀어보니 

- cards의 원소 - 1는 다음 인덱스의 값을 가리키고 있고,

- 0인덱스부터 시작하는데 인덱스 i에서 cards[i]로 이동한 다음,

- cards[i]를 방문하지 않았다면 cards[cards[i]]로 계속 이동하는 문제였다.

위와 같은 방식으로 계속 이동하다가 멈추었을 때가 하나의 박스 세트다. 각 갯수를 저장한 다음 가장 큰 값과 두번째로 큰 값의 곱을 반환하면 된다고 이해했다. 

풀이 이해

• cards의 값과 인덱스를 통일하기 위해서 전체 값에 -1을 한다. 
• 방문하지 않은 인덱스를 구별할 것이므로 visit를 초기화하고, 각 박스 세트의 박스 갯수를 세기위해 box_set도 초기화한다. 
• 인덱스 0부터 순차적으로 진행한는데, 방문하지 않은 인덱스 i에 대해 while문을 돌린다. 
  • index = cards[i]로 설정한뒤 visit[index] == 1이라면 while문을 break 하고
  • 아니라면 방문처리와 갯수를 증가하고 cards[index]로 이동한다.(index = cards[index])
• 갯수가 첫 번째로 많은 세트와 두번째로 많은 세트를 구해야하므로 내림차순으로 정렬한다. 
• 문제에서 세트가 한번에 끝나면 0을 반환하라고 했으므로 box_set가 하나만 있으면 0을 반환하고
• 아니라면 가장 큰 두 값의 곱을 반환한다. 

- 정답 풀이 :

def solution(cards):
    n = len(cards)
    for i in range(n):
        cards[i] -= 1
        
    box_set = []
    visit = [0] * n
    for i in range(n):
        if not visit[i]:
            visit[i], count, index = 1, 1, cards[i]
            while True:
                if visit[index]:
                    box_set.append(count)
                    break
                visit[index] = 1
                count += 1
                index = cards[index]            
    box_set.sort(reverse = True)
    
    if len(box_set) == 1:
        return 0
    else:
        return box_set[0] * box_set[1]

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

스스로 푼 문제다!

문제 이해

처음에는 ranges의 원소가 이해가지 않았는데, [a,b]형태라면 범위는 [a, 마지막 인덱스 + b] (b는 0이하인 정수이므로 더한다)인 것이다. 그래서 [a, 마지막 인덱스 + b]에 해당하는 넓이를 구하면 된다. 

풀이 이해

• 우박수열(sequence) 구한다. i 인덱스에 해당하는 값이 i번째 수열의 값이다. 
• 마지막 x 좌표는 마지막 인덱스 값이므로 last = len(sequence) - 1 해준다.
• ranges 원소를 탐색하면서 시작과 끝이
  • 유효한 경우(end > start) 해당 범위의 넓이(사다리꼴)를 구해서 answer에 추가한다. 
  • 유효하지 않은 경우(end < start)는 -1을 answer에 추가한다.
  • end == start인 경우 넓이는 존재하지 않으므로 0을 answer에 추가한다. 

- 정답 풀이 : 

각 구간에 해당하는 넓이를 각각 따로 계산해서 answer에 추가하니 정답이 떴다!

def get_area(a, b, sequence):
    # 높이가 1인 사다리꼴의 넓이 
    return (sequence[a] + sequence[b]) / 2

def solution(k, ranges):   
    K = k
    sequence = [k]
    while K != 1:
        if K % 2 == 0:
            K //= 2
        else:
            K = K * 3 + 1        
        sequence.append(K)  
    
    last = len(sequence) - 1
    answer = []
    for each in ranges:
        start, offset = each
        end = last + offset
        if end < start:
            answer.append(-1.0)
        if end == start:
            answer.append(0.0)
        if end > start:
            temp = 0
            for i in range(start, end):
                temp += get_area(i, i + 1, sequence)
            answer.append(temp)
       
    return answer

- 시도해본 풀이 :

이 풀이로는 10퍼센트만 맞혔는데, 각 단위 구간에 해당하는 넓이를 areas에 저장한 뒤 start, end가 유효할 때 areas의 start부터 end까지의 합을 구하려했다. 이렇게 구하면 원하는 값이 안 나오는 것 같다.

def get_area(a, b, sequence):
    # 높이가 1인 사다리꼴의 넓이 
    return (sequence[a] + sequence[b]) / 2

def solution(k, ranges):   
    K = k
    sequence = [k]
    while K != 1:
        if K % 2 == 0:
            K //= 2
        else:
            K = K * 3 + 1        
        sequence.append(K)
        
    last = len(sequence) - 1
    areas = [0]
    for i in range(1, last + 1):
        areas.append(get_area(i - 1, i, sequence))
        
    answer = []
    for each in ranges:
        start, offset = each
        end = last + offset
        if 0 <= start <= last and 0 <= end <= last:
            if end < start:
                answer.append(-1)
            if end == start:
                answer.append(0)
            if end > start:
                answer.append(sum(areas[start : end + 1]))
        else:
            answer.append(-1)
                

    return answer

- 문제 : 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)