작은 시작점

시작점을 오른쪽으로 이동시키면 항상 합이 감소하고,
끝점을 오른쪽으로 이동시키면 항상 합이 증가한다는 것을 알 수 있다.

package java_0626_twoPointer;
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] arr = new int[N+1];
        
        // 1부터 N까지 들어있는 배열
        for (int i = 1; i <= N; i++) {
			arr[i] = i;
		}
        
        int end = 1;
        int cnt = 0;
        int intervalSum = 0;

        // start를 인덱스 0부터 n까지 반복
        for (int start = 1; start <= N; start++) {
        	// 부분합이 res보다 작고,end 인덱스의 위치가 데이터의 개수보다 작을 때 실행
            while (intervalSum < N && end <= N) {
            	intervalSum += arr[end];
                end += 1;
            }
            if (intervalSum == N) {
                cnt += 1;
            }
            intervalSum -= arr[start];
        }

        System.out.println(cnt);
    }
}

N을 입력받고, 1~N까지 순차적으로 들어있는 배열을 만든다.

시작점과 끝점을 모두 맨 앞으로 위치시키고, 시작점이 끝까지 갈 때까지 계속 반복한다.

부분합을 0으로 초기화 시킨 후 끝점을 한칸씩 이동하면서 원하는 값이 N이 될 때까지 반복한다.

부분합이 N을 만족한다면, cnt++,
부분합이 N보다 커진다면, 시작점을 오른쪽으로 옮겨 합을 감소시킨다.
부분합이 N보다 작다면, 끝점을 오른쪽으로 이동시켜 합을 증가시킨다.

이를 계속 반복하다가 시작점이 배열의 끝까지 이동했다면, 반복문을 종료시킨 후

이를 만족하는 cnt의 개수를 출력한다.

import java.util.Scanner;

public class Main {
	public static int T; // 테스트 케이스 개수
	public static int n, m; // 나라 n개, 비행기 m
	public static int[] parent = new int[1000001]; // 부모 테이블 초기화하기
    public static int result = 0;
    
    // 특정 원소가 속한 집합을 찾기
    public static int findParent(int x) {
        // 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
        if (x == parent[x]) return x;
        return parent[x] = findParent(parent[x]);
    }

    // 두 원소가 속한 집합을 합치기
    public static void unionParent(int a, int b) {
        a = findParent(a);
        b = findParent(b);
        if (a < b) parent[b] = a;
        else parent[a] = b;
    }

	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        T = sc.nextInt();
        for (int t = 0; t < T; t++) {
            result = 0;
            n = sc.nextInt();
            m = sc.nextInt();
            
            // 부모 테이블상에서, 부모를 자기 자신으로 초기화
            for (int i = 1; i <= n; i++) {
                parent[i] = i;
            }
            
            for (int i = 0; i < m; i++) {
                int a = sc.nextInt();
                int b = sc.nextInt();
				
                if (findParent(a) != findParent(b)) {
                    unionParent(a, b);
                    result++;
                }
			}
            System.out.println(result);
		}
	}

}

상근이가 n개국을 여행할 때 m개의 비행기를 타고 이동해야하는데 가장 적은 비행기를 타야하니까 최소 간선의 개수를 구하면 된다.

가장 적은 종류의 비행기 == 최소 간선의 개수
1. 크루스칼 알고리즘으로 최소 신장 트리를 구한다.
2. 최소 신장 트리에 구성되어있는 간선의 개수가 최소 간선의 개수가 됨

T개의 테스트 개수만큼 반복해서 나라의 개수 n, 비행기의 개수 m을 구한다.

m번 a, b 쌍들을 입력 (a,b를 왕복하는 비행기)

a, b가 같은 집합에 속해있지 않을 때, 유니온 연산 실행(합집합을 만드는 연산) > 간선의 수 카운트 +1

만약 a, b가 같은 집합에 속해있다면, 유니온 연산을 실행하지 않음 -> 이미 이어지는 간선이 있다는 의미임 == 이어지는 비행기가 없어도 이동가능하다는 뜻 !

유니온 연산을 실행하는 것은 a, b가 이어지는 간선이 만들어진다는 의미이므로 비행기 종류의 최소 개수에 +1을 더함.

모든 연산이 끝나면 result 변수에 최소 간선의 수가 들어있게 된다.

크루스칼 알고리즘
가능한 한 최소한의 비용으로 신장 트리를 찾는 것

1. 간선 데이터를 비용에 따라 오름차순 정렬
2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인
- 사이클이 발생하지 않는. 경우 최소 신장 트리에 포함
- 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않음.
3. 모든 간선에 대하여 2번의 과정 반복

package java_0626_크루스칼;
import java.util.*;

class Edge implements Comparable<Edge> {
    private int distance; // 비용
    private int nodeA; // 시작점
    private int nodeB; // 종료점

    public Edge(int distance, int nodeA, int nodeB) {
        this.distance = distance;
        this.nodeA = nodeA;
        this.nodeB = nodeB;
    }

    public int getDistance() {
        return this.distance;
    }

    public int getNodeA() {
        return this.nodeA;
    }

    public int getNodeB() {
        return this.nodeB;
    }

    // 거리(비용)가 짧은 것이 높은 우선순위를 가지도록 설정
    @Override
    public int compareTo(Edge other) {
        return Integer.compare(this.distance, other.distance);
    }
}

public class Main {
	public static int max;
    // 노드의 개수(V)와 간선(Union 연산)의 개수(E)
    // 노드의 개수는 최대 100,000개라고 가정
    public static int v, e;
    public static int[] parent = new int[1000001]; // 부모 테이블 초기화하기
    // 모든 간선을 담을 리스트와, 최종 비용을 담을 변수
    public static ArrayList<Edge> edges = new ArrayList<>();
    public static int result = 0;

    // 특정 원소가 속한 집합을 찾기
    public static int findParent(int x) {
        // 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
        if (x == parent[x]) return x;
        return parent[x] = findParent(parent[x]);
    }

    // 두 원소가 속한 집합을 합치기
    public static void unionParent(int a, int b) {
        a = findParent(a);
        b = findParent(b);
        if (a < b) parent[b] = a;
        else parent[a] = b;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        v = sc.nextInt();
        e = sc.nextInt();

        // 부모 테이블상에서, 부모를 자기 자신으로 초기화
        for (int i = 1; i <= v; i++) {
            parent[i] = i;
        }

        // 모든 간선에 대한 정보를 입력 받기
        for (int i = 0; i < e; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int cost = sc.nextInt();
            edges.add(new Edge(cost, a, b));
        }

        // 간선을 비용순으로 정렬
        Collections.sort(edges);

        // 간선을 하나씩 확인하며
        for (int i = 0; i < edges.size(); i++) {
            int cost = edges.get(i).getDistance();
            int a = edges.get(i).getNodeA();
            int b = edges.get(i).getNodeB();
            // 사이클이 발생하지 않는 경우에만 집합에 포함
            if (findParent(a) != findParent(b)) {
                unionParent(a, b);
                result += cost;
                if (cost > max) max = cost;                
            }
        }

        System.out.println(result - max);
    }
}

핵심 아이디어 (전체 그래프에서 2개의 최소 신장 트리를 만들어야 함)
크루스칼 알고리즘으로 최소 신장 트리를 찾은 뒤에 최소 신장 트리를 구성하는 간선 중 가장 비용이 큰 간선을 제거
1. 최소 신장 트리 구축
2. 최소 신장 트리의 간선 중 가장 비용이 큰 간선 제거

사이클이 발생하지 않는 경우(a, b가 같은 집합이 아닌 경우) 유니온 연산 실행(같은 집합으로 만드는 과정)

유니온 파인드(Union Find)
여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과
두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘

union 연산 : 각 노드가 속한 집합을 1개로 합치는 연산

find 연산 : 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산

import java.util.*;

public class Main {
    // 노드의 개수(V)와 간선(Union 연산)의 개수(E)
    // 노드의 개수는 최대 100,000개라고 가정
    public static int n, m;
    public static int[] parent = new int[1000001]; // 부모 테이블 초기화하기

    // 특정 원소가 속한 집합을 찾기
    public static int findParent(int x) {
        // 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
        if (x == parent[x]) return x;
        return parent[x] = findParent(parent[x]);
    }

    // 두 원소가 속한 집합을 합치기
    public static void unionParent(int a, int b) {
        a = findParent(a);
        b = findParent(b);
        if (a < b) parent[b] = a;
        else parent[a] = b;
    }
    
    // 두 원소가 같은 집합에 포함되어있는지 확인
    public static void printParent(int a, int b) {
    	a = findParent(a);
    	b = findParent(b);
    	
    	if (a == b) System.out.println("YES");
    	else System.out.println("NO");
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        m = sc.nextInt();

        // 부모 테이블상에서, 부모를 자기 자신으로 초기화
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }

        // Union 연산을 각각 수행
        for (int i = 0; i < m; i++) {
            int bool = sc.nextInt();
            int a = sc.nextInt();
            int b = sc.nextInt();
            
            if (bool == 0) unionParent(a, b);
            else printParent(a, b);
        }
        sc.close();
    }
}

m번 입력받은 값을 차례대로 수행한다.

bool, a, b를 입력받고,

bool이 1이라면 유니온 파인드 연산을 실행하고,

0이라면  a,b가 같은 집합에 포함되어 있는지를 확인하는 연산을 실행한다.

// 특정 원소가 속한 집합을 찾기
public static int findParent(int x) {
    // 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if (x == parent[x]) return x;
    return parent[x] = findParent(parent[x]);
}

// 두 원소가 속한 집합을 합치기
public static void unionParent(int a, int b) {
    a = findParent(a);
    b = findParent(b);
    if (a < b) parent[b] = a;
    else parent[a] = b;
}

루트 노드드 찾을 때까지 재귀적으로 findParent를 호출해서 루트 노드를 찾고

이후 unionParent에서 값을 비교하여 작은 노드의 값을 루트 노드로 넣는다.

import sys
input = sys.stdin.readline

exp = input().rstrip().split('-') 
arr = []

for i in range(len(exp)):
  temp = 0  
  for t in exp[i].rstrip().split('+'):
    temp += int(t)
  arr.append(temp)

res = arr[0]
for a in arr[1:]:
  res -= a

print(res)

최솟값을 찾는 기준을 잘 모르겠어서 고민하다가 검색해서 알아낸 , , 답 

괄호를 적절히 쳐서 값을 최소로 만드는 방법은, 핵심적으로 '-' 연산자를 기준으로 나누는 것

이렇게 하면 '-' 연산자를 기준으로 나눠진 부분들을 먼저 더한 후, 마지막에 뺄셈을 수행하여 값을 최소화할 수 있음

1. 식을 '-' 연산자를 기준으로 나눈다.
2. 나눠진 부분 더하기 > 각 부분 문자열에 대해 '+' 연산자를 기준으로 더한다.
3. 처음 부분은 더한 값을 초기값으로 두고, 그 다음 나머지 더한 값들을 뺀다.

예를 들어, 입력이 "55-50+40-30+20+10"이라면,

1. "-" 기준으로 나누기 > ["55", "50+40", "30+20+10"]
2. 나눠진 부분 더하기
   
   • "55" → 55
   • "50+40" → 90
   • "30+20+10" → 60
3. 첫 번째 값에서 나머지 값들을 빼줍니다:
   • 55 - 90 - 60 = -95

결과적으로, 최소값은 -95

import sys
input = sys.stdin.readline
from collections import Counter

N = int(input())
Narr = list(map(int, input().split()))
Narr.sort()

M = int(input())
Marr = list(map(int, input().split()))
isTrue = False

# Counter를 사용하여 각 요소의 개수를 미리 셈
count_dict = Counter(Narr)
countArr = [0] * M

for i in range(M):
  pl = 0
  pr = N - 1

  while(pl <= pr):  
    pc = (pl + pr) // 2

    if (Marr[i] == Narr[pc]):
      countArr[i] = count_dict[Marr[i]]
      break
    elif (Marr[i] < Narr[pc]):
      pr = pc - 1
    else:
      pl = pc + 1

print(" ".join(map(str, countArr)))

바로 이전 포스팅 수 찾기와 비슷하게 이진탐색을 활용해서 풀었다.

그 전과 다른 점은 각 수가 적힌 카드의 개수를 세는 것이었는데 처음에 count 함수로 풀었더니 시간초과가 났다. ..

시간 초과 문제가 발생하는 이유는 배열을 정렬한 후, 이진 탐색을 사용하여 값을 찾고, 다시 해당 값을 count 메소드를 사용하여 세는 과정이 비효율적이기 때문입니다. 이 방식은 큰 데이터셋에서 비효율적일 수 있습니다. - gpt의 답변 ...

countArr[i] = Narr.count(Narr[pc])

if문 안에서 값을 찾은 후 count 메소드를 사용하였는데 이게 비효율적이라고 한다.

그래서 Counter 함수를 이용해서 각 요소의 개수를 미리 계산해두고,

 값을 찾았다면 count_dict 에서 해당 값의 요소 개수를 바로 가져와 사용할 수 있도록 했다.

그리고 countArr가 배열 형태로 출력되므로 join을 활용해서 문자열처럼 출력되도록 한다.

이진 검색 : 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
A.sort()

M = int(input())
arr = list(map(int, input().split()))
isTrue = True

for key in arr:
  pl = 0
  pr = N - 1
  isTrue = False

  while (pl <= pr):
    pc = (pl + pr) // 2
    if key == A[pc]:
      print(1)
      isTrue = True
      break
    elif (key < A[pc]):
      pr = pc - 1
    else:
      pl = pc + 1
  if not isTrue: print(0)

이진 검색을 활용해서 풀었다

중앙 요소의 인덱스를 while문 안에 넣어서 pl, pr 값에 따라 계속 바뀌도록 해야하는데

while문 밖에두고서는 오류를 찾지 못해 애먹었다 .. ㅎㅎ;

이진검색을 하려면 정렬된 배열이 필요하기 때문에 A를 정렬한 후 시작한다.

첫 인덱스(pl)와 마지막 인덱스(pr), 그리고 중앙 인덱스(pc) 값을 잡고,

먼저, 중앙 값을 기준으로

1. 중앙 값과 key값이 일치하면 1을 출력,

2. 중앙 값보다 작으면 왼쪽 배열만 검색하면 되기 때문에 pr 끝 값을 pc - 1로 지정하여 왼쪽 배열만 검색하도록

3. 반대로 중앙 값보다 key 값이 크다면 오른쪽 배열만 검색하면 되기 때문에 첫 인덱스(pl) 값을 pc + 1로 지정하여 오른쪽 배열만 검색하도록 한다.

반복문을 통해, pl, pr, pc 값의 범위를 줄여나가면서 일치하는 값을 찾으면 된다.

만약 없다면 isTrue 값이 False로 맨 아래 조건문에 걸려 0을 출력하도록 한다.

import sys
input = sys.stdin.readline

N = int(input())
time = [*map(int, input().split())]
time.sort() # 인출하는 시간이 짧은 사람 먼저 줄세우기 
sum = 0
total = 0

for i in range(len(time)):
  sum += time[i] 
  time[i] = sum # 앞 사람 시간 + 내 시간 => i번째 사람이 걸리는 시간
  total += time[i] # N명의 사람이 걸리는 총 시간의 최솟값

print(total)

인출하는데 걸리는 시간이 짧은 사람이 먼저와야 누적 시간이 최소화된다.

입력받은 인출 시간이 짧은 사람부터 정렬을 한 뒤에

i번째 사람의 총 시간을 계산하고 (앞 사람 인출 시간 + 자신의 인출 시간)

N명의 각자 총 인출 시간을 합산한다.

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
coins = []
count = 0

coins = [int(input()) for _ in range(N)]

coins.sort(reverse=True)

for coin in coins:
  count += K // coin
  K = K % coin
  if K == 0: break

print(count)

동전이 오름차순으로 입력되는데 우리는 필요한 동전 개수의 최솟값을 출력해야하기 때문에 내림차순 정렬을 한다.

1. K원을 큰 동전부터 나눈 후 몫을 count 한다.

ex) 4200원이면 4200 // 1000 > 동전 4개 카운트

2. K원을 큰 동전으로 나눈 나머지를 다시 반복해서 나눌 수 있도록 K에 넣는다.

ex) 4200 % 1000 > 200원

남은 200원으로 반복문 수행, 남은 돈이 0이 될 때까지 반복

import sys
input = sys.stdin.readline

N = int(input())
time = []

for i in range(N):
  start, end = map(int,input().split())
  time.append((start, end))

time.sort(key=lambda x : (x[1], x[0]))

cnt = 1
end = time[0][1]

for i in range(1, N):
  if time[i][0] >= end:
    end = time[i][1]
    cnt += 1

print(cnt)

회의가 빨리 끝나게 되면 남은 회의 시간이 많아서 더 많은 회의를 할 수 있다.

그래서 빨리 끝나는 순서대로 회의 시간을 정렬한다.

time.sort(key=lambda x : (x[1], x[0]))

두 번째 값(x[1])을 먼저, 첫 번째 값(x[0])을 그 다음 기준으로 삼아 정렬하는 방식

x[1]이 회의 종료시간이기 때문에 회의가 빨리 끝나는 순서대로 정렬되게 됨

(이 과정에서 요소 자체는 변하지 않고, 정렬 기준만 달라지는 것)

정렬된 회의시간을 반복해서 다음 회의 시작 시간 >= 이전 회의 끝나는 시간 을 만족할 때 해당 회의를 진행하도록 한다.

for i in range(1, N):
  if time[i][0] >= end:
    end = time[i][1]
    cnt += 1

이미 회의가 빨리 끝나는대로 정렬되어 있기 때문에 회의 시간이 겹치지 않도록 조건만 걸어준다.

겹치지 않을 때, 해당 회의 끝나는 시간을 end에 넣어서 다음 조건을 실행할 수 있게하고

회의 횟수 cnt를 더한다