Programming
백준 17086 - 아기 상어 2 (파이썬)
백준 17086 - 아기 상어 2 (파이썬)
2025.03.04https://www.acmicpc.net/problem/17086풀이입력 처리N, M = map(int, input().split())A = [[] for _ in range(N)]for i in range(N): A[i] = list(map(int, input().split()))N, M을 통해서 맵의 크기를 입력 받고,A배열에는 N * M 크기의 2차원 리스트를 생성하여, 각 좌표에 대한 정보를 저장하기 위해 사용BFS 탐색을 위한 초기 설정visit = [[False] * M for _ in range(N)]dist = [[-1] * M for _ in range(N)]queue = deque()visit : 방문 여부를 저장하는 2차원 리스트 (True : 방문함, False : 방문 안 ..
백준 2293 - 동전 1 (파이썬)
백준 2293 - 동전 1 (파이썬)
2025.03.04https://www.acmicpc.net/problem/2293 풀이dp[i][j] → i번까지의 동전을 사용하여 j원을 만드는 경우의 수점화식동전 i를 사용하지 않는 경우dp[i][j] = dp[i - 1][j]동전 i를 사용하는 경우dp[i][j] += dp[i][j - V[i]]현재 동전을 사용하면 j - V[i]를 만드는 방법에서 해당 동전을 추가한 방법이 가능초기에 코드는 다음과 같다.# 백준 2293 - 동전 1# 분류 : 다이나믹 프로그래밍N, K = map(int, input().split())V = [0] * Nfor i in range(N) : V[i] = int(input())# (i, j) : i번 까지의 동전을 사용해서 j원을 만드는 경우의 수dp = [[0] * (K + ..
백준 1062 - 가르침 (파이썬)
백준 1062 - 가르침 (파이썬)
2025.03.03https://www.acmicpc.net/problem/1062풀이1. 문제 분석주어진 N개의 단어는 항상 “anta” 로 시작하고, “tica” 로 끝난다.따라서 ‘a’, ‘c’, ‘i’, ‘n’, ‘t’ 다섯 개의 글자는 반드시 알아야 한다.만약 K 답은 0이 된다.K-5개의 추가 글자를 선택하여, 최대 몇 개의 단어를 읽을 수 있는지 탐색해야 한다.해결 방법기본 글자 (‘a’, ‘c’, ‘i’, ‘n’, ‘t’)를 제외한 21개의 글자 중 K-5개 선택itertools.combinations을 사용하여 K-5개의 글자 조합을 만듬각 조합에 대해 읽을 수 있는 단어 개수 계산선택한 글자로 단어를 읽을 수 있는지 확인하고, 최대 개수를 갱신백트래킹을 사용하여 탐색 최적화선택한 조합에 대해 teach ..
백준 6550 - 부분 문자열 (파이썬)
백준 6550 - 부분 문자열 (파이썬)
2025.03.02https://www.acmicpc.net/problem/6550풀이문자열 S가 문자열 T의 부분 문자열인지 판별하는 문제이다.즉, S에 포함된 문자들이 T에서 순서를 유지하면서 존재하는지를 확인 해야 한다.pos = 0good = Truepos는 T에서 S의 문자를 찾을 위치를 나타내는 포인터이다.good은 S가 T의 부분 문자열인지 여부를 저장하는 불 변수이다.for i in range(len(S)) : while pos S의 문자를 차례대로 순회하면서, T에서 해당 문자를 찾을 때까지 pos를 증가시킨다.T[pos] == S[i]가 성립할 때까지 pos를 이동한다.if pos T에서 S[i] 문자를 찾으면, 다음 문자를 찾기 위해 pos를 증가시킨다.else : good = False ..
백준 20442 - ㅋㅋ루ㅋㅋ
백준 20442 - ㅋㅋ루ㅋㅋ
2025.03.01https://www.acmicpc.net/problem/20442풀이문자열 S가 주어졌을 때, ㅋㅋ루ㅋㅋ의 형태를 만들 수 있는 가장 긴 부분 문자열의 길이를 구하는 문제이다.“ㅋㅋ루ㅋㅋ” 형태는 양 끝에는 K가 존재해야하며, 그 사이에 있는 R의 개수가 최대가 되어야 한다.접근 방식필자는 문제 접근에서 투포인터 기법을 활용해서 해결했다.초기 데이터 수집K와 R의 개수를 미리 세어둔다.num_k, num_r 을 통해 K와 R의 개수를 따로 저장한다.투 포인터 설정start = -1 (즉, 왼쪽에서 K를 찾을 위치)end = len(S) (즉, 오른쪽에서 K를 찾을 위치)max_length = 0 (만들 수 있는 최대 부분 문자열의 길이)투 포인터 탐색K가 양 끝에 i개씩 있는 경우를 고려해여 2 * i..
백준 14675 - 단절점과 단절선 (파이썬)
백준 14675 - 단절점과 단절선 (파이썬)
2025.02.28https://www.acmicpc.net/problem/14675풀이그래프의 단절점과 단절선을 판별하는 문제이다.단절점어떤 정점을 제거했을 때 그래프가 여러 개의 컴포넌트로 나뉘는 정점단절선어떤 간선을 제거했을 때 그래프가 여러 개의 컴포넌트로 나뉘는 간선트리의 간선을 입력받아 입접 리스트를 구성한다.N = int(input())adj = [[] for _ in range(N + 1)]for _ in range(N - 1) : u, v = map(int, input().split()) adj[u - 1].append(v - 1) adj[v - 1].append(u - 1)단절점을 판별한다.for _ in range(Q) : t, k = map(int, input().split())..
백준 1316 - 그룹 단어 체커 (파이썬)
백준 1316 - 그룹 단어 체커 (파이썬)
2025.02.28https://www.acmicpc.net/problem/1316풀이문제 이해주어진 단어가 그룹 단어인지 판별하는 문제그룹 단어란, 단어에서 연속적으로 나타나는 문자만 허용되는 단어예시) aabb → O예시) ababa → X (b가 다시 등장)알고리즘 동작count 변수를 선언하여 그룹 단어 개수를 저장arr의 각 단어에 대해 아래 과정 수행check 리스트를 통해서 알파벳 26개의 방문 여부를 저장한다.prev 변수를 사용해서 이전 문자를 저장하여 비교각 문자 w를 순회하며, prev가 w가 다르면 이미 나온 문자면 그룹 단어가 아님아니라면, check 배열에 방문을 표시하고, prev 값을 현재 문자로 업데이트 진행한다.중간에 break 없이 끝까지 검사되면 그룹 단어이다.시간 복잡도 분석각 단어를..
백준 20922 - 겹치는 건 싫어 (파이썬)
백준 20922 - 겹치는 건 싫어 (파이썬)
2025.02.27https://www.acmicpc.net/problem/20922풀이진짜 단순히 배열에서 K개 이상의 dic을 만들어서 종료하는 구문으로 풀어볼까 했는데, 어림도 없지 당연히 틀렸다.import sysinput = sys.stdin.readlineN, K = map(int, input().split())arr = list(map(int, input().split()))dic = {}answer = 0for i in arr : if i in dic : dic[i] += 1 else : dic[i] = 1 if dic[i] > K : break else : answer += 1문제를 이해하면 다음과 같다. 주어진 정수 배열 A에..
백준 14502 - 연구소 (파이썬)
백준 14502 - 연구소 (파이썬)
2025.02.26https://www.acmicpc.net/problem/14502풀이이 문제는 BFS와 완전 탐색을 조합하여 해결하는 문제이다.문제에서는 연구소에서 벽을 3개 세우는 모든 경우의 수를 고려하고, 이후 바이러스가 퍼지는 과정을 BFS로 시뮬레이션하여 안전 영역의 최대 크기를 구하는 방식으로 해결한다.사용한 해결 전략은 다음과 같다.연구소에서 빈칸 (0)의 좌표를 찾는다.빈칸 중 3곳을 선택하여 벽을 세운다. (여기서 필자는 combinations()를 통해 조합을 구함)BFS를 이용해서 바이러스를 퍼뜨린다.바이러스가 퍼진 후 남은 안전 영역(0)을 계산한다.벽을 세우기 전 상태로 되돌린다. (백트래킹)가장 큰 안전 영역 값을 저장하여 출력한다.cells = [(i, j) for i in range(N) ..
백준 6064 - 카잉 달력 (파이썬)
백준 6064 - 카잉 달력 (파이썬)
2025.02.25풀이이 문제는 브루트포스 방법을 이용해 특정 해가 몇 번쨰 해인지 구하는 문제이다.단순히 모든 연도를 하나씩 증가시키며 탐색하면 시간 복잡도가 O(M * N)으로 너무 커지기 때문에 시간 초과가 일어 날 수 있다.found = Falsefirst = yfound = False: x:y에 해당하는 해를 찾았는지 여부를 저장하는 변수first = y: y를 기준으로 탐색을 시작for i in range(M): if first == x: print(y + i * N) found = True breakfirst 값을 N씩 증가시키면서 x와 같은 값을 찾기만약 first == x가 되는 순간, 해당 연도가 답이므로 출력 후 종료first += Nif first > N: ..
백준 9342 - 염색체 (파이썬)
백준 9342 - 염색체 (파이썬)
2025.02.25분류 : 문자열 + 정규 표현식https://www.acmicpc.net/problem/9342풀이먼저 T를 입력받아 테스트 케이스 개수를 정함T만큼 반복하면서 문자열 S를 입력받음기본적으로 문자열 S의 길이가 3미만이면 패턴을 만족할수 없으므로 “Good”을 출력하고 다음 반복으로 넘어감첫문자가 “A”가 아니라면 “A”, “B”, “C”, “D”, “E”, “F”에 속하는지 확인만약 속하지 않는다면 “Good”을 출력하고 다음 반복으로 넘어감만약 속한다면 이를 제거하고 진행한다.마지막 문자를 먼저 확인해 “C”가 아니라면 “A”, “B”, “C”, “D”, “E”, “F”에 속하는지 확인속하지 않는다면 “Good”을 출력하고 다음 반복으로 넘어감만약 속한다면 이를 제거하고 진행한다.여기서 T라는 새로운..
백준 2015 - 수들의 합 4 (파이썬)
백준 2015 - 수들의 합 4 (파이썬)
2025.02.24분류 : 누적합링크 : https://www.acmicpc.net/problem/2015풀이부분합을 활용하여 특정 구간 합이 K가 되는 경우의 수를 찾는 문제이다.단순한 방법으로는 O(N^2) 시간 복잡도로 모든 구간을 확인 할 수 있지만, 주어진 N의 최대값이 200,000 이므로, 이는 비효율적인 방법이다.따라서, 누적합과 해시맵을 활용하여 O(N)으로 해결해야한다.psum = [0] * Npsum[0] = A[0]for i in range(1, N) : psum[i] = psum[i - 1] + A[i]psum[i] 는 A[0] 부터 A[i] 까지의 합을 저장하는 누적합 배열이다.psum[i] = psum[i - 1] + A[i]를 이용하여 이전 누적합에 현재 값을 다하는 방식으로 누적합을 구..
백준 20365 - 블로그2 (파이썬)
백준 20365 - 블로그2 (파이썬)
2025.02.24https://www.acmicpc.net/problem/20365분류 : 그리디https://www.acmicpc.net/problem/20365풀이이 문제는 그리디 알고리즘을 활용하여 최소한의 작업 횟수로 문제들을 원하는 색상으로 칠하는 방법을 찾는것이다.주어진 문자열 S에서 연속된 같은 색상의 블록을 그룹화 하여 최소한의 횟수로 전체를 칠 할 수 있도록 해야한다.8BBRBRBBR예시로 위와 같은 예제가 있다면 색상을 그룹화 하면 다음과 같다.BB | R | B | R | BB | R즉, B 그룹: 3개, R 그룹: 3개이 경우, 한쪽 색상만을 먼저 칠하고, 나머지를 한 번에 칠하는 것이 최소 작업 횟수를 보장한다.문제 풀이의 주요한 알고리즘연속된 같은 색상을 하나의 그룹으로 압축압축된 그룹에서 B ..
백준 10844 - 쉬운 계단 수 (파이썬)
백준 10844 - 쉬운 계단 수 (파이썬)
2025.02.23분류 : 다이나믹 프로그래밍https://www.acmicpc.net/problem/10844풀이먼저 문제 이해를 하면 다음과 같다.계단 수는 인접한 모든 자리의 차이가 1인 수이다.N이 주어질 때, 깊이가 N인 계단 수의 갯수를 구하는 문제이다.0으로 시작하는 수는 계단 수가 아니다.결과는 10^9로 나눈 나머지를 출력해야한다.문제 풀이를 위해서 DP 알고리즘을 사용한다.dp[i][j]를 길이가 j이고 마지막 숫자가 i인 계단 수의 갯수라고 정의한다.점화식을 세우면 다음과 같다.dp[j][i] = dp[j-1][i-1] + dp[j+1][i-1]즉, 길이가 i이고 끝자리가 j인 계단 수는 이전 자리(i-1)에서 끝자리가 j-1이거나 j+1이었던 경우의 합이다.초기 조건으로는dp[0][1] = 0 (0으..
백준 14889 - 스타트와 링크 (파이썬)
백준 14889 - 스타트와 링크 (파이썬)
2025.02.22분류 : 브루트포싱https://www.acmicpc.net/problem/14889풀이문제 분석을 하면 다음과 같다.N명의 사람을 두 개의 팀으로 나누어야한다.S[i][j]는 i번 사람과 j번 사람이 같은 팀일때 더해지는 능력치이다.두팀의 능력치 차이를 최소화 해야한다.능력치는 대팅이 아닐 수 있으며, 대각선 값은 항상 0이다.40 1 2 34 0 5 67 1 0 23 4 5 0예제의 값을 생각해보면 다음과 같이 풀이 할 수 있다. 일단 가능한 팀 조합은 다음과 같다.(1, 2) vs (3 , 4) → 능력치 차이 | 5 - 7 | = 2(1, 3) vs (2, 4) → 능력치 차이 | 9 - 10 | = 1(1, 4) vs (2, 3) → 능력치 차이 | 6 - 6 | = 0문제 풀이를 위한 해결 방..