[SWEA] [파이썬 SW 문제해결 기초] 2. List2

연습문제 풀기 전 강의 듣기. 모르는 것만 정리할거임.

[ 부분집합 알고리즘 ]

1. Loop를 이용하여 확인하고 부분집합 생성하기

bit = [0, 0, 0, 0]
for i in range(2):
  bit[0] = i					# 0번째 원소
  for j in range(2):
    bit[1] = j				# 1번째 원소
    for k in range(2):
      bit[2] = k			# 2번째 원소
      for l in range(2):
        bit[3] = l		# 3번째 원소
        print(bit)		# 생성된 부분집합 출력

☆2. 비트연산자 사용해서 간결하게 부분집합 생성하기

arr = [3, 6, 7, 1, 5, 4]
n = len(arr)		# n: 원소의 개수

for i in range(1<<n):		# 1<<n: 부분 집합의 개수 => 0부터 2^n - 1까지 반복
  for j in range(n):		# 원소의 수만큼 비트를 비교 (원소의 포함 여부 판단 가능)
    if i & (1 << j):	# i의 j번째 비트가 1이면 j번째 원소 출력
      print(arr[j], end=',')
  print()
    
    
'''
예제: arr=[3, 6, 7], n=3
i=5 → 이진수: 101

j    1<<j    이진수       i&(1<<j) 결과          포함 여부
0     1       001      101 & 001= 001(True)     arr[0] 포함
1     2       010      101 & 010= 000(False)    arr[1] 미포함
2     4       100      101 & 100= 100(True)     arr[2] 포함

'''

 

[ 검색 알고리즘 ]

저장되어 있는 자료 중에서 원하는 항목을 찾는 작업
=> 원하는 항목? 목적하는 탐색키를 가진 항목
=> 탐색키? 자료를 구별하여 인식할 수 있는 키

종류: 순차 검색(Sequential Search), 이진 검색(Binary Search), 인덱싱(Indexing)

1. 순차 검색
- 일렬로 되어 있는 자료를 순서대로 검색하는 방법
- List나 연결 List 등 순차구조로 구현된 자료구조에서 유용
- 구현이 쉽지만, 검색 대상이 많은 경우 수행시간의 증가로 비효율적
- 시간복잡도: O(n)

# 1. 정렬되지 않은 자료에서의 검색
def sequentialSearch(a, n, key):
	i = 0
    while i < n and a[i] != key:	# 리스트 범위를 안 넘고 + 찾고자 하는 값(key)이 아니면
    	i = i + 1					# 다음 원소랑 비교

    if i < n: return i		# 원소 동일한 거 찾으면 while문 탈출
    else: return -1			# 리스트 끝까지 다 검색했는데 못 찾아도 탈출


# 2. 정렬된 자료에서의 검색
def sequentialSearch2(a, n, key):
	i = 0
    while i < n ad a[i] < key:		# a[i] > key가 되는 순간 어차피 key가 안 나옴
    	i = i + 1
        
    if i < n and a[i] == key: return i
    else: return -1

 

2. 이진 검색
- 자료의 가운데 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속함
- 목적 키를 찾을 때까지 이진 검색을 순환적으로 반복 수행 ⇒ 검색 범위를 반으로 줄여나감 
- 자료가 정렬된 상태여야 함
- 시간복잡도: O(log N)

# 1. 검색 범위의 시작점과 종료점을 이용하여 구현
def binarySearch(a, key):		# a: 검색할 자료, key: 찾고자 하는 값
	start = 0
    end = len(a) - 1
    while start <= end:
    	middle = start + (end-start)//2
        if key == a[middle]: # 검색 성공
        	return True
        elif key < a[middle]:
        	end = middle-1
        else:
        	start = middle+1
    return False	# 검색 실패
    
    
# 2. 재귀 함수를 이용하여 구현
def binarySearch2(a, low, high, key):
	if low > high:		# 검색 실패
    	return False
    else:
    	middle = (low + high) // 2
        if key == a[middle]:	# 검색 성공
        	return True
        elif key < a[middle]:
        	return binarySearch2(a, low, middle-1, key)
        elif key > a[middle]:
        	return binarySearch2(a, middle+1, high, key)

 

[ 정렬 알고리즘 ]

# 셀렉션 알고리즘
# ex. k번째로 작은 원소를 찾는 알고리즘
def select(list, k):
	for i in range(0, k):
    	minIndex = i
        for j in range(i+1, len(list)):
        	if list[minIndex] > list[j]:	# 최솟값보다 크면 => 새로운 최솟값으로 만들기
            	minIndex = j
        list[i], list[minIndex] = list[minIndex], list[i]	# 자리 바꿔준다
    return list[k-1]	# 인덱스가 0부터 시작하니까 k번째로 작은 값의 인덱스는 k-1

# 선택 정렬
def selectionSort(a):
	for i in range(0, len(a)-1):
    	min = i
        for j in range(i+1, len(a)):
        	if a[min] > a[j]:
            	min = j
        a[i], a[min] = a[min], a[i]

---

이제 문제를 풀어보자. 벌써 쉽지 않을 것으로 예상된다.

4836. 그림과 같이 인덱스가 있는 10x10 격자에 빨간색과 파란색을 칠하려고 한다. N개의 영역에 대해 왼쪽 위와 오른쪽 아래 모서리 인덱스, 칠할 색상이 주어질 때, 칠이 끝난 후 색이 겹쳐 보라색이 된 칸 수를 구하는 프로그램을 만드시오. 주어진 정보에서 같은 색인 영역은 겹치지 않는다.

T = int(input())

for test_case in range(1, T+1):
    N = int(input())
    arr = [[0] * 10 for _ in range(10)]		# 칠해진 영역 저장할 2차원 리스트
    res = 0		# 보라색 칸
    
    for paint in range(1, N+1):
        r1, c1, r2, c2, color = map(int, input().split())
        
        for i in range(r1, r2+1):
            for j in range(c1, c2+1):
                arr[i][j] += color
                if arr[i][j] == 3:
                    res += 1
    print(f"#{test_case} {res}")

이번 문제는 패드에 써가면서 어떻게 풀어야 할지 고민 좀 했다. 2차원 배열 쓰면 되겠다는 아이디어 생각해내고, 어떻게 구현할지 고민하고... 새벽이라 그런가 머리가 잘 안 돌아간다.

 

★2. 1부터 12까지의 숫자를 원소로 가진 집합 A가 있다. 집합 A의 부분 집합 중 N개의 원소를 갖고 있고, 원소의 합이 K인 부분집합의 개수를 출력하는 프로그램을 작성하시오. 해당하는 부분집합이 없는 경우 0을 출력한다. 모든 부분 집합을 만들어 답을 찾아도 된다. 예를 들어 N = 3, K = 6 경우, 부분집합은 { 1, 2, 3 } 경우 1가지가 존재한다.

저한테 왜 이러세요.

T = int(input())
arr = [ i for i in range(1, 13) ]
length = len(arr)

subset = []
    
for i in range(1 << length):
    tmp = []
    for j in range(length):
        if i & (1 << j):
            tmp.append(arr[j])
    subset.append(tmp)
        
for test_case in range(1, T+1):
    count = 0
    n, k = map(int, input().split())
    
    for sub in subset:
        if len(sub) == n and sum(sub) == k:
            count += 1
    print(f"#{test_case} {count}")

아직 익숙해지지 않은 부분집합 구현하기... 비트연산자 가지고 하는 거 기억이 안나서 위로 스크롤 몇 번씩 왔다갔다 함. And 인터넷의 고수님들의 도움... 이 문제는 다시 풀어봐야 할 듯.

 

★3. 코딩반 학생들에게 이진 탐색을 설명하던 선생님은 이진탐색을 연습할 수 있는 게임을 시켜 보기로 했다. 짝을 이룬 A, B 두 사람에게 교과서에서 각자 찾을 쪽 번호를 알려주면, 이진 탐색만으로 지정된 페이지를 먼저 펼치는 사람이 이기는 게임이다. 예를 들어 책이 총 400쪽이면, 검색 구간의 왼쪽 l=1, 오른쪽 r=400이 되고, 중간 페이지 c= int((l+r)/2)로 계산한다. 찾는 쪽 번호가 c와 같아지면 탐색을 끝낸다. A는 300, B는 50 쪽을 찾아야 하는 경우, 다음처럼 중간 페이지를 기준으로 왼쪽 또는 오른 쪽 영역의 중간 페이지를 다시 찾아가면 된다. 책의 전체 쪽수와 두 사람이 찾을 쪽 번호가 주어졌을 때, 이진 탐색 게임에서 이긴 사람이 누구인지 알아내 출력하시오. 비긴 경우는 0을 출력한다.

T = int(input())

for test_case in range(1, T+1):
    P, P_a, P_b = map(int, input().split())
    
    a = [i for i in range(1, P+1)]

    startA, startB = 0, 0
    endA, endB = len(a)-1, len(a)-1
    countA, countB = 0, 0
    
    # A 먼저
    while startA <= endA:
        midA = startA + (endA-startA)//2
        if P_a == a[midA]:
            countA += 1
            break
        elif P_a > a[midA]:
            startA = midA+1
            countA += 1
        elif P_a < a[midA]:
            endA = midA-1
            countA += 1
    
    # B 차례
    while startB <= endB:
        midB = startB + (endB-startB)//2
        if P_b == a[midB]:
            countB += 1
            break
        elif P_b > a[midB]:
            startB = midB+1
            countB += 1
        elif P_b < a[midB]:
            endB = midB-1
            countB += 1
    
    winner = 0
    if countA == countB:
        winner = 0
    elif countA > countB:
        winner = 'B'
    elif countA < countB:
        winner = 'A'
    
    print(f"#{test_case} {winner}")

돌렸더니 테스트 케이스 10개 중 8개만 맞은 상황. 나머지 2개는 어디서 뽀록이 난걸까.

def binarySearch(start, end, key):
    count = 0

    while start <= end:
        mid = (start + end)//2
        count += 1
        if key == mid:
            return count
        elif key > mid:
            start = mid
        elif key < mid:
            end = mid

T = int(input())

for test_case in range(1, T+1):
    P, P_a, P_b = map(int, input().split())

    countA = binarySearch(1, P, P_a)
    countB = binarySearch(1, P, P_b)
    
    winner = 0
    if countA > countB:
        winner = 'B'
    elif countA < countB:
        winner = 'A'
    else:
        winner = 0
    
    print(f"#{test_case} {winner}")

일단 예쁘게 정리하고 인덱스 기반 이진 검색에서 그냥 숫자로 이진 검색으로 바꿨다. 근데 mid+1, mid-1을 안 쓰고 그냥 쌩 mid를 썼더니 풀림. 값 기반 이진 검색이라 그런가... 이건 잘 모르겠다. 얘도 나중에 다시 풀어야 할 듯.

 

4. 보통의 정렬은 오름차순이나 내림차순으로 이루어지지만, 이번에는 특별한 정렬을 하려고 한다. N개의 정수가 주어지면 가장 큰 수, 가장 작은 수, 2번째 큰 수, 2번째 작은 수 식으로 큰 수와 작은 수를 번갈아 정렬하는 방법이다. 예를 들어 1부터 10까지 10개의 숫자가 주어지면 다음과 같이 정렬한다. 10 1 9 2 8 3 7 4 6 5 주어진 숫자에 대해 특별한 정렬을 한 결과를 10개까지 출력하시오.

T = int(input())

for test_case in range(1, T+1):
    N = int(input())
    num = list(map(int, input().split()))
    num = sorted(num)
    new_sort = []
    
    for i in range(len(num)):
        if (i % 2) == 0:
            new_sort.append(num.pop())
        elif (i % 2) == 1:
            new_sort.append(num.pop(0))
        if len(new_sort) == 10:
            break
    
    res = ''
    for i in range(len(new_sort)):
        res += str(new_sort[i]) + ' '

    print(f"#{test_case} {res}")

 이번 문제는 좀 쉬웠다. 비록 조건을 제대로 안 봐서 2번 fail 맞긴 했지만... 그리고 리스트를 못 풀어서 애먹다가(*도 안되고, str이 아니라서 join도 안되서 애먹음) 그냥 심플하게 문자열에 하나하나 추가하는 방법으로 해결했다.

 

이제 4문제 풀었는데 벌써 오전 3시 반... 아직 남은 게 산더미인데 걍 망한 듯.
내일 하루종일 string, stack1/2, queue, linked list, tree 풀고. 다음 날 3단계 절반 이상 해야 기출 문제 풀러 갈 수 있을 것 같다.. 기출문제 풀고 익히는 데도 한 세월 걸릴 거 같은데. 하아아아