전체 글132 [백준] 20437 파이썬 - 문자열 게임 2 문제https://www.acmicpc.net/problem/20437 코드import sysfrom collections import defaultdictinput = sys.stdin.readlinet = int(input())def solution(): w = input().strip() k = int(input().strip()) dict = defaultdict(list) for i in range(len(w)): if w.count(w[i]) >= k: # k개 이상 등장하는 문자열인 경우 dict[w[i]].append(i) # 좌표 저장 if not dict: print(-1) else: t.. 2025. 1. 9. [백준] 9935 파이썬 - 문자열 폭발 문제https://www.acmicpc.net/problem/9935 첫 풀이 코드import sysinput = sys.stdin.readlinestr = input().strip()explosion_str = input().strip()def check_explosion(str): # 시간초과 # new_str = "".join(str.split(explosion_str)) new_str = str.replace(explosion_str,"") return new_strdef solution(): global str while(True): # 문자열이 폭발 문자열을 포함하지 않는 경우 break if explosion_str not in str.. 2025. 1. 9. [백준] 2668 파이썬 - 숫자고르기 문제https://www.acmicpc.net/problem/2668첫 풀이 코드import sysfrom itertools import combinationsinput = sys.stdin.readlinen = int(input())array = [int(input()) for _ in range(n)]numbers = [i for i in range(1,n+1)]def find_match_set(arr): new_arr = [] for i in arr: new_arr.append(array[i-1]) arr.sort() new_arr.sort() if arr == new_arr: return True else: return .. 2025. 1. 8. [백준] 1976 파이썬 - 여행 가자 문제https://www.acmicpc.net/problem/1976 풀이union - find를 쓰는 문제이다.연결 정보들의 정보를 돌며 만약 1이라면 연결되어 있으므로 Union 함수를 사용한다. 이후 여행 계획들을 앞에서부터 두 개씩 검사하며,루트 노드가 하나라도 다르다면 NO를, 아니라면 YES를 출력해주면 되는 문제이다. 코드import sysinput = sys.stdin.readlinen = int(input())m = int(input())parent = [i for i in range(n+1)] graph = []# 노드 n의 루트노드 returndef find(n): if parent[n] != n: parent[n] = find(pa.. 2025. 1. 8. [백준] 1922 파이썬 - 네트워크 연결 문제https://www.acmicpc.net/problem/1922풀이최소 신장 트리를 구하는 간단한 문제였다. 오늘 다른 최소 신장 트리 관련 문제(아래 링크)를 풀어서 쉽게 풀 수 있었다. [백준] 1647 파이썬 - 도시 분할 계획문제https://www.acmicpc.net/problem/1647풀이최소 신장 트리 문제이다.최소 신장 트리란 가장 적은 비용 + 사이클 없음 + 모든 정점이 연결되어있는 트리이다. 신장 트리에서 연결된 단 하나의 간선을 끊jeongeunji1127.tistory.com 코드import sysinput = sys.stdin.readlinen = int(input())m = int(input())graph = []parent = list(range(n+1))for _ .. 2024. 11. 12. [백준] 2138 파이썬 - 전구와 스위치 문제https://www.acmicpc.net/problem/2138풀이아이디어가 필요한 그리디 문제였다. 주어진 입력 000을 목표 전구 010로 변환시키려면 각각 1,2,3번째 전구를 전부 눌러야한다. 이 문제의 핵심 아이디어는 전구를 누르는 순서는 관련이 없다는 것이다.1->2->3 순서로 누르든, 3->1->2 순서로 누르든 결과는 같다. 따라서 순차적으로 앞 인덱스부터 스위치를 누르면서 검사해주면 된다.순차적 검사이므로 한번 지나간 전구를 다시 검사하지 않는다.현재 검사하는 전구의 왼쪽 전구가 goal_bulbs와 다른 채로 넘어갈 수 없다는 뜻이다.(다시 앞의 전구로 돌아가 바꿀 수 없기 때문) 또한, 0번째 전구 누르기 or 누르지 않는 경우 두 가지의 경우의 수가 존재하므로 나누어 생각해주.. 2024. 11. 12. [백준] 1647 파이썬 - 도시 분할 계획 문제https://www.acmicpc.net/problem/1647풀이최소 신장 트리 문제이다.최소 신장 트리란 가장 적은 비용 + 사이클 없음 + 모든 정점이 연결되어있는 트리이다. 신장 트리에서 연결된 단 하나의 간선을 끊으면 2개의 신장 트리로 나뉜다.따라서 위 문제에서 비용이 가장 높은 간선을 끊으면 2개의 신장 트리로 나눌 수 있다. 나는 최소 신장 트리 구현을 위해 크루스칼 알고리즘을 사용했다.크루스칼 알고리즘은 간선을 가중치 기준으로 정렬하고, 가중치가 작은 간선부터 선택하여 트리를 만든다. 자세한 풀이는 아래와 같다. 1. 주어진 입력을 가중치(비용 c)가 작은 순서대로 정렬for _ in range(m): a,b,c = map(int,input().split()) graph... 2024. 11. 12. [Study] 팩토리 패턴 팩토리 패턴이란?팩토리 패턴이란 객체 생성에 관한 디자인 패턴이다.상속 관계에 있는 두 클래스에서 상위 클래스가 중요한 뼈대를 결정, 하위 클래스는 객체 생성에 관한 구체적인 내용을 결정하는 패턴이다.즉, 한 클래스에서 객체를 생성하는 역할을 파생 클래스에게 넘겨 수행하게 하는 것이다. 팩토리 패턴의 장점은 다음과 같다.1. 상위 클래스와 하위 클래스가 분리되어 느슨한 결합을 가진다.2. 상위 클래스는 인스턴스 생성 방식에 관해 알지 못하므로 다형성을 가진다.3. 새로운 기능을 추가할 때 해당 객체만 변경하면 되므로 유연성이 높아진다.4. 코드 리팩토링시 유지보수가 용이하다. 더보기Enum이란?상수의 집합을 정의할 때 사용되는 타입본질적으로 Thread Safe 하다 -> 싱글톤 패턴에 도움이 된다. T.. 2024. 11. 4. [Study] SCC (강한 연결 요소) SCC (Strongly Connected Component)란?- 어떤 두 정점을 잡든 서로 도달할 수 있는 경로가 있는 부분 방향 그래프- 유향 그래프 (방향이 있는 그래프)만 SCC를 가진다.- 한 그래프 내에 여러 개의 SCC가 존재할 수 있다.- 같은 SCC 모음 내의 노드는 어떤 경로를 통하더라도 다른 노드를 향해 갈 수 있어야 한다. 즉, 같은 강한 연결 요소에 속하는 정점들은 서로 이동할 수 있는 방향 경로가 반드시 존재한다.- 시간복잡도 O(V+E)를 가진다. SCC 알고리즘 구현 방법코사라주 알고리즘- 주어진 방향 그래프의 역방향 그래프와 스택을 사용하여 SCC를 구하는 알고리즘.- 방향 그래프와 역방향 그래프가 동일한 SCC를 구성한다는 것을 이용함.알고리즘1. 주어진 방향그.. 2024. 11. 4. 이전 1 2 3 4 ··· 15 다음
