String 문자열을 + * / 기호로 나누고 싶을 때, String[] tmp = str.split("+"); 다음과 같이 작성하면 java.util.regex.PatternSyntaxException: Dangling meta character ‘+’ near index 0 에러가 발생한다. 정상적으로 동작하기 위해서는 \\ 을 붙여주면 된다. String[] tmp = str.split("\\+");
11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 532ms 다익스트라 특정노드에서 다른노드까지의 최소 비용을 구하는 문제로 다익스트라 알고리즘을 사용했다. 단, 이 문제에서는 최소 비용뿐만 아니라 출발노드에서 도착노드까지의 최단 경로에 포함되는 노드 또한 출력해줘야 한다. 다익스트라는 많이 해봐서 빠르게 최소비용을 구할 수 있었지만 최단 경로에 포함되어 있는 노드를 찾는 데 어려움이 있었다. 다익스트라 알고리즘에 이전의 노드를 저장해주는 코드를 추가한 후, 경로를 역추적하며 해결..
1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 504ms 그리디 한 개의 회의실을 사용할 수 있는 회의의 최대 개수를 구하는 문제로 그리디 알고리즘의 대표적인 문제이다. # 접근 방식 1. 일찍 끝나야 다음 회의를 진행하므로 끝나는 시간을 기준으로 오름차순 정렬한다. 2. 회의 끝나는 시간이 다음 회의 시작 시간보다 작거나 같아야한다. Comparable 인터페이스를 통해 끝나는 시간을 기준으로 오름차순 정렬하며 끝나는 시간이 같을 때는 시작 시간 기준으로 오름차순 정렬을 해준다. import java.io.*; import java.util.*; public class Main { static class Node impl..
Web Storage 에는 LocalStorage 와 SessionStorage 가 있다. 데이터는 키와 값(key-value)으로 저장하며 값은 문자열로 저장된다. ✅ 공통 메소드와 프로퍼티 setItem(key, value) getItem(key) removeItem(key) clear() key(index) : index에 해당하는 key length Local Storage 데이터를 사용자의 로컬에 보존하는 방식이다. 데이터를 저장, 덮어쓰기, 삭제 등 조작이 가능하며 자바스크립트로만 조작할 수 있다. 🍪 Cookie와의 차이점 유효기간이 없고 영구적으로 이용 가능 단순 문자열 외에 객체 정보 저장 가능 용량제한이 없음 ( 쿠키는 도메인당 20개의 쿠키 수가 제한되면 4KB까지 ) 쿠키와는 다르게..
💡 기존 JAVA와 동일 시 되는 부분은 생략하여 작성함 JavaScript 선언 HTML에서 JavaScript를 사용하려면 태그를 사용 태그는 HTML 파일 내부의 나 안 어느 곳에서나 선언 가능하지만 안의 끝부분에 태그를 둘 것을 권장 웹 브라우저가 HTML문서를 순차적으로 해석(parsing)하므로, script 위치에 따라 로드의 실행 시점이 달라진다. 변수 변수의 타입 지정없이 값이 할당되는 과정에서 자동으로 변수의 타입이 결정 같은 변수에 여러 타입의 값을 할당 가능 Camel 표기법을 사용 키워드, 공백, 문자 포함, 숫자로 시작X 특수 문자 _ $ 허용 Camel case : 소문자로 작성하되 2개 이상의 단어일 경우 단어의 첫 글자는 대문자로 표기 자료형을 원시타입(primitive)과..
그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 일반적인 그리디 알고리즘 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다. 하지만 코테에서의 대부분 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제된다. 거스름 돈 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. 단 N은 항상 10의 배수입니다. 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러 주면..
1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 192ms 다익스트라 특정 노드에서 모든 노드까지의 최단 경로 계산문제로 다익스트라 구현 구해야 하는 것 go : 1번부터 n번 마을에서 x번 마을로 가는 최단 시간 back : x번 마을에서 1번~n번 마을로 되돌아가는 최단 시간 여기서 1~n번 마을에서 x번 마을로 가는 최단 시간(go)은 입력으로 주어진 to 와 from 을 반대로 저장한 그래프에서 x번을 출발노드로 하고 1번부터 n번노드까지 가는 최단 경로를 계산하는 것과 ..
1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 640ms 다익스트라 1부터 N까지 u와 v를 반드시 거치면서 최단 경로를 구해야 하는 문제이다. 다음과 같은 두 가지 경로 중 더 짧은 경로를 선택하면 된다. 1 → u → v → n 1 → v → u → n 입력이 양방향 그래프로 주어지므로 u가 시작노드일 때의 다익스트라, v가 시작노드일 때의 다익스트라를 실행해준다. dijkstra(u); // u를 출발노드로 1, v, n의 최단경로 구하기 startU = d..
1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 516ms 다익스트라 특정 노드에서 다른 노드까지의 최단 경로를 계산하는 문제로 다익스트라 알고리즘을 이용하였다. 다익스트라 알고리즘 : 하나의 출발점에서 다른 모든 출발지까지 최단 경로 계산 최단 경로 알고리즘은 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중 간선의 가중치 합이 최소인 경로를 찿는 알고리즘을 의미한다. 다익스트라 알고리즘 다익스트라 알고리즘은 gangintheremark.tistory.com imp..
1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 최소 신장 트리(Minimum Spanning Tree)를 구하는 문제로 크루스칼 알고리즘과 프림 알고리즘으로 구현해보았다. 크루스칼 알고리즘 : 최소 신장 트리(MST)를 찾는 알고리즘 신장 트리란 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이 gangintheremark.tistory.com ..
11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 244ms 벨만 포드 알고리즘 특정 노드(1번 노드)에서 모든 노드로 가는 가장 빠른 시간을 순서대로 출력하는 문제로 최단 경로를 계산하는 문제이다. 그리고 이 문제에서는 가중치가 음수의 값을 가지므로 다익스트라가 아닌 벨만 포드 알고리즘으로 최단 경로를 계산한다. 음의 가중치 순환으로 시간을 무한히 오래 전으로 되돌릴 수 있으면 -1 출력해야 하므로 전체 간선을 확인하며 최단 거리 테이블 d 를 갱신한..
모든 간선의 비용이 양수일 때는 다익스트라 최단 경로 알고리즘을 사용하면 된다. 하지만 음수 간선이 포함된다면? 음수 간선이 있는 경우 음수 간선 순환이 없는 경우 음수 간선 순환이 있는 경우 벨만 포드 알고리즘은 음수 간선의 순환을 감지할 수 있으며 음의 간선이 포함된 상황에서 사용할 수 있다. 시간복잡도는O(VE)로 다익스트라 알고리즘에 비해 느리다. 동작과정 1. 출발 노드 설정 2. 최단 거리 테이블 초기화 3. V-1번 반복 3-1. 전체 간선 E개를 하나씩 확인 3-2. 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신 4. 음수 간선 순환이 발생하는지 체크하고 싶다면 3번의 과정을 한 번 더 수행 → 최단 거리 테이블이 갱신된다면 음수 간선 순환이 존재 다익스트라 vs..
