[실버 2] 백준 11053 - 가장 긴 증가하는 부분 수열 (파이썬)
[실버 2] 백준 11053 - 가장 긴 증가하는 부분 수열 (파이썬)
2025.04.17https://www.acmicpc.net/problem/11053풀이이 문제는 조금 복잡하다… 일단 다이나믹 프로그래밍 풀이로 작성하였는데, 일반적인 풀이보다 2차원 DP를 활용한 조금은 특이한 방식이다.일단 문제는 수열 A가 주어졌을때, 증가하는 부분 수열 중 가장 길이가 긴 것의 길이를 구하는 문제이다.D = [[0] * 1001 for _ in range(N)] # N * 1001D[i][j] 는 i번째까지 고려했을때, 마지막 수가 j이하인 증가 부분 수열의 최대 길이이다.for i in range(1001): D[0][i] = 1 if A[0] 첫번째 원소만 쓸 수 있는 상황에서 j 조건을 만족하면 길이는 1로 지정한다.for i in range(1, N): for j in range..
[골드 4] 백준 1976 - 여행 가자 (파이썬)
[골드 4] 백준 1976 - 여행 가자 (파이썬)
2025.04.17https://www.acmicpc.net/problem/1976풀이N개의 도시가 있고, 어떤 도시끼리는 도로로 연결되어 있다.M개의 도시가 주어진 여행 계획에 포함되어 있다.주어진 도시들이 모두 같은 연결 요소에 속해 있다면 여행이 가능하다.연결 정보는 인접 행렬로 주어진다.이 문제는 그래프 연결 요소 판별 문제이다.BFS를 통해 각 도시가 어떤 연결 요소에 속해 있는지 visit 배열에 저장하고여행 계획에 포함된 도시들이 모두 같은 연결 요소에 속해 있는지를 확인한다.하나라도 다르면 NO, 모두 같으면 YES를 출력한다.N = int(input()) # 도시 수M = int(input()) # 여행에 포함된 도시 수adj = [[] for _ in range(N)]for i in range(N..
[브론즈 1] 백준 1526 - 가장 큰 금민수 (파이썬)
[브론즈 1] 백준 1526 - 가장 큰 금민수 (파이썬)
2025.04.17https://www.acmicpc.net/problem/1526풀이금민수란 숫자는 4또는 7로만 이루어진 수이다. 입력으로 주어지는 N이하의 수 중에서 가장 큰 금민수를 출력하는 문제이다.결국, 1~6자리의 모든 금민수를 생성하고, 그중 N이하인 것 중 가장 큰 수를 찾는다.이 문제는 6자리 이하의 숫자만 고려하면 되므로, 완전탐색으로 충분히 해결 할 수 있다.for i in range(1, 7): # 자릿수: 1~6자리 for j in range(i + 1): # 7을 넣을 자리 개수 for combination in combinations(range(i), j): kms = 0 for k in range(i): ..
[실버 3] 백준 1904 - 01타일 (파이썬)
[실버 3] 백준 1904 - 01타일 (파이썬)
2025.04.16https://www.acmicpc.net/problem/1904풀이길이가 N인 이진 문자열 중 1 또는 00만 사용해서 만들 수 있는 경우의 수를 구하는 문제이다.1 또는 00만 사용해서 N자리 수를 만들 수 있는 경우의 수 = 피보나치 수열길이가 N일때 만들 수 있는 경우의 수를 D[n]이라고 할때,D[N - 1] 뒤에 “1”을 붙으면 길이 N이 된다.D[N - 2] 뒤에 “00”을 붙이면 길이 N이 된다.즉 점화식은 다음과 같다.✅ D[N] = D[N - 1] + D[N - 2]초기값을 1, 2로 미리 초기항을 설정한다.최대 N이 1,000.000이므로 충분히 크게 초기화 하고, 중간에 나머지 연산을 해줘야 오버플로우를 방지 할 수 있기에, 매 실행시 mod로 나머지 연산을 해준다.시간 복잡도 분석..
[골드 5] 백준 1038 - 감소하는 수 (파이썬)
[골드 5] 백준 1038 - 감소하는 수 (파이썬)
2025.04.16https://www.acmicpc.net/problem/1038풀이감소하는 수란 각 자릿수가 왼쪽부터 오른쪽으로 감소하는 수이다.예를 들어서, 321, 740, 1 , 20 이런식을 의미한다.0부터 9876543210 까지 총 1023개의 감소하는 수가 존재한 다는것을 알 수 있다.입력 N이 주어졌을때, N번째 감소하는 수를 출력하는 문제이다.만약 존재하지 않으면 -1을 출력해야 한다.for i in range(1, 11): for combination in combinations(list(range(10)), i):combinations(range(10), i)는 0~9중 i개를 뽑는 조합을 구한다예를 들어서 i 가 2라면 (0, 1), (0, 2), … , (8, 9)와 같은 모든 조합이 나온..
[골드 5] 백준 15686 - 치킨 배달 (파이썬)
[골드 5] 백준 15686 - 치킨 배달 (파이썬)
2025.04.15https://www.acmicpc.net/problem/15686풀이도시에는 집(1)과 치킨집(2)가 있고, 나머지는 (0)으로 빈칸이다.최대 M개의 치킨집만 선택해서 영업해야하며, 모든 집은 가장 가까운 치킨집까지의 거리로 만족한다.모든 지들의 치킨 거리의 합이 최소가 되도록 M개의 치킨집을 선택해야한다.N, M = map(int, input().split())C = [list(map(int, input().split())) for _ in range(N)]N, M, C는 도시의 크기, 영업할 치킨집 수, 도시 지도 정보를 나타낸다.house = []chicken = []for i in range(N): for j in range(N): if C[i][j] == 1: ..
[골드 4] 백준 17298 - 오큰수 (파이썬)
[골드 4] 백준 17298 - 오큰수 (파이썬)
2025.04.15https://www.acmicpc.net/problem/17298풀이주어진 수열에서, 각 원소에 대해 오른쪽에 있으면서 자기보다 큰 수 중 가장 왼쪽에 있는 수를 말한다. 없으면 -1을 출력한다.for i in range(N - 1, -1, -1): while len(stack) > 0 and stack[-1] 1: answer[i] = stack[-2]stack에는 값이 저장되고 있고, 그것을 기반으로 stack[-2]를 사용하고 있는데, 이는 오큰수를 정확히 보장하지 않는다. 왜냐하면 stack[-2]는 항상 stack[-1] 보다 작거나 같다는 보장이 없고, 해당 원소 A[i]보다 큰 가장 가까운 오른쪽 값이 아닐 수도 있다.예를 들어 A = [2, 1, 3] 일때 동작을 살..
[실버 5] 백준 7785 - 회사에 있는 사람 (파이썬)
[실버 5] 백준 7785 - 회사에 있는 사람 (파이썬)
2025.04.14https://www.acmicpc.net/problem/7785풀이이 문제는 회사에 출퇴근한 사람을 바탕으로 회사에 남아 있는 사람을 구하는 문제이다.나는 단순히 Dictionary를 생각했지만, Set으로도 풀이가 가능하다고 생각해서 두개의 버전을 작성하였다.먼저 Dict의 경우 people 딕셔너리에 사람이 들어 있지 않고, 상태가 enter인 경우에 dict에 추가하였다.그외에는 딕셔너리에서 삭제하는 방법을 생각했다.for i in range(N) : name, status = input().split() if name not in people and status == "enter" : people[name] = status else : del people..
[실버 1] 백준 1926 - 그림 (파이썬)
[실버 1] 백준 1926 - 그림 (파이썬)
2025.04.14https://www.acmicpc.net/problem/1926풀이도화지에는 0 또는 1로 된 값이 채워진 N * M 크기의 이차원 배열이 있다.1은 그림의 일부, 0은 빈 공간.그림은 상하좌우로 연결된 1들의 집합이며, 그림의 개수와 가장 넓은 그림의 넓이를 출력해야한다.즉, BFS로 1을 시작점으로 탐색하여 그림 하나를 모두 탐색하고, 이미 방문한 좌표는 visit 배열로 체크한다,각 BFS마다 count로 넓이를 측정한다.queue = deque()visit = [[False] * M for _ in range(N)]BFS용 큐를 초기화 하고, visit은 해당 좌표를 이미 방문했는지 여부를 저장하는 2차원 리스트이다.dr = [0, 0, 1, -1]dc = [-1, 1, 0, 0]상, 하, 좌,..
[골드 5] 백준 1484 - 다이어트 (파이썬)
[골드 5] 백준 1484 - 다이어트 (파이썬)
2025.04.13https://www.acmicpc.net/problem/1484풀이현재 몸무게의 제곱에서과거 몸무게의 제곱을 뺀 값이 G일때 가능한 현재 몸무게를 오름차순으로 출력한다.결국 b^2 - a^2를 인수분해하면 (b-a)(b + a) = G 이다.현재 틀린 코드는 다음과 같은 알고리즘을 사용한다.# 백준 1484 - 다이어트# 분류 : 수학G = int(input())answer = []for i in range(1, G + 1) : if G % i != 0 : continue j = G / i # b - a = i # b + a = j if j G 5 i ≠ 0 조건으로 G의 약수를 구한다.J = G i 를 통해 실수형 나눗셈을 진행한다.자연수 b가 a보다 큰..
[실버 2] 백준 1699 - 제곱수의 합 (파이썬)
[실버 2] 백준 1699 - 제곱수의 합 (파이썬)
2025.04.13https://www.acmicpc.net/problem/1699풀이자연수 N이 주어졌을 때, N을 제곱수들의 합으로 표현하는 데에 필요한 최소 항의 수를 구하는 문제이다.예를 들어서 4 = 2 ^ 2 → 1개, 7 = 2 ^ 2 + 1 ^ 2 + 1 ^ 2 + 1 ^ 2 → 최소 4개D[i]를 i의 제곱수의 합으로 나타낼 수 있는 최소 항의 수라고 생각하고 문제를 푼다.점화식은 다음과 같다.D[i] = min(D[i], 1 + D[i - j ^ 2])if (i ** 0.5).is_integer(): D[i] = 1 continue자기 자신 하나의 제곱수로 표현 가능한 경우는 바로 1로 설정하고 넘어간다.D[i] = 1e9 # 초기값은 매우 큰 수j = 1while j * j i보다 작은 모..
[브론즈 2] 백준 1100 - 하얀 칸 (파이썬)
[브론즈 2] 백준 1100 - 하얀 칸 (파이썬)
2025.04.12https://www.acmicpc.net/problem/1100풀이8 * 8 체스판이 주어지고, 각 칸에는 말이 있거나 비어 있다. 체스판에서 하얀 칸에 말이 놓여 있는 칸의 개수를 구하는 문제이다.체스판의 왼쪽 위는 하안 캰이다.하얀 칸은 (i + j) % 2 == 0 일때 발생한다.B = [input() for _ in range(8)]체스판 입력은 쉽게 입력 받을 수 있다.answer = 0for i in range(8) : for j in range(8) : if (i + j) % 2 == 0 and B[i][j] == 'F' : answer += 1체스판을 (i, j)로 순회하면서하얀칸인지 확인 : (i + j) % 2 == 0해당 칸에 말이 있는지 확인 ..
[골드 4] 백준 9935 - 문자열 폭발 (파이썬)
[골드 4] 백준 9935 - 문자열 폭발 (파이썬)
2025.04.11https://www.acmicpc.net/problem/9935풀이핵심 아이디어는 스택을 활용해 문자열을 한 글자씩 처리하면서 폭발 문자열(T)이 나타날 때마다 제거하는 것이다.문자열 S에서 폭발 문자열 T가 등장하면, 그 부분을 제거한다.제거 후 남은 문자열에서 다시 폭발 문자열이 등장할 수 있다면 또 제거한다.이 과정을 반복해 최종 문자열을 구한다.결과가 빈 문자열이면 "FRULA"를 출력한다.stack = []for i in range(len(S)): stack.append(S[i]) # 현재 문자를 스택에 추가한 글자씩 stack에 넣으면서 문자열을 구성해 나간다.if len(stack) >= len(T): same = True for j in range(len(T)): ..
[브론즈 2] 백준 15829 - Hashing (파이썬)
[브론즈 2] 백준 15829 - Hashing (파이썬)
2025.04.10https://www.acmicpc.net/problem/15829풀이문자열에 대해 특정한 방식으로 해시 값을 계산하는 문제이다.각 문자의 알파벳 순서에 가중치를 곱해서 더하는 방식이 사용된다.mod = 1234567891 # 모듈러 값po = [0] * L # 거듭제곱 저장 리스트po[0] = 1 # r^0 = 1# r^1, r^2, ..., r^(L-1) 을 미리 계산for i in range(1, L): po[i] = po[i - 1] * 31 % mod문자열 길이가 최대 50이라 효울적으로 r ^ i % mod 값을 미리 계산해둔다.H = 0for i in range(L): H += (ord(S[i]) - ord('a') + 1)..
[실버 1] 백준 1149 - RGB거리 (파이썬)
[실버 1] 백준 1149 - RGB거리 (파이썬)
2025.04.09https://www.acmicpc.net/problem/1149풀이집이 N개 있고, 각 집은 빨강(R), 초록(G), 파랑(B) 중 하나로 색칠해야 한다.조건: 인접한 집은 같은 색을 칠할 수 없다.즉, 각 집을 칠하는 비용이 주어졌을 때, 모든 집을 칠하는 최소 비용을 구하는 문제이다.R[0] = C[0][0] # 첫 번째 집을 빨강으로 칠했을 때 비용G[0] = C[0][1] # 첫 번째 집을 초록으로 칠했을 때 비용B[0] = C[0][2] # 첫 번째 집을 파랑으로 칠했을 때 비용두번째 집부터는 이전 집과 색이 달라야 하므로, 각 색에 대해 아래와 같이 계산한다.R[i] = C[i][0] + min(G[i - 1], B[i - 1])G[i] = C[i][1] + min(R[i - 1], B..