th42500의 TIL

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 코드 효율 👉 메모리 : 15760 KB 👉 시간 : 164 ms 👉 코드 길이 (주석 및 print()함수 제외) : 1430 B ✔ 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { //..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 코드 효율 👉 메모리 : 14124 KB 👉 시간 : 124 ms 👉 코드 길이 (주석 및 print()함수 제외) : 1029 B ✔ 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main ..

배열(Array) 배열이란? 👉 일정한 자료형의 변수들을 하나의 이름으로 열거하여 사용하는 자료구조 배열의 필요성 👉 프로그램 내에서 여러 개의 변수가 필요할 때, 한번의 선언만으로 둘 이상의 변수를 선언할 수 있음 배열의 선언과 접근 1) 배열의 선언 자료형 이름[] = new 자료형[길이]; int arr[] = new int[10]; 2) 배열의 접근 배열명[인덱스번호] = 값; arr[0] = 20; 배열 순회 👉 ex) 2*n 배열 순회하는 방법 for(int i=0; i< arr.length(); i++) { for(int j=0; j 0; i--) { arr[i] = arr[i-1]; } arr[0] = temp; // 저장해두었던 원소 다시 채우기 } } 2️⃣ 배열 원소 왼쪽 Shift ..

DFS (Depth-First Search) ✔ 그래프 탐색 알고리즘 탐색(Search)이란 많은 양의 데이터 내에서 원하는 데이터를 찾는 과정을 의미 ✔ DFS 특징 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘으로, 깊이 우선 탐색이라고도 불림 재귀적으로 구현 또는 후입선출 구조의 스택을 적용 트리일 경우 순회 방향 (번호 순서대로 진행) 시간복잡도는 O(V+E) 👉 V : 노드 수, E : 에지 수 ✔ 동작 과정 1️⃣ 탐색 시작 노드를 스택에 삽입하고 방문 처리 2️⃣ 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드 꺼내기 3️⃣ 더 이상 2️⃣번의 과정을 수행할 수 없을 때까지 반복 ..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 코드 효율 👉 메모리 : 45612KB 👉 시간 : 600ms 👉 코드 길이(주석 포함) : 2503B ✔ 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.StringTokenizer; public class Main { // 회의실 배정 static class M..

Greedy Algorithm Greedy? 사전적 의미로는 탐욕스러운, 욕심 많은이라는 의미를 담고 있음 Greedy Algorithm 그리디 알고리즘은 Greedy의 사전적 의미인 "탐욕스러운"이라는 의미를 따와 탐욕법이라고도 불림 현재 상황에서 지금 당장 좋은 것만 고르는 선택을 반복적으로 활용하여 문제를 해결하는 방법 Greedy Algorithm의 필수 요소 탐욕적 선택 속성(Greedy Choice Property) 👉단순히 가장 좋아 보이는 방법을 선택했을 때 최적의 해를 보장할 수 있는지 검토함으로써, 탐욕적 선택이 항상 안전함을 보여야 함 최적 부분 구조(Optimal Substructure Property) 👉 현재 상황에서 가장 최적의 해를 구한 이후, 나머지에서 또 최적 해를 구하는..