나만의 깍두기판

1. 문제https://www.acmicpc.net/problem/11758 2. 풀이세 점 P1, P2, P3가 주어졌을 때, 이들을 순서대로 이은 선분이 어떤 방향을 이루는지 판단하는 문제다.외적(벡터의 곱)으로 접근했다.두 벡터의 외적은 걔네들이 이루는 평행사변형의 넓이를 나타내는데, 외적의 부호가 방향을 알려준다는 점을 활용했다.공식도출: 외적 = (x2-x1) × (y3-y1) - (y2-y1) × (x3-x1)판단기준외적 > 0: 반시계방향 -> 1외적 -1외적 = 0: 일직선 -> 0P3가 P1에서 P2로 가는 벡터의 왼쪽에 있으면 반시계, 오른쪽에 있으면 시계방향?def ccw(p1, p2, p3): x1, y1 = p1 x2, y2 = p2 x3, y3 = p3 ..

1. 문제https://www.acmicpc.net/problem/2251 2. 풀이물통 A가 비어 있을 때, 물통 C에 들어갈 수 있는 물의 양을 모두 찾아보는 게 목표였음. 각각의 상태는 [A에 든 물, B에 든 물, C에 든 물] 리스트로 표현했음. 매번 새로운 상태를 만들어서 다음 재귀 호출에 넘겨줬음가능한 6가지 물 붓기 경우를 모두 재귀적으로 따라가면서, 중복된 상태는 다시 탐색하지 않도록 방문 여부를 체크했음방문 여부는 visited[a][b]라는 2차원 리스트로 관리했음. C의 값은 항상 "전체 물 - a - b"로 유추할 수 있음A가 비어 있는 상태에서 C에 들어 있는 물의 양을 answers에 저장했음. list에 넣고, 출력 전에 sort()로 정렬했음 아래는 작성한 최종코드impo..

1. 문제https://www.acmicpc.net/problem/2533 2. 배경지식전형적인 DP 문제이다(진짜 개극혐) Dynamic Programming정의: 큰 문제를 작은 문제로 쪼개어, 큰 문제를 풀 때 활용 → 일명 "기억하며 풀기"조건Overlapping Subproblems(겹치는 부분 문제): 동일한 작은 문제들이 반복하며 나타남(재사용이 가능한 부분이 있어야 함)Optimal Substructure(최적 부분 구조): 부분 문제의 최적 결과값으로 전체 문제의 최적 결과값을 낼 수 있는 경우구현 방식Bottom-up 방식: 반복문 사용Top-down 방식: 재귀 사용 아래는 실패 코드class Node: def __init__(self, value): self.val..

1. 문제https://www.acmicpc.net/problem/6603 2. 풀이전체 코드from itertools import combinationswhile True: num = input() if len(num)==1 and int(num) == 0: break else: num = num.split() k = num[0] num.pop(0) result = list(combinations(num, 6)) for i in range(len(result)): for j in range(len(result[i])): print(result[i][j], end=' ') print() pri..

1. 문제https://www.acmicpc.net/problem/4779   2. 풀이def change_cantor(list): cube_root = len(list)**(1/3) breakpoint = int(len(list) / 3) if(cube_root == 1): print(list[0], end='') return else: list1, list2, list3 = list[0:breakpoint], list[breakpoint:breakpoint*2], list[breakpoint*2:] list2 = [' ' for _ in range(len(list2))] change_cantor(list1) ..

1. 문제https://www.acmicpc.net/problem/10870   2. 풀이def fibonacci(num): if(num

1. 문제https://www.acmicpc.net/problem/2108   2. 풀이import sysfrom collections import Counterinput = sys.stdin.readlinen = int(input())digits = []total_sum = 0for i in range(n): x = int(input()) digits.append(x) total_sum += x# 산술평균print(round(total_sum / n))# 중앙값digits.sort()print(digits[n//2])# 두 번째로 작은 최빈값num_counts = Counter(digits)freq_list = sorted(num_counts.items(), key=lambda x: (..

1. 문제https://www.acmicpc.net/problem/26069  2. 풀이import sysinput = sys.stdin.readlineN = int(input())chong = ["ChongChong"]for _ in range(0, N): x, y = map(str, input().strip().split()) if x in chong: chong.append(y) elif y in chong: chong.append(x) else: continueresult = list(set(chong))print(len(result))