본문 바로가기

공부/Algorithms w.Java48

[Java] 백준 2098 외판원 순회 - dp, bitmasking https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 오랜만에 이산수학 책을 폈다 ㅎㅎ - 해밀턴 경로 : 그래프의 점을 모두 방문하되, 중복하여 방문하지 않고 모든 점을 지나는 경로. (1->2->3->4) - 해밀턴 순환 : 그래프의 점을 모두 방문하고, 중복하여 방문하지 않으며, 처음 시작 점으로 돌아오는 경로. (1->2->3->4->1) 순환이기에 모든 점을 출발점으로 외판원 순회 경로를 계산하지 않아도.. 2024. 1. 21.
[Java] 프로그래머스 250137 -붕대감기 class Solution { public int solution(int[] bandage, int health, int[][] attacks) { int answer = health; // 현재 체력. 처음엔은 최대 최력으로 시작. int t = bandage[0], x = bandage[1], y = bandage[2]; int lastAttackedTime = 0; // 마지막으로 공격당한 시각 int recoveryTime = 0; // 연속 회복 시간 for(int i=0; i health) ? health : answer; // 현재 체력은 최대 체력보다 클 수 없다. //answer = Math.min(answer + (recoveryTime * x) + (recoveryTime / t) *.. 2024. 1. 20.
[Java] 백준 2637 장난감 조립 - 위상정렬, dp import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; StringBuffer sb = new StringBuffer(); int n .. 2024. 1. 7.
[Java] Deque / 위상정렬 / 백준 2252 Deque 큐의 양쪽에서 데이터를 삽입과 삭제를 할 수 있는 자료구조 new ArrayDeque(), new LinkedList() 등으로 선언 Deque que = new ArrayDeque(); Deque que = new LinkedList(); Deque 삽입 Deque deque = new ArrayDeque(); // Deque 선언 // 값 추가 deque.addFirst("Hello"); deque.offerFirst("Hello"); deque.addLast("World"); deque.offerLast("World"); deque.add("Hello"); addFirst() : Deque의 맨 앞에 데이터를 삽입합니다. 용량을 초과하는 경우 Exception이 발생합니다. offerFi.. 2024. 1. 6.
[Java] ArrayList, LinkedList ArrayList vs LinkedList ArrayList 배열처럼 데이터들이 순서대로 나열되어 있다. 크기가 한정되어 있다. 즉, 크기가 한정되어 있고 순서대로 저장이 되어 각 요소의 저장 주소값이 연속적이다. 삽입, 삭제 연산이 비효율적이다. 메모리 낭비. 무작위 접근 O 시간 복잡도 : O(1) LinkedList 각 노드들이 앞 노드, 뒤 노드와 연결되어 있다. (→ 그래서 Queue의 삽입, 삭제가 가능하다.) 무한 개의 자료를 삽입할 수 있다. 삽입, 삭제 연산이 효율적이다. 무작위 접근 X, 처음 노드부터 순차적 접근 O arrayList와 다르게, 다음 노드의 저장 주소값이 랜덤하다. 처음 노드부터 순서대로 탐색해야 한다. 시간 복잡도 O(n) 포인터 사용(뒤 노드의 주소값 저장)으로 인.. 2024. 1. 6.
[LeetCode 264] Ugly Number II; Java 사전지식 - prime factor = 소인수 - 인수 : =약수. 자연수 a, b, c 에 대하여 a=bxc 일 때, b와 c는 a의 인수 - 소인수 : 자연수의 약수 중에서 소수인 수. 12의 약수는 1,2,3,4,6,12. 12의 소인수는 2,3(1,2,3,4,6,12 중 소수) - 소인수분해 : 모든 정수는 소인수들만의 곱으로 표현할 수 있고, 이를 소인수분해라고 한다. 12 = 3*4 = 3*(2*2) 문제 https://leetcode.com/problems/ugly-number-ii/description/ 소인수를 2,3,5만 갖는 수 중에서 n번째 큰 수를 구하여라. 궁금했던 점 소인수를 2,3,5만 가져야 하는데 왜 소수도 아닌 1이 항상 고려되는가? 답 1은 소수가 아니다. 따라서 어떠.. 2023. 12. 17.

티스토리툴바