알고리즘/코테에 필요한 지식만
다익스트라 알고리즘
1. 개념 두 노드를 연결할 때, 가중치가 최소인 것을 구하는 알고리즘 2. 설명 1부터 시작할 때, minEdge[] 배열을 나타냈다. 각 노드를 탐색하면서 minEdge에 가중치를 누적 시킨다. 3. 문제 www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net for문을 전부 탐색해서 최소 누적치를 찾는 풀이 -> 시간초과 때문에, 노드 수가 많으면 못 푼다. import java.util.ArrayList; import java.ut..
투 포인터
1. 투 포인터 포인터를 2개 사용하여 더 빠르게 배열을 탐색할 수 있다. 2. 예시문제 www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 3. 설명 문제의 N의 크기가 100000이기 때문에 이중for문을 쓰면 시간 초과가 난다. 그렇기 때문에 투 포인터를 사용해야한다. k개를 탐색한 경우 가장 마지막에 더한 값을 빼주고, 현재 값을 더하는 식으로 해결 가능 import java.util.Scanner; public class back_2559수..
LIS 최장 증가 부분수열
1. 개념 2. 예시 swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWBOKg-a6l0DFAWr SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com O(N^2) 풀이법 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Scanner; public class swea_3307최장증가부분수열 { public static void main(String[] args) { Scanner sc = new Sc..
순열과 조합 뿌시기
1. 순열 1) 순열이란? {1,2,3}이 주어졌을 때, {1,2,3} {1,3,2} {2,1,3} {2,3,1} {3,1,2} {3,2,1}처럼 순서를 바꿔서 나타낼수 있는 모든 경우를 말한다 2) 코드 크기가 3인 배열의 순열을 구했다. public class 순열 { static String fruits[] = {"사과", "바나나", "딸기"}; static boolean check[]= new boolean[3]; static String[] sel = new String[3]; public static void main(String[] args) { perm(0); } static void perm(int select_idx) { if(select_idx == fruits.length) { S..
우선순위 큐
1. Comparable, Comparator를 이용한 오름차순 compareTo를 구현 함으로 r변수를 기준으로 오름차순 정렬한다. Comparator를 구현한 다음, 정렬을 할때 객체를 같이 넘긴다. 내림차순은 o2.r - this.r 같이 순서만 바꿔주면 된다. import java.util.Arrays; import java.util.Comparator; public class 정렬 { static class Pair implements Comparable { int r, c; public Pair(int r, int c) { this.r = r; this.c = c; } @Override public int compareTo(Pair o) { //r기준 오름차순 정렬하고 싶음 return thi..
비트연산자
1. 비트연산자 1) & : 비트가 둘다 1인 경우만 결과가 1 나온다. 2) | : 비트가 하나라도 1인 경우 결과가 1 나온다 3) 1