2024-03-06 AI 코딩 TIL

튜터님 강의

완전 탐색

map함수

map(함수, 리스트)

받은 리스트에게 모두 함수를 적용시키고 싶을때!

그냥 하면 함수명으로 나옴

그래서 리스트로 만들어 주어야함 

아니면 이렇게도 가능합니다.

 

for i, num in enumerate(input_list, 1):

1씩 증가 하는 i값이 같이 반복문에 들어간다.

(input_list, 1)의 1은 시작 값이 1로 설정

 

이분탐색

경우의 수를 절반씩 줄여가면서 만들어야 하는 경우

너무 많아서 선형식으로 계산하게 되면 시간 초과가 되어버리는 경우에는
이분탐색으로 하는 것이 유용하다.

이렇게 계산 하는 방법의 시간은 log₂n으로 줄어들게 된다!

 이분탐색은 정렬이 되어있다는 가정하에 사용이 가능합니다!

key이용하기

 

lambda 사용하기

람다는 일회용 함수!

 

---

강의를 듣고 오늘의 문제 풀이!!

- 문제 01번 풀이
    - 문제 (링크 혹은 번호) : 색종이
    
   설명
    
    여기서 저는 색종이를 포갠다는 개념을 평면으로 생각한다기 보다 점으로 생각했습니다.
    
    이 문제의 특성 상 좌표는 [0, 0] 부터 [100, 100]까지 점위에 있고 면으로 보게 되면
    
   

    
    이런 평면에서도 왼쪽 아래의 점이 시작이 되니 저 부분만 동일하면 포개어진다고 생각했습니다. 그래서 좌표에서도 같은 점위치가 있는 부분은 합집합을 이용해서 하나로 만들어 주었습니다.
    

# 10*10 색종이 만들기
def solution(x, y):
    # list 대신 집합을 이용 이것이 시간이 더 짧다.
    set_list = set()
    # x축10배 y축10배 생산
    for i in range(10):
        for j in range(10):
            # xy 좌표를 1씩 이동 시키면서 위치 값을 튜플형식으로 set에 저장 튜플 형식만 저장가능
            set_list.add((x + i, y + j))
    return set_list

# 입력값 받기
n = int(input())
# 합집합으로 겹치는 부분 제거하게 될 통
colored_paper = set()
# 색종이 갯수 만큼 반복 입력
for i in range(n):
    # 색종이 좌표값 띄어쓰기 기준으로 입력으로 나누어서 입력 받기
    paper = list(map(int, input().split()))
    # 기존의 색종이와 새로만든 색종이의 좌표값을 겹치지 않게 합집합으로 합치기
    colored_paper = (colored_paper | solution(paper[0], paper[1]))

print(len(colored_paper))

 

문제 02번 풀이

문제 (링크 혹은 번호) : 최댓값

설명똑같이 반복을 해서 입력을 받아야 하는 상황에서 반복문 안에서 변수를 선언해야 하는데..
for문으로 동적 변수 생성하기 (tistory.com)저는 먼저 최고 값을 찾는 것을 우선으로 두고 최고 값을 찾으면 반대로 최고 값이 있는 위치를 찾아가는 방식으로 해보자라고 생각했습니다!

for문으로 동적 변수 생성하기 (tistory.com)

위에 링크에서 참조 하시면 좋을 것 같습니다😁😁

그냥 변수를 사용하면 다음 반복문 실행에 변수가 덮혀버리게 되니 이점을 보완하기 위해 구글링을 해서 동적변수를 사용하는 방법을 알았습니다!.

여기서 저는 동적 변수라는 것을 사용해서 만들었습니다.

for i in range(1, 10):
    # 1번 줄부터 9번 줄까지 쭉 받아서 리스트에 넣기
    globals()["line{}".format(i)] = list(map(int, input().split()))
    # 리스트중에서 최고 값을 뽑아서 변수 만들기
    globals()["max_line{}".format(i)] = max(globals()['line{}'.format(i)])

# 만들어진 max 값 리스트에 넣어서 한 줄로 만들기
max_max = []
for i in range(1, 10):
    max_max.append(globals()['max_line{}'.format(i)])

# 그중에 또 최고 값 찾기
first_value = max(max_max)
print(first_value)
# 반복문 탈출용 플레그
flag = False
# 최고 값을 찾았으니 최고 값이 위치하고 있는 좌표 값 찾기
for i in range(1, 10):
    # 만약에 최고 값이 그라인중에 최고 값이랑 동일 하다면 반복문 진입
    if globals()['max_line{}'.format(i)] == first_value:
        # 여기서는 기존의 라인[21 77 45 35 28 75 90 76 1] 중에서 최고 값이 있는 위치 찾기
        for j in range(1, 10):
            # 리스트는 0 부터 시작이고 우리가 아는 좌표는 1부터 시작이니 -1 이든 +1이든 달아주어야함
            if globals()['line{}'.format(i)][j - 1] == first_value:
                # 좌표 위치 표시
                print(f"{i} {j}")
                # 답을 찾았으니 플래그 온!
                flag = True
                break
    # 플래그가 참이면 탈출!
    if flag:
        break

 

문제 03번 풀이

문제 (링크 혹은 번호) :  수 찾기

설명

이 문제는 번호에 맞는 깃발을 만들어 준다고 생각을 했습니다.

이 부분은 튜터님이 알려주는 방법과는 조금 다른 방법으로 풀었던 것 같습니다.

# 숫자 갯수 입력 (파이썬 에서는 없어도 작동에 문제가 없다...)
n = int(input())
# 리스트 받아 오기
numbers = list(map(int, input().split()))

# 리스트에 있는 숫자를 번호 적힌 깃발로 만들기
for i in numbers:
    globals()["num_flag{}".format(i)] = True

# 정답 입력 받기
m = int(input())
select = list(map(int, input().split()))

# 정답 번호의 깃발을 찾을 때 깃발이 True 라면 1 없으면 오류가 뜨니 except 로 빼서 0
for i in select:
    try:
        if globals()["num_flag{}".format(i)]:
            print("1")
    except KeyError:
        print("0")

문제 04번 풀이

문제 (링크 혹은 번호) : 랜선 자르기

 

설명

처음 문제를 접하고 for문을 써서 1 씩 내려가는 방법을 사용 하였으나…

시간 초과로 인하여 방법을 찾아보았는데.  

이거는 재귀 함수를 써야 하는 방법 이였습니다.

가장 긴 랜선을 기준으로 반으로 나누고 그 반으로 가능한 지점을 찾았을 때 
거기서 부터는 다시 그것보다는 긴 방법을 찾는 방안으로 찾는 것이였습니다. 

# k와 n값 입력
k, n = map(int, input().split())
# n개 나올 수 있는 길이
answer = 0
# k개 라인 종류 받아오기
line = []
# k번 길이 입력
for i in range(k):
    line.append(int(input()))
# k개 랜선 중에 가장 긴 라인 찾기
line_max = max(line)

# 라인 찾는 함수
def binary(low, high):
    # 최고 길이가 최저 길이 보다 작아 졌을 때 기저 사례~!
    if high <= low:
        return
    # 함수 밖에 변수를 가져올 때 사용
    global n
    global answer
    # 함수가 시작이 되면 가능한 범위 에서 가장 큰 값과 작은 값의 반이 되는 길이를 정함
    mid = (low + high) // 2
    # n개가 될 수 있는지 검사를 위해서 빈통 준비
    temp = 0
    # k개의 라인을 돌면서 하나 씩 mid 의 길이로 잘라 본다.
    for item in line:
        # 자르고 나서 생기는 라인의 갯수를 temp 에 저장
        temp += item // mid
    # 만약에 우리가 원하는 n개의 라인을 만들 수 있다면 그 길이를 answer 에 저장 한다.
    if temp >= n:
        answer = mid
        # 값을 찾았으니 빠져 나가기 위해서 low 에 mid+1 값을 넣고 돌리면 다음 함수가 한 바퀴를 돌 때 맨 처음 if 으로 인해서 나갈 수 있음
        binary(mid + 1, high)
    else:
        # 이 값 으로는 n개를 만들 수 없기 때문에 중앙 값을 high 로 잡고 다시 해보자.
        binary(low, mid - 1)


binary(0, line_max * 2)
print(answer)

 

문제 05번 풀이

문제 (링크 혹은 번호) : 나무 자르기

# 나무 갯수 원하는 나무길이
n, m = map(int, input().split())
# 나무 높이
trees = list(map(int, input().split()))
# 가장 높은 나무
heighten_tree = max(trees)
cut_height = 0


# 재귀 입장
def cut_tree(low, high):

    # 전역 변수 가져오기
    global m
    global cut_height

    # 기저 사례~
    if low > high:
        return

    # 나무 중앙 값
    mid = (low + high) // 2
    taken_tree = 0

    # 나무들 자르자
    for tree in trees:
        if tree > mid:
            taken_tree += tree - mid
    # 자른 나무 양이 목표치 보다 클때
    if taken_tree >= m:
        cut_height = mid
        cut_tree(mid + 1, high)
    # 자른 나무 양이 모자랄 때
    else:
        cut_tree(low, mid - 1)


cut_tree(0, heighten_tree)
print(cut_height)