[브론즈 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..
[골드 2] 백준 1202 - 보석 도둑 (파이썬)
[골드 2] 백준 1202 - 보석 도둑 (파이썬)
2025.04.08https://www.acmicpc.net/problem/1202풀이정렬 + 그리디 + 우선순위 큐 알고리즘으로 해결 할 수 있다.문제의 핵심은 무게 제한이 있는 가방에 최대 가치를 가지는 보석을 훔치는 방법이다.J = [tuple(map(int, input().split())) for _ in range(N)]B = [int(input()) for _ in range(K)]J.sort()B.sort()보석 리스트 J는 무게 기준 오름차순 정렬가방 리스트 B는 무게 제한 기준 오름차순 정렬가방을 무게 제한이 작은 순서대로 처리하면서, 해당 가방에 담을 수 있는 보석 중 가장 비싼 보석을 선택한다.pq = PriorityQueue()answer = 0pos = 0최대 힙을 구현하기 위해 - 가격을 우선순위..
[실버 1] 백준 14225 - 부분수열의 합 (파이썬)
[실버 1] 백준 14225 - 부분수열의 합 (파이썬)
2025.04.07https://www.acmicpc.net/problem/14225 풀이itertools.combinations를 이용해서 길이 1부터 N까지 모든 조합을 구한다.각 조합의 합을 리스트 sums에 추가한다.sums = []for i in range(1, N + 1): for combination in combinations(S, i): sums.append(sum(combination))중복된 합들을 제거한 후, 오름차순으로 정렬한다.sums = list(set(sums))sums.sort()그 후 만들 수 없는 가장 작은 자연수를 찾기 위해서answer = len(sums) + 1for i in range(len(sums)): if sums[i] != i + 1: a..
[실버 2] 백준 1535 - 안녕 (파이썬)
[실버 2] 백준 1535 - 안녕 (파이썬)
2025.04.06https://www.acmicpc.net/problem/1535풀이친구들에게 인사를 할 수 있는데, 각 친구에게 인사를 하면 체력이 감소하고, 기쁨은 증가한다.체력이 100 이하가 되면 죽기 때문에, 체력을 1 이상 유지하면서 얻을 수 있는 최대 기쁨의 합을 구하는 문제이다.모든 친구들에게 인사할 수 있는 경우의 수는 2^N이다.브루트포스로 가능한 모든 친구 조합을 만들고, 그 조합이 체력 조건을 만족하는지 확인 후 기쁨은 계산하면 풀 수 있다.max_jsum = 0for i in range(0, N + 1) : for combination in combinations(range(N), i) : lsum = 0 jsum = 0 for j in combinati..
[브론즈 2] 백준 3040 - 백설 공주와 일곱 난쟁이 (파이썬)
[브론즈 2] 백준 3040 - 백설 공주와 일곱 난쟁이 (파이썬)
2025.04.05https://www.acmicpc.net/problem/3040풀이해당 문제는 브루트포스 알고리즘을 사용하면 쉽게 해결 할 수 있다.A = [int(input()) for _ in range(9)]먼저 입력을 받기 위해서 리스트 컴프리핸션을 이용해서 다음과 같이 입력을 받는다.combinations 모듈을 사용해서 A에서 7개를 뽑아 합이 100이면 출력하고 종료하면 되는 간단한 문제이다.코드# 백준 3040 - 백설 공주와 일좁 난쟁이# 분류 : 브루트포스from itertools import combinationsA = [int(input()) for _ in range(9)]for combination in combinations(A, 7) : if sum(combination) == 100..
[브론즈 4] 백준 11945 - 뜨거운 붕어빵 (파이썬)
[브론즈 4] 백준 11945 - 뜨거운 붕어빵 (파이썬)
2025.04.04https://www.acmicpc.net/problem/11945풀이이 문제는 간단한 문자열 뒤집기 문제로, N행 M열로 이루어진 붕어빵의 모양이 주어졌을 때, 이를 좌우로 뒤집은 결과를 출력하는 문제이다.먼저 N, M을 입력받고, 이후 N줄에 걸쳐 붕어빵의 모양을 문자열로 입력받아 리스트에 저장한다.그 다음 각 줄의 문자열을 역순으로 뒤집기 위해 파이썬의 슬라이싱 기능인 [::-1]을 사용한다.뒤집은 결과를 한 줄씩 출력한다.시간 복잡도 분석문자열을 한 줄씩 입력받고, 각각을 한 번 뒤집기 때문에 전체 시간 복잡도는 O(NM)N과 M의 범위가 작으므로 (예: N ≤ 10, M ≤ 10), 속도 걱정 없이 단순 구현으로 풀 수 있는 문제이다.코드# 백준 11945 - 뜨거운 붕어빵# 분류 : 구현N, ..
[골드 5] 백준 - 노드사이의 거리 (파이썬)
[골드 5] 백준 - 노드사이의 거리 (파이썬)
2025.04.03https://www.acmicpc.net/problem/1240풀이트리의 노드 N, 거리 구할 쌍의 개수 M을 초기에 입력받는디ㅏ.N - 1개의 간선정보와 M개의 노드 쌍이 주어진다.트리는 사이클이 없고, 두 노드사이의 경로가 항상 유일하게 존재한다.따라서 s번 노드에서 DFS를 돌리면 모든 노드까지의 거리를 구할 수 있다.t번 노드까지의 누적 거리를 출력하면 s - t 거리이다.for _ in range(N - 1): u, v, w = map(int, input().split()) u -= 1 v -= 1 adj[u].append((v, w)) adj[v].append((u, w))트리의 간선을 입력 받고, 편의를 위해서 1씩 빼준다.또한 양방향으로 연결하기 u, v를 각각..
[실버 4] 백준 1269 - 대칭 차집합 (파이썬)
[실버 4] 백준 1269 - 대칭 차집합 (파이썬)
2025.04.02https://www.acmicpc.net/problem/1269풀이A를 집합(set)으로 변환집합을 사용하면 in 연산이 평균 시간 복잡도 O(1)로 빠르게 작동B를 순회하며 A에 포함된 원소 개수를 센다.대칭 차집합 개수 계산print(N + M - 2 * count)시간 복잡도 분석집합 변환 (set) : O(N)B 순회 및 포함 여부 확인 : O(M)최종 연산 : O(1)최종 시간 복잡도 : O(N + M)코드# 백준 1269 - 대칭 차집합# 분류 : 집합N, M = map(int, input().split())A = list(map(int, input().split()))B = list(map(int, input().split()))A = set(A)count = 0for b in B : ..
프로그래머스 - [Level 2] 전력망을 둘로 나누기 (파이썬)
프로그래머스 - [Level 2] 전력망을 둘로 나누기 (파이썬)
2025.04.02https://school.programmers.co.kr/learn/courses/30/lessons/86971?language=python3 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이BFS + 완전탐색 방식의 풀이로 작성하였다. 각 연결을 하나씩 끊어보면서 두 전력망의 노드 수 차이의 최소값을 구하는 방식이다.문제에서 요구하는 사항은하나의 연결을 끊어 전력망을 두개로 나누었을때,두 전력망 송전탑 개수 찾이의 최소값을 반환하는 문제이다.BFS 코드는 너무 단순하기 때문에 간단하게 설명하면, 하나의 연결 그래프에서 시작 노드 S로부터 BFS를 수행하여 연결된 노드의 개수를 세는 함수로 칭한다.전..
프로그래머스 - [Level 2] 숫자 카드 나누기 (파이썬)
프로그래머스 - [Level 2] 숫자 카드 나누기 (파이썬)
2025.04.02https://school.programmers.co.kr/learn/courses/30/lessons/135807 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이두 배열이 주어졌을 떄, 한 배열의 모든 수를 나누면서 다른 배열의 어떤 수로도 나누어지지 않는 수중에서 최대값을 찾는 문제이다.내가 접근한 방식은 다음과 같다.두배열 arrayA, arrayB가 주어지고,x는 arrayA의 모든 원소를 나눌수 있어야한다.x는 arrayB의 어떤 원소도 나눌 수 없어야한다.또는 반대로 x는 arrayB의 모든 원소를 나눌 수 있어야한다.x는 arrayA의 어떤 원소도 나눌 수 없어야한다.from math i..
백준 2495 - 연속구간 (파이썬)
백준 2495 - 연속구간 (파이썬)
2025.04.02https://www.acmicpc.net/problem/2495풀이이 문제는 0과 1로 이루어진 문자열이 세 줄 주어졌을 때, 각 줄에서 같은 숫자가 연속으로 등장하는 가장 긴 길이를 구하는 문제이다.예를 들어, “0001000”이라는 문자열에서는 0이 최대 3번 연속으로 등장하므로 정답은 3이 된다.문자열을 앞에서부터 한 글자씩 확인하면서, 이전 문자와 같은지 비교한다.만약 현재 문자가 이전 문자와 같다면, 현재 연속 길이(count)를 1 증가시킨다.반대로 다르다면, 연속이 끊긴 것이므로 count를 1로 초기화한다.매 반복마다 지금까지의 최대 연속 길이(max_count)를 갱신다.문자열을 모두 확인한 후, 해당 줄의 최대 연속 길이를 출력한다.시간 복잡도 분석각 줄에 대해 한번 씩 문자열을 순회..
백준 2456 - 나는 학급회장이다 (파이썬)
백준 2456 - 나는 학급회장이다 (파이썬)
2025.04.01https://www.acmicpc.net/problem/2456풀이투표는 여러 명의 학생들이 진행하며, 각 사람은 1번, 2번, 3번 후보에게 1~3점 중 하나씩 점수를 준다.가장 총점이 높은 사람이 회장이 됨.동점일 경우에는 다음 우선순위로 결정.3점을 더 많이 받은 후보2점을 더 많이 받은 후보그래도 같으면 무효처리 (0)코드# 백준 2456 - 나는 학급회장이다# 분류 : 구현N = int(input())score = [0] * 3count_3 = [0] * 3count_2 = [0] * 3for _ in range(N) : s = list(map(int, input().split())) for i in range(3) : score[i] += s[i] if s..