풀이 1 : 리스트와 in 문법 사용class Solution: def hasDuplicate(self, nums: List[int]) -> bool: count = [] for i in nums: if i not in count: count.append(i) else: return True return FalseNeetCode에서 통과한 코드다.하지만 LeetCode에서는 nums 배열이 아주 큰 테스트케이스에서 시간 초과로 통과하지 못했다. 풀이 2 : set과 in 문법 사용class Solution: def containsDuplicate(se..
⚙️ Problem Solving
이진 트리를 입력 받아 preorder traversal, inorder traversal, postorder traversal한 결과를 출력하는 프로그램 풀이 1: tree를 딕셔너리로 표현, 재귀 이용import sysinput = sys.stdin.readlinen = int(input().strip())tree = {}for _ in range(n): parent, left, right = input().split() tree[parent] = (left, right)root = 'A'def preorder(tree, node): if node == '.': return "" return node + preorder(tree, tree[node][0]) + pre..
각 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 인접한 집들이 같은 색이 되지 않도록 하면서 모든 집을 칠하는 최소 비용을 구하는 문제-> DP 테이블을 2차원 리스트로 정의하여 풀 수 있다. 풀이동적 프로그래밍 테이블 정의:dp[i][j]: i번째 집을 j색으로 칠하는 최소 비용 (j = 0: 빨강, 1: 초록, 2: 파랑)점화식 설정:dp[i][0] = cost[i][0] + min(dp[i-1][1], dp[i-1][2]) (i번째 집을 빨강으로 칠하는 경우)dp[i][1] = cost[i][1] + min(dp[i-1][0], dp[i-1][2]) (i번째 집을 초록으로 칠하는 경우)dp[i][2] = cost[i][2] + min(dp[i-1][0], dp[i-1][1]) (i번째 ..
문제 요약MBTI 성격 유형을 가진 학생들 사이의 심리적인 거리를 계산하는 문제이다. 주어진 학생들 중 가장 가까운 세 학생의 심리적인 거리를 구하는 것이 목표이다.입력첫 줄에는 테스트 케이스의 수를 나타내는 정수 ( T )가 주어진다.각 테스트 케이스의 첫 줄에는 학생의 수를 나타내는 정수 ( N )이 주어지며, 두 번째 줄에는 각 학생의 MBTI 성격 유형을 나타내는 문자열들이 공백을 두고 주어진다.출력각 테스트 케이스에 대한 답을 정수 형태로 한 줄에 하나씩 출력한다. 풀이 설명이 문제는 세 학생의 MBTI 유형 간의 심리적 거리를 구하는 문제이다. MBTI는 4개의 척도로 구성되어 있으므로 총 16개의 유형이 있다. 세 학생 간의 심리적 거리는 세 유형 간의 심리적 거리의 합으로 정의된다.문제에서..
문제 요약도연이는 캠퍼스에서 만날 수 있는 친구의 수를 알고 싶어한다. 캠퍼스는 ( N \times M ) 크기이며, 도연이는 빈 공간('O')과 사람('P')이 있는 곳으로 이동할 수 있다. 벽('X')은 이동할 수 없다. 도연이가 시작하는 위치는 'I'로 주어진다. 도연이가 만날 수 있는 사람의 수를 출력하는 프로그램을 작성하는 문제이다.입력첫 번째 줄에 캠퍼스의 크기를 나타내는 두 정수 ( N )과 ( M )이 주어진다.다음 ( N )개의 줄에 캠퍼스의 정보가 주어진다. 'O'는 빈 공간, 'X'는 벽, 'I'는 도연이의 시작 위치, 'P'는 사람이다.출력도연이가 만날 수 있는 사람의 수를 출력한다. 만약 아무도 만나지 못한 경우 "TT"를 출력한다. 풀이 설명이 문제는 BFS(너비 우선 탐색)를..
문제 요약지도에서 각 지점에 대해 목표 지점(값이 2인 지점)까지의 거리를 구하는 문제이다. 지도는 가로와 세로로만 움직일 수 있으며, 0은 갈 수 없는 땅, 1은 갈 수 있는 땅, 2는 목표 지점을 의미한다. 풀이 설명이 문제는 너비 우선 탐색(BFS)를 사용하여 각 지점에서 목표 지점까지의 최단 거리를 구하는 문제이다.BFS는 최단 거리를 구하는 데 적합한 알고리즘이다. from collections import dequeimport sysinput = sys.stdin.readlinen, m = map(int, input().split())graph = [list(map(int, input().split())) for _ in range(n)]def bfs(graph, n, m): distan..
문제 요약N+1개의 I와 N개의 O로 이루어진 문자열을 PN이라고 한다. 예를 들어, P1은 "IOI", P2는 "IOIOI", P3는 "IOIOIOI"이다. 주어진 문자열 S 안에 PN이 몇 번 포함되어 있는지 찾는 프로그램을 작성하는 문제이다. 풀이 설명문제의 본질은 문자열 S 안에 PN 패턴이 몇 번 포함되어 있는지를 찾는 것이다.이를 위해 문자열을 순회하면서 IOI 패턴을 찾고, N개의 IOI 패턴이 연속적으로 등장할 때마다 카운트를 증가시키는 방식으로 해결할 수 있다. N = int(input())M = int(input())S = input()def count_pn(N, S): pattern_count = 0 i = 0 count = 0 while i 코드 설명변수 초기..
문제 설명자연수 ( n )이 주어질 때, ( n )을 최소 개수의 제곱수 합으로 표현하는 방법을 찾는 프로그램을 작성하는 문제이다. 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 예를 들어, 26은 ( 5^2 + 1^2 )로 표현할 수 있고, ( 4^2 + 3^2 + 1^2 )로도 표현할 수 있다. 이 문제에서는 ( n )을 최소 개수의 제곱수 합으로 표현할 때 그 최소 개수를 구해야 한다. 풀이 설명이 문제는 동적 계획법(Dynamic Programming)을 사용하여 해결할 수 있다. def min_squares(n): # dp[i]는 i를 최소 개수의 제곱수 합으로 표현하는 방법의 개수를 저장 dp = [float('inf')] *..
문제 요약이중 우선순위 큐는 정수를 저장하고, 최댓값 또는 최솟값을 삭제하는 연산을 지원한다.주어진 연산 명령을 수행한 후 큐에 남아 있는 값 중 최댓값과 최솟값을 출력한다.만약 큐가 비어 있다면 'EMPTY'를 출력한다. 풀이 설명문제를 해결하기 위해 두 개의 우선순위 큐 (최소 힙과 최대 힙)를 사용한다.또한 각 숫자의 등장 횟수를 저장하는 딕셔너리를 사용하여, 삭제 연산 시 실제로 큐에서 존재하는 숫자를 관리한다. 풀이 코드from collections import dequeimport heapqimport sysinput = sys.stdin.readlinedef is_empty(nums): for item in nums: if item[1] > 0: retu..
문제 요약보드 게임에서 플레이어는 주사위를 굴려 1번 칸에서 100번 칸까지 이동해야 한다.사다리는 도착하면 더 높은 번호로 이동하고, 뱀은 더 낮은 번호로 이동하게 한다.100번 칸에 도착하기 위해 주사위를 최소 몇 번 굴려야 하는지 구한다. 풀이from collections import dequeimport sysinput = sys.stdin.readlinedef snakes_and_ladders(N, M, ladders, snakes): board = list(range(101)) # 보드의 각 칸 초기화 for start, end in ladders.items(): board[start] = end # 사다리 설정 for start, end in snakes.it..
