true-false

앞으로 테스트 준비를 하면서 나를 고생시킨 문제에 대해선 이곳에 막글을 남겨야겠다. 며칠동안 골머리를 앓게한 부분이다.전체 테케 중 마지막 테케만 아쉽게 시간초과가 발생했던 부분인데,요구사항대로 구현을 하면서 좀 더 쉽게 구현을 하려다 보니 add 메서드의 파라미터 인덱스를 0으로 넣어줬다.이부분 때문에 시간복잡도가 O(N)으로 되면서 제시간에 패스를 못했다.(이 외에도 리스트의 요소를 삭제할 때 Binarysearch를 해줬어야 했음)열심히 구현하다가 디버깅을 하다보면 이런 문제점들이 쉽게 보이지 않는다.

조합 계산은 다음 공식을 사용합니다:조합 공식:예시 계산: 5C35C3여기서:n=5n = 5 (전체 태그 수)r=3r = 3 (선택할 태그 수)공식을 대입하면:팩토리얼 계산:5!=5×4×3×2×1=1203!=3×2×1=63! = 3 \times 2 \times 1 = 63!=3×2×1=62!=2×1=22! = 2 \times 1 = 22!=2×1=2따라서:결과:5개의 태그 중 3개를 선택하는 조합의 수는 10가지입니다.

자료구조를 이해하는 것은 매우 중요하며, 이는 다음과 같은 이유로 연결됩니다: 1. 시간 복잡도와 자료구조의 관계알고리즘의 시간 복잡도는 사용하는 자료구조에 크게 영향을 받습니다.자료구조를 적절히 선택하면 비효율적인 알고리즘을 최적화할 수 있습니다.예제: 두 숫자의 합을 찾는 문제브루트 포스 (완전 탐색):이 경우 O(N2)O(N^2)입니다.for (int i = 0; i 해시셋(HashSet)을 이용한 최적화:이 경우 O(N)O(N)로 훨씬 효율적입니다.자료구조(HashSet) 덕분에 탐색 연산이 O(1)O(1)로 빨라졌습니다.Set set = new HashSet(); for (int num : arr) { if (set.contains(target - num)) { return true; } set..

시간 복잡도(Time Complexity)는 알고리즘이 실행되는데 필요한 연산 횟수를 입력 크기 NN에 따라 분석하는 것입니다. 이를 통해 알고리즘의 효율성을 비교하고, 입력 크기가 증가했을 때의 성능을 예측할 수 있습니다. 아래는 시간 복잡도를 계산하는 기본 방법과 개념입니다.  1. 시간 복잡도 계산의 기본 원칙가장 많이 반복되는 연산을 기준으로 계산합니다.상수 시간은 무시합니다 (예: O(1)+O(N)→O(N)).가장 높은 차수의 연산만 남깁니다 (예: O(N^2+N)→O(N2)). 2. 시간 복잡도 분석 단계(1) 반복문 확인반복문이 실행되는 횟수를 기반으로 복잡도를 계산합니다.예제 1: 단일 반복문for (int i = 0; i 반복문은 N번 실행되므로 시간 복잡도는 O(N).예제 2: 중첩 반..

https://www.acmicpc.net/problem/1717 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;//https://www.acmicpc.net/problem/1717public class 유니온파인드1_집합의표현 { static int[] parent; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ..

유니온 파인드(Union-Find)유니온 파인드는 서로소 집합(Disjoint Set)을 표현하고 관리하기 위해 사용하는 자료구조입니다.서로소 집합은 겹치는 원소가 없는 여러 그룹으로 나뉜 데이터를 표현하며, 대표적으로 그래프에서의 연결성 확인에 사용됩니다. 주요 연산Find(찾기):특정 원소가 어떤 집합에 속해 있는지 확인합니다.집합을 식별할 수 있도록 각 집합에는 고유한 root가 있습니다.x의 부모를 찾는 과정경로 압축(Path Compression)을 사용해 탐색 과정에서 트리의 깊이를 줄여 효율성을 높입니다.Union(합치기):두 집합을 하나로 합치는 과정. 집합의 대표자를 기준으로 병합.일반적으로 한 집합의 루트를 다른 집합의 루트로 설정하여 합칩니다. 유니온 파인드 알고리즘의 특징시간 복잡도..

https://www.acmicpc.net/problem/1753 풀이 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.PriorityQueue;import java.util.StringTokenizer;//https://www.acmicpc.net/problem/1753public class Main { private static int E; private static int V; private static int K; private static ArrayList[] AL; private static int[]..

https://www.acmicpc.net/problem/11779 23% 시간초과로 어리둥절했던 문제이다.분명 다익스트라로 잘 구현했는데 시간초과가 발생했다. 문제는 아래 핵심이라고 주석메모를 해놓은 부분이다. 다익스트라를 구현 할 때 가중치가 작은 순으로 PQ에 담기는데,큐에서 꺼낸 노드의 누적 비용(cur.w)이 해당 노드의 dist[cur.v]와 다를 수 있는 경우가 발생한다는 것이다.언제? 간선의 수(m)가 많아질수록, 즉 복잡한 그래프일수록 발생할 가능성이 높아진다. 간선의 수가 적을 때만 테스트 해보니 간과했던 부분이었다. 더보기왜 이런 상황이 발생하는지 설명하겠습니다:PriorityQueue 특성: 다익스트라 알고리즘에서 우선순위 큐는 가장 짧은 거리를 가진 노드를 먼저 꺼냅니다. 하지만 ..

https://www.acmicpc.net/problem/1086 이번 문제는 '세그먼트 트리'를 활용해 풀어야 하는 문제이다.log나 복잡한 식을 이용하지 않고 treeSize를 구하도록 최대한 쉬운 방법으로 접근해보았다.총 3가지 순서로 구현된다. 1. 트리 사이즈 및 offset 구하기2. 트리 초기화3. 인덱스 트리를 이용해 최솟값 구하기 세그먼트 트리를 이용하려면 우선 트리의 총 사이즈부터 구해야한다.이 문제에서 주어진 노드의 수는 10이다. 따라서 10개 이상을 담아야하는 리프노드를 구해야하는데1부터 시작해서 2를 곱해주면서 주어진 노드의 갯수를 초과하는 때를 캐치한다.이 때 캐치한 2의 배수는 문제에서 주어진 인덱스(1~N)를 리프노드의 인덱스로 치환하기 위한 offset으로 사용되고,off..

최소 신장 트리 (Minimum Spanning Tree)그래프 이론에서 최소 신장 트리란 모든 노드들을 연결하면서 사이클이 존재하지 않고 각 간선의 가중치의 합이 최소인 트리주어진 연결 그래프가 있을 때, 최소 신장 트리를 찾는 것은 네트워크 설계, 클러스터링 등의 다양한 분야에서 매우 중요한 문제이다.  특징모든 노드가 연결: 그래프의 모든 노드가 서로 연결되어 있어야 하며, 이 과정에서 어떤 노드도 고립되지 않습니다.사이클이 존재하지 않음: 최소 신장 트리는 트리 구조이므로, 간선이 하나 더 추가되면 사이클이 생기게 됩니다. 따라서 트리에서는 절대 사이클이 존재할 수 없습니다.최소 가중치: 주어진 그래프의 모든 간선 중, 가중치의 합이 최소가 되도록 간선을 선택합니다.연결된 그래프: MST는 그래프..