본문 바로가기

algorithm11

[그래프 이론] Matching과 Vertex Cover 간단 정리 Matching그래프 $ G = (V,E) $ 에서 Matching(매칭) 이란,간선들의 부분집합 $ M \subseteq E $ 가 모든 간선이 서로 정점을 공유하지 않는 경우에, $ M $ 을 Matching 이라고 한다.그래프에서 겹치지 않는 간선들의 부분집합을 고르는 것.즉, 어떤 정점도 두 개 이상의 매칭 간선을 가질 수 없음.예를 들어, 소개팅 시켜줄 때, 한 명이 여러명과 연결되면 안 됨. 즉, 1:1 짝을 짓는 것이 Matching Maximal Matching : 더 이상 간선을 추가할 수 없는 매칭Maximum Matching : 가장 많은 정점을 포함하는 매칭Perfect Matching : 모든 정점이 매칭에 포함된 경우  Vertex Cover그래프 $ G = (V,E) $ 에서 .. 2025. 3. 12.
[이코테] 1이 될 때까지 문제어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.1. N에서 1을 뺀다.2. N을 K로 나눈다.예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 된다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 된다. 이는 N을 1로 만드는 최소 횟수이다.N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.입력 조건첫째 줄에 N(2≤ N ≤ 100,000)과 K(2≤ K ≤ 100,000)가 공백으로 구분되며 각각 자연수로 주어.. 2025. 2. 19.
[이코테] 숫자 카드 게임 문제숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다.1. 숫자가 쓰인 카드들이 N X M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다.2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.3. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.카드들이 N X M 형태로 놓여 있을 때, 게임의 룰에 맞게 카드를 뽑는 프로그램을 만드시오.입력첫.. 2025. 2. 19.
[이코테] 큰 수의 법칙 문제동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다. 예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정한다. 예를 들어 순선대로 2, 4, 5, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6 + 6 + 6 + 5 + 6 + 6 +6 +5인  46이 된다.단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다. 예를 들어 순서대로 3, 4.. 2025. 2. 18.
[BOJ] 1874: 스택 수열 (python) https://www.acmicpc.net/problem/1874 문제 문제 이해 하는 데에만 5분? 걸렸다. (이럴 때 마다 자괴감 듦..)사실 문제를 제대로 잘 안읽어서 그랬던 거다.아직 코테 공부 초기이니 하다보면 문제 읽는 거, 핵심 파악하는 거, 전부 늘겠거니 생각하고 있다.1부터 N까지의 수를 스택에 넣었다가 다시 빼서 수열을 만들었을 때, 입력으로 넣은 수열을 만들 수 있느냐. 임index 비교해서 +하고 -하는 아이디어까지는 생각했지만, 결국 while문을 생각 못해서 끝내 힌트 참고 했다. 코드import sysn = int(sys.stdin.readline())num = [int(sys.stdin.readline().strip()) for _ in range(n)]stack = []op.. 2025. 2. 15.
배열(Array)과 리스트(List) 개념 정리 배열 (Array)배열의 특징- 동일한 자료형을 가지는 데이터들의 집합- 고정된 크기 (정적 할당)- 연속된 메모리 공간에 저장됨- Index 기반으로 빠른 조회 가능 (O(1))- 삽입, 삭제 시 연산이 느림 (O(n)) (중간 요소 변경 시 모든 요소 이동이 필요하기 때문)배열의 장점- 메모리 접근 속도가 빠르다. (연속된 메모리 할당)- Index 기반으로 빠른 조회 가능 (O(1))- CPU 캐시 최적화가 가능배열의 단점- 크기가 고정됨 (Python 예외)- 중간 삽입/삭제 시 비효율적 (뒤 요소들을 이동해야 함)시간 복잡도- 접근 (Access) : O(1)- 삽입 (Insert) & 삭제 (Delete) : O(n)  리스트 (List)리스트의 특징- 크기가 동적으로 변경 가능 (가변 길이).. 2025. 2. 6.