⭐실력진단 결과

특정 물제를 선택해가며 완전탐색을 진행하는 방법에 대해 배우게 됩니다.

---

기본개념

---

🟢좌표평면 위의 특정 구역 2

📌문제

📌나의 코드

n = int(input())
points = [tuple(map(int, input().split())) for _ in range(n)]

ans = 10e9
for i in range(n):
    # 각 점의 x, y 저장 리스트
    xs = []
    ys = []
    for j in range(n):
        if j == i:
            continue

        xs.append(points[j][0])
        ys.append(points[j][1])

	
    area = (max(xs) - min(xs)) * (max(ys) - min(ys))
    # print(xs, ys, area)
    ans = min(ans, area)
    
print(ans)

🔓풀이

1. 좌표 1개를 건너뛰면서 남은 점들의 x좌표와 y좌표 리스트를 따로 만든다.
2. 점들을 모두 포함해야 하므로 x좌표 중의 최댓값, 최솟값과 y좌표 중의 최댓값, 최솟값을 구해 넓이를 계산한다.
3. 넓이의 최솟값을 구한다.

🟢가장 가까운 두 점 사이의 거리

📌문제

📌나의 코드

Runtime: 119ms, Memory: 25MB

n = int(input())
points = [tuple(map(int, input().split())) for _ in range(n)]

ans = 10e9

for i in range(n):
    for j in range(i + 1, n):
        for k, (x, y) in enumerate(points):
        	# 첫번째 점
            if k == i:
                x1, y1 = x, y
            # 두번째 점
            if k == j:
                x2, y2 = x, y
    
        # print((x1, y1), (x2, y2))
        dist_square = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)
        ans = min(ans, dist_square)

print(ans)

정답코드 - Runtime: 162ms, Memory: 72MB
정답코드보다 더 효율적이다😏

🟢삼각형 만들기

📌문제

📌나의 코드

n = int(input())
points = [list(map(int, input().split())) for _ in range(n)]

# 세 점 중 두 점이 x축 평행과 y축 평행하는지 확인
def parallel(x1, y1, x2, y2, x3, y3):
    if (x1 == x2 and y2 == y3) or (x1 == x2 and y1 == y3) or (x1 == x3 and y1 == y2) \
        or (x1 == x3 and y3 == y2) or (x2 == x3 and y2 == y1) or (x2 == x3 and y3 == y1):
        return True
    return False

# 삼각형 만들어서 넓이 구하기
def make_triangle(a, b, c):
    s = 0
    for i, (x, y) in enumerate(points):
        if i == a:
            x1, y1 = x, y
        if i == b:
            x2, y2 = x, y
        if i == c:
            x3, y3 = x, y
    
    if parallel(x1, y1, x2, y2, x3, y3):
        s = 0.5 * abs((x1 * y2 + x2 * y3 + x3 * y1) - (x2 * y1 + x3 * y2 + x1 * y3))

    return s

max_area = 0
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            area = make_triangle(i, j, k)
            max_area = max(max_area, area)

print(int(max_area * 2))

✏️개선점

1. 넓이에 2를 곱할 거라면 처음부터 0.5를 안 곱하면 된다.
2. 조건문을 더 간단하게 작성할 수 있다.

• 모든 경우의 수를 다 조건으로 작성했을 때

if (x1 == x2 and y2 == y3) or (x1 == x2 and y1 == y3) or (x1 == x3 and y1 == y2) \
    or (x1 == x3 and y3 == y2) or (x2 == x3 and y2 == y1) or (x2 == x3 and y3 == y1):

• 반복되는 부분을 기준으로 조건을 작성했을 때

if (x1 == x2 or x1 == x3 or x2 == x3) and (y1 == y2 or y1 == y3 or y2 == y3):

---

연습문제

---

🟢운행 되고 있는 시간

📌문제

📌나의 코드

n = int(input())
workers = [tuple(map(int, input().split())) for _ in range(n)]

ans = -10e9
for i in range(n):
    count = [0] * 1001
    time = 0
    for j, (s, e) in enumerate(workers):
  		# i번째는 건너뜀
        if j == i:
            continue
        
        # 일하는 시간에 해당하는 인덱스 증가, 끝나는 시간은 포함되지 않음
        for k in range(s, e):
            count[k] += 1
	
    # 일하는 시간을 모두 더함
    for l in range(1001):
        if count[l] >= 1:
            time += 1
            
    ans = max(ans, time)

print(ans)

🟠겹치지 않는 선분 2

📌문제

📌나의 코드

n = int(input())

lines = []
for _ in range(n):
    x1, x2 = map(int, input().split())
    lines.append(((x1, 0) , (x2, 1)))

cross = 0
for i in range(n):
    for j in range(n):
        # 자기 자신은 제외
        if j == i:
            continue

        # 첫번째 선분과 두번째 선분
        line1 = lines[i]
        line2 = lines[j]

        # 첫번째 선분의 시작점 x좌표가 두번째 선분의 시작점 x좌표보다 작고
        # 첫번째 선분의 끝점 x좌표가 두번째 선분의 끝점 x좌표보다 크면
        # 교차하므로 교차하는 선분 2개 증가
        if (line1[0][0] < line2[0][0]) and (line1[1][0] > line2[1][0]):
            cross += 2

# 선분의 개수 중 교차하는 선분 뺀 값
ans = n - cross

# 서로 교차하는 선분이 2개 이상이면 뺀 값이 음수가 나올 수 있으므로 
# ans가 음수면 교차하지 않는 선분이 없다는 의미로 0 출력
if ans < 0:
    print(0)
else:
    print(ans)

✏️개선점

x1이 큰 쪽이 x2가 더 작으면 교차하는 것으로 설정하고, True/False로 교차하지 않는 선분을 세면 더 효율적이다.

❌🟠스승의 은혜 2

📌문제

📌나의 코드

🤔

✏️오답노트

다음 가격을 더했을 때 예산을 벗어나는 경우까지는 생각했으나, 가격을 정렬하여 최대 학생 수를 구하는 방법을 생각하지 못했다.

🔴상해버린 치즈

📌문제

📌나의 코드

# 사람 수, 치즈 수, 치즈 먹은 기록 수, 아픈 기록 수
n, m, d, s = map(int, input().split())

# (몇 번째 사람, 몇 번째 치즈, 몇 초)
ate = [tuple(map(int, input().split())) for _ in range(d)]

# (몇 번째 사람, 몇 초)
sick = [tuple(map(int, input().split())) for _ in range(s)]

# 시간 포함한 치즈 먹은 사람 리스트와 시간을 제외한 치즈 먹은 사람 리스트
cheese = [[] for _ in range(m + 1)]
non_time_cheese = [[] for _ in range(m + 1)]
for p, c, t in ate:
    cheese[c].append((p, t))
    non_time_cheese[c].append(p)

# 각 치즈별 사람 확인 리스트
cheese_check = [True for _ in range(m + 1)]

spoil = []
for i in range(1, m + 1):

    # 치즈 먹은 사람이 아픈 사람보다 적으면 continue
    if len(cheese[i]) < s:
        continue

    for k in range(s):
        # print(i, sick[k][0])
        # 아픈 사람이 치즈 먹은 사람 리스트에 없으면 치즈별 사람 확인 리스트 False
        if sick[k][0] not in non_time_cheese[i]:
            cheese_check[i] = False
            break
        
    for j in range(len(cheese[i])):
        for k in range(s):
            # 치즈 먹은 사람이 아픈 사람과 같을 때 
            # 치즈 먹은 시간이 아픈 시간보다 늦다면 break
            if cheese[i][j][0] == sick[k][0]:
                if cheese[i][j][1] >= sick[k][1]:
                    cheese_check[i] = False
                    break

    # 각 치즈별 사람 확인 리스트가 True이면 상한 치즈에 차즈 리스트 넣기 
    if cheese_check[i]:
        spoil.append(cheese[i])

# print(spoil)

# 시간을 제외한 상한 치즈를 먹었을 사람 리스트
person = [[] for _ in range(len(spoil))]
for i in range(len(spoil)):
    for j in range(len(spoil[i])):
        # 한 치즈를 여러 번 먹은 사람이 있으므로
        # 사람 리스트에 없는 사람일 경우 추가
        if spoil[i][j][0] not in person[i]:
            person[i].append(spoil[i][j][0])

# print(person)


ans = 0

# 상한 치즈별 사람 리스트 중 최대 길이가 
# 아플 수 있는 최대 사람의 수
for p in person:
    if ans <= len(p):
        ans = len(p)

print(ans)

✏️개선점

모든 테스트케이스마다 틀린 점 찾아서 일일이 수정하는 건 아닌 것 같다...
가능한 경우의 수를 처음부터 찾아보자

🟢개발자의 순위

📌문제

📌나의 코드

k, n = map(int, input().split())

# 경기별 순위
ranking = [tuple(map(int, input().split())) for _ in range(k)]

# 개발자별 순위
cnt = [[0] * (n + 1) for _ in range(k)]
for i in range(k):
    for j in range(n):
        num = ranking[i][j]
        cnt[i][num] = j + 1

ans = 0
for i in range(1, n + 1):
    for j in range(1, n + 1):

        # 새로운 개발자와 비교하면 현재가 비교보다 높은 경기 수 초기화
        immut = 0

        for m in range(k):
            if j == i:
                continue
            
            # 현재 개발자보다 비교하는 개발자 순위가 더 높을 경우 
            # 다음 경기로
            if cnt[m][i] > cnt[m][j]:
                continue

            immut += 1

        # 현재가 비교하는 개발자 순위보다 높은 경기가 총 경기 수와 같으면
        # 불변의 순위로 정답 1 증가
        if immut == k:
            ans += 1

print(ans)

✏️개선점

변하지 않는 순위의 수를 셀 필요없이 순위가 변하면 False, 변하지 않으면 True로 쉽게 작성할 수 있다.

🟢이상한 폭탄 2

📌문제

📌나의 코드

n, k = map(int, input().split())
bomb = [int(input()) for _ in range(n)]

# 폭발 폭탄이 없으면 -1
ans = -1
for i in range(n):
    # 현재 폭탄 번호
    a = bomb[i]
    for j in range(i + 1, n):
        # 비교할 폭탄 번호
        b = bomb[j]

        # 현재 폭탄과 같은 번호라면 거리를 구한다.
        if a == b:
            dist = j - i
            # 거리가 k 이내이면서 현재까지 저장된 폭발 폭탄보다 번호가 크면 갱신
            if dist <= k and ans < a:
                ans = a

print(ans)

✏️개선점

1. 거리를 비교하는 경우 굳이 폭탄을 지정해줄 필요없다.
2. 거리를 벗어나는 경우 break, 같은 폭탄이 아닌 경우 continue를 하면 더 간단하게 작성할 수 있다.

break문 : 프로그램 블록 안에서 실행을 중단하고 다음 블록으로 넘어갈 때 사용
continue문 : 반복문의 반복을 한 번 취소하고 다음 반복을 실행할 때 사용

🟠선분 3개 지우기

📌문제

📌나의 코드

n = int(input())
lines = [tuple(map(int, input().split())) for _ in range(n)]

def check_overlapped(l1, l2, l3):
    count = [0] * 100

    for i in range(n):
        # 선분이 제거할 선분 중의 하나라면 continue
        if i in [l1, l2, l3]:
            continue

        # 남아있는 선분이라면 count 표시
        x1, x2 = lines[i]
        for j in range(x1, x2 + 1):
            count[j] += 1

    # count 배열을 돌며 1보다 클 경우 겹치는 것으로 보고
    # overlap을 True로 변경
    overlap = False
    for i in range(100):
        if count[i] > 1:
            overlap = True
            break
        
    return overlap


ans = 0
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            # 3개의 선분 제거 후 남은 선분들이 겹치지 않으면
            # 경우의 수 증가
            if not check_overlapped(i, j, k):
                ans += 1

print(ans)

✏️개선점

<기본개념 - 3, 물체 세 개를 정하여 완전탐색>을 보고 풀었다.

---

연습문제

---

🟠스승의 은혜 3

📌문제

📌나의 코드

n, b = map(int, input().split())
wishes = [tuple(map(int, input().split())) for _ in range(n)]

ans = 0
for i in range(n):
    # 학생들이 원하는 선물의 가격 리스트
    tmp = [list(wishes[j]) for j in range(n)]

    # 선물 한 개를 반값 할인
    tmp[i][0] /= 2

    # (선물 가격 + 배송비) 리스트
    prices = [(tmp[k][0] + tmp[k][1]) for k in range(n)]
    prices.sort()

    # 선물할 수 있는 학생수, 현재까지 쓴 예산
    student = 0
    cnt = 0

    for x in range(n):
        if cnt + prices[x] > b:
            break
        cnt += prices[x]
        student += 1

    ans = max(ans, student)

print(ans)

🔓풀이

tmp = [wishes[j] for j in range(n)]

1. 선물 가격과 배송비 쌍을 tuple로 선언하고, 위와 같이 tmp 리스트를 만들면 값을 변경할 수 없다.
2. 선물 가격과 배송비 쌍을 list로 선언하고, 위과 같이 tmp 리스트를 만들면 원본 리스트의 값도 변경되므로 모든 가격이 할인된 가격이 된다.
   
   

tmp = [list(wishes[j]) for j in range(n)]

따라서 위와 같이 wishes의 각 원소를 리스트로 입력받아야 결과를 제대로 출력할 수 있다.

✏️개선점

1. <연습문제 - 3, 스승의 은혜 2>를 보고 풀었다.
2. 선물 가격과 배송비 리스트를 따로 만들고, 0으로 초기화한 tmp 리스트에 각각의 합을 더하는 방법이 더 빠르다.