Algorithm 썸네일형 리스트형 ArrayList add메서드 앞으로 테스트 준비를 하면서 나를 고생시킨 문제에 대해선 이곳에 막글을 남겨야겠다. 며칠동안 골머리를 앓게한 부분이다.전체 테케 중 마지막 테케만 아쉽게 시간초과가 발생했던 부분인데,요구사항대로 구현을 하면서 좀 더 쉽게 구현을 하려다 보니 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: 중첩 반.. 더보기 <BOJ> 1717 자바 (집합의표현) + 유니온파인드 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(합치기):두 집합을 하나로 합치는 과정. 집합의 대표자를 기준으로 병합.일반적으로 한 집합의 루트를 다른 집합의 루트로 설정하여 합칩니다. 유니온 파인드 알고리즘의 특징시간 복잡도.. 더보기 <BOJ> 1753자바 (최단경로) 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[].. 더보기 <BOJ> 11779 자바 (최소비용 구하기2) https://www.acmicpc.net/problem/11779 23% 시간초과로 어리둥절했던 문제이다.분명 다익스트라로 잘 구현했는데 시간초과가 발생했다. 문제는 아래 핵심이라고 주석메모를 해놓은 부분이다. 다익스트라를 구현 할 때 가중치가 작은 순으로 PQ에 담기는데,큐에서 꺼낸 노드의 누적 비용(cur.w)이 해당 노드의 dist[cur.v]와 다를 수 있는 경우가 발생한다는 것이다.언제? 간선의 수(m)가 많아질수록, 즉 복잡한 그래프일수록 발생할 가능성이 높아진다. 간선의 수가 적을 때만 테스트 해보니 간과했던 부분이었다. 더보기왜 이런 상황이 발생하는지 설명하겠습니다:PriorityQueue 특성: 다익스트라 알고리즘에서 우선순위 큐는 가장 짧은 거리를 가진 노드를 먼저 꺼냅니다. 하지만 .. 더보기 이전 1 2 3 4 다음
