[필수2]알고리즘 필수 코드암기
위상정렬, 플로이드, 다익스트라, 프림, 크루스칼, BFS, DFS, 순열, 조합, 부분집합, 이분탐색 등 기본적인 알고리즘 코드 암기 연습을 위해 작성
연습
BFS, DFS, 순열, 조합, 부분집합
public static void main(String[] args) {
// bfs(0, 0);
// perm(0);
// permDup(0);
// comb(0,1);
// combDup(0, 1);
// subset(0);
// topological();
// floyd();
// dijkstra();
// prim();
// kruskal();
// System.out.println(binarySearch(1, 4));
// System.out.println(lower_bound(1, 4));
// System.out.println(upper_bound(1, 4));
// print_ver1();
// print_ver2();
}
/**
* BFS : 너비순회
* 2차원 좌표상에 4방향 BFS 순회 구해보라. (중복방문 방지)
*/
static int[] dx = {0,1,0,-1}; //오,아,왼,위
static int[] dy = {1,0,-1,0}; //오,아,왼,위
static void bfs(int cx, int cy) {
}
static class Pair4 {
int x; int y;
public Pair4(int x, int y){
this.x=x;this.y=y;
}
}
/**
* DFS : 깊이순회
* 생략. -> 아래 순.조.부 를 DFS 재귀형태로 구했기 때문
*/
/**
* 순열 : "순서(자리)" 가 의미 있게 나열 -> visited 활용(백트래킹)
* 중복순열 : "+중복" -> visited 없이
*/
// 순열 nPm
static int N,M;
static boolean[] visited;
static int[] outArr;
static void perm(int depth) {
}
// 중복순열
static void permDup(int depth) {
}
/**
* 조합 : "순서(자리)" 가 의미 없음 -> idx+1 (visited 없이)
* 중복조합 : "+중복" -> idx
*/
// 조합 nCm
static void comb(int depth, int idx) {
}
// 중복조합
static void combDup(int depth, int idx) {
}
// 참고) 조합 또다른 방식
//comb(depth+1, idx+1); // 현재 선택 OK 다음 자리 이동
//comb(depth, idx+1); // 현재 선택 X
/**
* 부분집합 : aC0+aC1+...+aCa 즉, 조합과 유사 ("있다 or 없다") 경우의 수 -> visited의 T/F 에 재귀 2개
*/
static int A = 5;
static boolean[] visited2 = new boolean[A + 1];
static void subset(int depth) {
}
위상정렬, 플로이드, 다익스트라, 프림, 크루스칼
/**
* 위상정렬 : 주어진 순서대로 선후관계 위배X 정렬 -> 방향 그래프
* 반드시 기억 : indegree 0이 큐 삽입시점 -> 최외곽
*/
public static void topological(){
int[][] input = {{1, 3}, {2, 3}}; // output:1 2 3
//...
}
/**
* 플로이드 : 모든정점->모든정점 최단경로
* 반드시 기억 : 3중 for문(k부터) + new 인접행렬
[백준13418](https://www.acmicpc.net/problem/13418) 의 경우 "오르막길(최악)", "내리막길(최선)"을 각각 1, 0으로 임의로 입력받고,
임의로 입력받은 간선을 "오름차순, 내림차순"으로 따로 정렬후 MST를 각각 진행해서 최선, 최악 비용을 구해낼 수 있다.
*/
public static void floyd(){
int N=4; int M=8; int X=2; // N->X->N 경로의 최단거리 구한후 가장 오래걸리는 학생 비용 구하라
int[][] input = {{1,2,4},{1,3,2},{1,4,7},{2,1,1},{2,3,5},{3,1,2},{3,4,4},{4,2,3}};
//...
}
/**
* 다익스트라 : 1개정점->모든정점 최단경로
* 반드시 기억 : 우선순위 큐(도착점, 도착비용) + new 거리배열
* +++ 최단거리 배열과 현재 도착거리 다르면 PASS(예외)
*/
public static void dijkstra() {
int N=4; int M=8; int X=2; // N->X->N 경로의 최단거리 구한후 가장 오래걸리는 학생 비용 구하라
int[][] input = {{1,2,4},{1,3,2},{1,4,7},{2,1,1},{2,3,5},{3,1,2},{3,4,4},{4,2,3}};
//...
}
/**
* 프림 : MST -> 최소 비용 정점을 선택해 나가는 방식
* 반드시 기억 : 우선순위 큐 + cnt + visited (중복 방지 필수)
*/
public static void prim() {
// 최악경로 비용과 최선경로 비용의 차이를 구하라.
int N = 4;
int M = 5;
int[][] input = {{0, 1, 1}, {1, 2, 0}, {1, 4, 0}, {4, 2, 1}, {3, 4, 1}, {2, 3, 0}};
//...
}
/**
* 크루스칼 : MST -> 간선 가중치를 비내림차순 정렬 후 순서대로 선택하는 방식
* 반드시 기억 : 정렬 + Union find
*/
public static void kruskal() {
// 최악경로 비용과 최선경로 비용의 차이를 구하라.
int N = 4;
int M = 5;
int[][] input = {{0, 1, 1}, {1, 2, 0}, {1, 4, 0}, {4, 2, 1}, {3, 4, 1}, {2, 3, 0}};
//...
}
이분탐색
/**
* 이분탐색 -> 자바에서 제공하는 Arrays.binarySearch 가 존재하지만, lower_bound, upper_bound
* 경우에는 직접 구현해줘야 하므로 "직접 구현방식"을 기억해둘것
*/
static int n=5;
static int[] a = {1,2,2,2,3};
// 분할정복 -> index 활용방식
public static int binarySearch(int target, int len) {
int st = 0;
int en = len;
// ...
return -1; // 못찾음
}
public static int lower_bound(int target, int len) {
int st = 0;
int en = len;
// ...
return st;
}
public static int upper_bound(int target, int len) {
int st = 0;
int en = len;
// ...
return st;
}
/**
추가) 응용ver -> 백준2467 - 용액 -> 이해안되면 문제를 읽어볼것
* 기존 문제점 : lower_bound 는 target 못 찾으면 그 뒤의 값을 가져오는데 정작 필요한건 앞의 값일 수도 있다. (문제 특성상) 그렇다고 앞의 값을 가져오게 로직을 수정해도 그 뒤의 값이 또 필요할 수도 있다.
* 결론 : 따라서 이분탐색을 사용하되 내부 로직에는 두 값의 합(sum)에 따라 갱신해야 한다.
* st 가 커질수록 합이 커질거고, en 이 작아질수록 합이 작아지는걸 생각
* 따라서 sum < 0 과 sum > 0 과 sum == 0 때로 나눠 구현하자.
* 또한 기존 문제점에서 언급했듯이, 찾는값이 없을때 앞의 값이 클수도 뒤의 값이 클수도 있어서
* 찾는 과정에서 계속 outArr(정답값)도 갱신해야한다.
*/
for (int i = 0; i < N; i++) { // NlogN 복잡도
int st = i+1;
int en = N-1;
// ...
}
/**
추가) 응용ver -> 백준2473 - 세 용액 -> 이해안되면 문제를 읽어볼것
* 이전의 "용액" 문제와의 차이점은 mid 값을 사용하는게 아닌 st, en 값을 사용해서 3개 값을 찾는다.
* 그런데 mid 값을 사용하는게 아니다보니 이분탐색 이라기보단
* 그냥 "투포인터"로 보는게 맞는것 같다?
*/
for (int i = 0; i < N-2; i++) { // N-2 -> i, st, en 순서 인덱스 임으로
int st = i+1;
int en = N-1;
// ...
}
답안
BFS, DFS, 순열, 조합, 부분집합
/**
* BFS : 너비순회
* 2차원 좌표상에 4방향 BFS 순회 구해보라. (중복방문 방지)
*/
static int[] dx = {0,1,0,-1}; //오,아,왼,위
static int[] dy = {1,0,-1,0}; //오,아,왼,위
static void bfs(int cx, int cy) {
int N = 10; //크기 임의지정
int level=0; int width=0; // level, width 는 그냥 참고용으로 넣음
boolean[][] visited = new boolean[N + 1][N+1];
Queue<Pair4> qu = new ArrayDeque<>();
qu.offer(new Pair4(cx, cy));
visited[cx][cy] = true;
while (!qu.isEmpty()) {
int size = qu.size();
level++;
for (int s = 0; s < size; s++) {
width++;
Pair4 cur = qu.poll();
System.out.print(cur+"\t");
for (int i = 0; i < 4; i++) {
Pair4 nxt = new Pair4(cur.x + dx[i], cur.y + dy[i]);
if(nxt.x<0||nxt.y<0||nxt.x>=N||nxt.y>=N
||visited[nxt.x][nxt.y]) continue;
qu.offer(nxt);
visited[nxt.x][nxt.y] = true;
}
}
System.out.println();
}
}
static class Pair4 {
int x; int y;
public Pair4(int x, int y){
this.x=x;this.y=y;
}
}
@Override
public String toString() {
return "Pair4{" +
"x=" + x +
", y=" + y +
'}';
}
/**
* DFS : 깊이순회
* 생략. -> 아래 순.조.부 를 DFS 재귀형태로 구했기 때문
*/
/**
* 순열 : "순서(자리)" 가 의미 있게 나열 -> visited 활용(백트래킹)
* 중복순열 : "+중복" -> visited 없이
*/
// 순열 nPm
static int N=5, M=3;
static boolean[] visited = new boolean[N+1];
static int[] outArr = new int[M+1];
static void perm(int depth) {
//base condition
if (depth == M) {
System.out.println(Arrays.toString(outArr));
return;
}
//recursion
for (int i = 1; i <= N; i++) {
if(visited[i]) continue;
visited[i] = true;
outArr[depth] = i;
perm(depth + 1);
visited[i] = false; //backtracking
}
}
// 중복순열
static void permDup(int depth) {
//base condition
if (depth == M) {
System.out.println(Arrays.toString(outArr));
return;
}
//recursion
for (int i = 1; i <= N; i++) {
outArr[depth] = i;
permDup(depth + 1);
}
}
/**
* 조합 : "순서(자리)" 가 의미 없음 -> idx+1 (visited 없이)
* 중복조합 : "+중복" -> idx
*/
// 조합 nCm
static void comb(int depth, int idx) {
//base condition
if (depth == M) {
System.out.println(Arrays.toString(outArr));
return;
}
//recursion
for (int i = idx; i <= N; i++) {
outArr[depth] = i;
comb(depth + 1, i + 1);
}
}
// 중복조합
static void combDup(int depth, int idx) {
//base condition
if (depth == M) {
System.out.println(Arrays.toString(outArr));
return;
}
//recursion
for (int i = idx; i <= N; i++) {
outArr[depth] = i;
combDup(depth + 1, i);
}
}
// 참고) 조합 또다른 방식
//comb(depth+1, idx+1); // 현재 선택 OK 다음 자리 이동
//comb(depth, idx+1); // 현재 선택 X
/**
* 부분집합 : nC0+nC1+...+nCn 즉, 조합과 유사 ("있다 or 없다") 경우의 수 -> visited의 T/F 에 재귀 2개
*/
static void subset(int depth) {
//base condition
if (depth == A) {
for (int i = 0; i < A; i++) {
if(visited2[i]) continue;
System.out.print(i+" ");
}
System.out.println();
return;
}
//recursion
visited2[depth] = true;
subset(depth+1);
visited2[depth] = false;
subset(depth + 1);
}
위상정렬, 플로이드, 다익스트라, 프림, 크루스칼
/**
* 위상정렬 : 주어진 순서대로 선후관계 위배X 정렬 -> 방향 그래프
* 반드시 기억 : indegree 0이 큐 삽입시점 -> 최외곽
*/
public static void topological(){
int[][] input = {{1, 3}, {2, 3}}; // output:1 2 3
//...
int N = 4; // 1,2,3 까지 범위
int[] indegree = new int[N];
int[] outArr = new int[N]; //result
List<Integer>[] graph = new ArrayList[N];
for(int i=0; i<N; i++) graph[i] = new ArrayList<>();
for(int i=0; i<2; i++){
int parent = input[i][0];
int child = input[i][1];
graph[parent].add(child); // 방향 그래프
indegree[child]++;
}
Queue<Integer> qu = new ArrayDeque<>();
for(int i=1; i<N; i++){
if(indegree[i]==0) qu.offer(i);
}
int idx = 0;
while(!qu.isEmpty()){
int node = qu.poll();
outArr[idx++] = node; //result
for(int nxt : graph[node]){
indegree[nxt]--;
if(indegree[nxt]==0) qu.offer(nxt); // 큐 삽입시점
}
}
System.out.println(Arrays.toString(outArr));
}
/**
* 플로이드 : 모든정점->모든정점 최단경로
* 반드시 기억 : 3중 for문(k부터) + new 인접행렬
* output:10
*/
public static void floyd(){
int N=4; int M=8; int X=2; // N->X->N 경로의 최단거리 구한후 가장 오래걸리는 학생 비용 구하라
int[][] input = {{1,2,4},{1,3,2},{1,4,7},{2,1,1},{2,3,5},{3,1,2},{3,4,4},{4,2,3}};
//...
int[][] floyd = new int[N+1][N+1];
for(int i=1; i<=N; i++) Arrays.fill(floyd[i], Integer.MAX_VALUE/3); // 원소 더하다가 음수로 안넘어가기 위해 /3
for(int i=0; i<M; i++){ // 입력정점
int parent = input[i][0];
int child = input[i][1];
int time = input[i][2];
floyd[parent][child] = time;
}
for(int k=1; k<=N; k++){
for(int i=1; i<=N; i++){
for(int j=1; j<=N; j++){
floyd[i][j] = Math.min(floyd[i][j], floyd[i][k]+floyd[k][j]);
}
}
}
//debug
// for(int i=1; i<=N; i++){
// System.out.println(Arrays.toString(floyd[i]));
// }
int result = 0;
for(int i=1; i<=N; i++){
result = Math.max(result,floyd[i][X]+floyd[X][i]); // N->X->N 경로
}
System.out.println(result); //10
}
/**
* 다익스트라 : 1개정점->모든정점 최단경로
* 반드시 기억 : 우선순위 큐(도착점, 도착비용) + new 거리배열
* +++ 최단거리 배열과 현재 도착거리 다르면 PASS(예외)
* output:10
*/
public static void dijkstra() {
int N=4; int M=8; int X=2; // N->X->N 경로의 최단거리 구한후 가장 오래걸리는 학생 비용 구하라
int[][] input = {{1,2,4},{1,3,2},{1,4,7},{2,1,1},{2,3,5},{3,1,2},{3,4,4},{4,2,3}};
//...
List<Pair>[] graph = new ArrayList[N+1];
List<Pair>[] graphRev = new ArrayList[N+1];
for(int i=0; i<=N; i++) graph[i]=new ArrayList<>();
for(int i=0; i<=N; i++) graphRev[i]=new ArrayList<>();
PriorityQueue<Pair> pq1 = new PriorityQueue<>();
PriorityQueue<Pair> pq2 = new PriorityQueue<>();
int[] dist1 = new int[N+1];
int[] dist2 = new int[N+1];
Arrays.fill(dist1, Integer.MAX_VALUE);
Arrays.fill(dist2, Integer.MAX_VALUE);
for(int i=0; i<M; i++){ // 입력정점
int parent = input[i][0];
int child = input[i][1];
int time = input[i][2];
graph[parent].add(new Pair(child, time));
graphRev[child].add(new Pair(parent, time)); //역방향
}
//N->X (역방향!!) X->N 을 구하자
dist1[X] = 0; // 도착점 비용(시작)
pq1.offer(new Pair(X, dist1[X])); // 도착점, 도착비용
while(!pq1.isEmpty()){
Pair cur = pq1.poll();
if(dist1[cur.child] != cur.time) continue; // 최단거리 배열과 현재 도착거리 다르면 PASS(예외)
for(Pair nxt : graphRev[cur.child]) {
if(dist1[nxt.child] <= dist1[cur.child]+nxt.time) continue;
dist1[nxt.child] = dist1[cur.child]+nxt.time;
pq1.offer(new Pair(nxt.child, dist1[nxt.child]));
}
}
//X->N
dist2[X] = 0; // 도착점 비용(시작)
pq2.offer(new Pair(X, dist2[X])); // 도착점, 도착비용
while(!pq2.isEmpty()){
Pair cur = pq2.poll();
if(dist2[cur.child] != cur.time) continue; // 최단거리 배열과 현재 도착거리 다르면 PASS
for(Pair nxt : graph[cur.child]) {
if(dist2[nxt.child] <= dist2[cur.child]+nxt.time) continue;
dist2[nxt.child] = dist2[cur.child]+nxt.time;
pq2.offer(new Pair(nxt.child, dist2[nxt.child]));
}
}
int result = 0;
for(int i=1; i<=N; i++){
int sum = dist1[i]+dist2[i];
result = Math.max(result, sum);
}
System.out.println(result);
}
static class Pair implements Comparable<Pair> {
int child; int time;
public Pair(int child, int time){
this.child=child; this.time=time;
}
@Override
public int compareTo(Pair o1) {
return this.time-o1.time; //asc
}
}
/**
* 프림 : MST -> 최소 비용 정점을 선택해 나가는 방식
* 반드시 기억 : 우선순위 큐 + cnt + visited (중복 방지 필수)
* output:8 -> [백준13418](https://www.acmicpc.net/problem/13418)
debug -> outArr1, outArr2
[Pair2{child=0, cost=0}, Pair2{child=1, cost=1}, Pair2{child=2, cost=0}, Pair2{child=4, cost=0}, Pair2{child=3, cost=0}]
[Pair2{child=0, cost=0}, Pair2{child=1, cost=1}, Pair2{child=2, cost=0}, Pair2{child=4, cost=1}, Pair2{child=3, cost=1}]
* 피로도 : 오르막길 k^2, 내리막길은 피로도X
* 출발은 항상 입구(=0) 부터
*/
public static void prim() {
// 최악경로 비용과 최선경로 비용의 차이를 구하라.
int N = 4;
int M = 5;
int[][] input = {{0, 1, 1}, {1, 2, 0}, {1, 4, 0}, {4, 2, 1}, {3, 4, 1}, {2, 3, 0}};
//...
PriorityQueue<Pair2> pq1 = new PriorityQueue<>((o1, o2) -> {
Pair2 p1 = (Pair2)o1;
Pair2 p2 = (Pair2)o2;
return p1.cost-p2.cost; //asc -> 최악경로비용
});
PriorityQueue<Pair2> pq2 = new PriorityQueue<>((o1, o2) -> {
Pair2 p1 = (Pair2)o1;
Pair2 p2 = (Pair2)o2;
return p2.cost-p1.cost; //desc -> 최선경로비용
});
List<Pair2>[] graph = new ArrayList[N+1];
for(int i=0; i<=N; i++) graph[i]=new ArrayList<>();
Pair2[] outArr1 = new Pair2[N+1];
Pair2[] outArr2 = new Pair2[N+1];
for(int i=0; i<M+1; i++){ // 입력정점
int parent = input[i][0];
int child = input[i][1];
int cost = input[i][2];
graph[parent].add(new Pair2(child, cost));
graph[child].add(new Pair2(parent, cost)); //양방향
}
//1.최선경로비용
boolean[] visited = new boolean[N+1];
pq1.offer(new Pair2(0, 0)); // 입구(=0)부터 시작이고 비용도 0으로 봐야한다.
int idx=0;
// visited 방문처리를 "큐 삽입시점" 아니라 "큐 poll 시점" 에 하기 때문에,
// 큐에는 중복으로 또 같은 값이 삽입되는 경우가 생긴다.
// 따라서 !pq.isEmpty() 가 아닌 cnt <= N 조건문을 사용하여 "시간을 최적화" 한다.
while (cnt <= N) {
Pair2 cur = pq1.poll();
if(visited[cur.child]) continue; // 이미 MST 선택되었나 방문체크는 필수
visited[cur.child]=true; //방문시점 -> MST 선택 시점
outArr1[idx++] = cur;
for(Pair2 nxt : graph[cur.child]) {
if(visited[nxt.child]) continue; // 이부분 없어도 잘 동작하지만 조금이라도 "시간을 최적화" 위함
pq1.offer(nxt); //큐 삽입시점
}
}
int result1=0;
for(int i=1; i<idx; i++){ // 입구 이후부터니까 i=1 부터
if(outArr1[i].cost == 1) continue; // 1은 내리막길 -> PASS
result1 += 1; // 오르막길 개수 추가
}
//2.최악경로비용
visited = new boolean[N+1];
pq2.offer(new Pair2(0, 0)); // 0번 정점부터 시작(cost:0으로써 임의의 시작점일뿐)
idx=0;
while (cnt <= N) {
Pair2 cur = pq2.poll();
if(visited[cur.child]) continue;
visited[cur.child]=true;
outArr2[idx++] = cur;
for(Pair2 nxt : graph[cur.child]) {
if(visited[nxt.child]) continue;
pq2.offer(nxt);
}
}
int result2=0;
for(int i=1; i<idx; i++){
if(outArr2[i].cost == 1) continue; // 1은 내리막길
result2 += 1;
}
System.out.println((int)(Math.pow(result1,2)-Math.pow(result2,2))); //8
}
static class Pair2 {
int child; int cost;
public Pair2(int child, int cost){
this.child=child; this.cost=cost;
}
}
/**
* 크루스칼 : MST -> 간선 가중치를 비내림차순 정렬 후 순서대로 선택하는 방식
* 반드시 기억 : 정렬 + Union find
* output:8
*/
public static void kruskal() {
// 최악경로 비용과 최선경로 비용의 차이를 구하라.
int N = 4;
int M = 5;
int[][] input = {{0, 1, 1}, {1, 2, 0}, {1, 4, 0}, {4, 2, 1}, {3, 4, 1}, {2, 3, 0}};
//...
edges = new Pair3[M + 1]; // M+1 크기
parent = new int[N + 1];
outArr1 = new Pair3[N + 1];
outArr2 = new Pair3[N + 1];
for (int i = 0; i < M + 1; i++) {
int n1 = input[i][0];
int n2 = input[i][1];
int cost = input[i][2];
edges[i] = new Pair3(n1, n2, cost);
}
//1.최악경로비용
// 에지 정렬부터
Arrays.sort(edges, 0, M+1, (o1, o2) -> Integer.compare(o1.cost, o2.cost)); //asc
Arrays.fill(parent, -1);
int idx = 0;
for (Pair edge : edges) {
if(isUnion(edge.n1, edge.n2)) continue; // 집합이면 PASS
outArr1[idx++] = edge;
}
//2.최선경로비용
Arrays.sort(edges, 0, M+1, (o1, o2) -> Integer.compare(o2.cost, o1.cost)); //desc
Arrays.fill(parent, -1);
idx = 0;
for (Pair edge : edges) {
if(isUnion(edge.n1, edge.n2)) continue; // 집합이면 PASS
outArr2[idx++] = edge;
}
//output
int result1=0;
for(int i=0; i<idx; i++){ // 입구 이후부터니까 i=1 부터
if(outArr1[i].cost == 1) continue; // 1은 내리막길 -> PASS
result1 += 1; // 오르막길 개수 추가
}
int result2=0;
for(int i=0; i<idx; i++){
if(outArr2[i].cost == 1) continue; // 1은 내리막길
result2 += 1;
}
System.out.println((int)(Math.pow(result1,2)-Math.pow(result2,2))); //8
}
static boolean isUnion(int n1, int n2) {
n1 = find(n1); n2 = find(n2); // root 찾기
if(n1==n2) return true; // 합집합(부모 동일하므로)
if (parent[n1] > parent[n2]) { // n2 부모가 제일 자식이 많다면,
int temp = n1;
n1 = n2; n2 = temp;
} //swap
parent[n1] += parent[n2]; // 자식이 많은쪽에 merge -> 하나의 집합으로 합치려는 의도
parent[n2] = n1; // 부모기록
return false;
}
static int find(int x) {
if(parent[x] < 0) return x; // -1 은 초기값 (자기 자신이 부모)
return parent[x] = find(parent[x]); // root 까지 재귀
}
static class Pair3 {
int n1; int n2; int cost;
public Pair(int n1, int n2, int cost) {
this.n1=n1; this.n2=n2; this.cost=cost;
}
}
이분탐색
/**
* 이분탐색 -> 자바에서 제공하는 Arrays.binarySearch 가 존재하지만, lower_bound, upper_bound
* 경우에는 직접 구현해줘야 하므로 "직접 구현방식"을 기억해둘것
*/
static int n=5;
static int[] a = {1,2,2,2,3};
// 분할정복 -> index 활용방식
public static int binarySearch(int target, int len) { // len = n-1 이 들어올거임
int st = 0;
int en = len;
while(st <= en) { // 찾기위해 '=='까지 포함
int mid = (st+en)/2;
if(a[mid] < target) st = mid+1;
else if(a[mid] > target) en = mid-1;
else return mid; // 찾음
}
return -1; // 못찾음
}
public static int lower_bound(int target, int len) {
int st = 0;
int en = len;
while(st < en) {
int mid = (st+en)/2;
if(a[mid] < target) st = mid+1; // target 발견시 st는 그 첫 위치 유지됨
else en = mid; // (a[mid] >= target) -> en=mid 반복시 target 끝이 보장됨
}
return st; // 그림보면 알겠지만 결국 'st=mid=en' 이 되므로 en 리턴도 상관없을 거임
}
public static int upper_bound(int target, int len) {
int st = 0;
int en = len;
while(st < en) {
int mid = (st+en)/2;
if(a[mid] <= target) st = mid+1; // '초과 값 위치' 구하는게 목표니까 mid+1 한것
else en = mid; // (a[mid] > target)
}
return st;
}
/**
추가) 응용ver -> 백준2467 - 용액 -> 이해안되면 문제를 읽어볼것
* 기존 문제점 : lower_bound 는 target 못 찾으면 그 뒤의 값을 가져오는데 정작 필요한건 앞의 값일 수도 있다. (문제 특성상) 그렇다고 앞의 값을 가져오게 로직을 수정해도 그 뒤의 값이 또 필요할 수도 있다.
* 결론 : 따라서 이분탐색을 사용하되 내부 로직에는 두 값의 합(sum)에 따라 갱신해야 한다.
* st 가 커질수록 합이 커질거고, en 이 작아질수록 합이 작아지는걸 생각
* 따라서 sum < 0 과 sum > 0 과 sum == 0 때로 나눠 구현하자.
* 또한 기존 문제점에서 언급했듯이, 찾는값이 없을때 앞의 값이 클수도 뒤의 값이 클수도 있어서
* 찾는 과정에서 계속 outArr(정답값)도 갱신해야한다.
*/
for (int i = 0; i < N; i++) { // NlogN 복잡도
int st = i+1;
int en = N-1;
while (st <= en) {
int mid = (st+en)/2;
int temp = inArr[i] + inArr[mid];
if(sum >= Math.abs(temp)) {
sum = Math.abs(temp);
outArr[0] = inArr[i];
outArr[1] = inArr[mid];
}
if(temp < 0) st = mid+1;
else if(temp > 0) en = mid-1;
else break; // temp == 0 을 찾은것
}
}
/**
추가) 응용ver -> 백준2473 - 세 용액 -> 이해안되면 문제를 읽어볼것
* 이전의 "용액" 문제와의 차이점은 mid 값을 사용하는게 아닌 st, en 값을 사용해서 3개 값을 찾는다.
* 그런데 mid 값을 사용하는게 아니다보니 이분탐색 이라기보단
* 그냥 "투포인터"로 보는게 맞는것 같다?
*/
for (int i = 0; i < N-2; i++) { // N-2 -> i, st, en 순서 인덱스 임으로
int st = i+1;
int en = N-1;
while (st < en) {
long temp = inArr[i] + inArr[st] + inArr[en]; // i, st, en 순서 인덱스
if (sum > Math.abs(temp)) { // "크기" 를 비교하므로 절대값
sum = Math.abs(temp);
outArr[0] = inArr[i];
outArr[1] = inArr[st];
outArr[2] = inArr[en];
}
if(temp < 0) st++;
else if(temp > 0) en--;
else break; // temp==0
}
}
출력 예시
BFS, DFS, 순열, 조합, 부분집합
//BFS
x:0 y:0
x:0 y:1 x:1 y:0
x:0 y:2 x:1 y:1 x:2 y:0
x:0 y:3 x:1 y:2 x:2 y:1 x:3 y:0
...
x:7 y:9 x:8 y:8 x:9 y:7
x:8 y:9 x:9 y:8
x:9 y:9
//순열
[1, 2, 3, 0]
[1, 2, 4, 0]
[1, 2, 5, 0]
[1, 3, 2, 0]
[1, 3, 4, 0]
[1, 3, 5, 0]
[1, 4, 2, 0]
[1, 4, 3, 0]
[1, 4, 5, 0]
[1, 5, 2, 0]
[1, 5, 3, 0]
[1, 5, 4, 0]
[2, 1, 3, 0]
[2, 1, 4, 0]
[2, 1, 5, 0]
[2, 3, 1, 0]
[2, 3, 4, 0]
[2, 3, 5, 0]
...
[4, 5, 3, 0]
[5, 1, 2, 0]
[5, 1, 3, 0]
[5, 1, 4, 0]
[5, 2, 1, 0]
[5, 2, 3, 0]
[5, 2, 4, 0]
[5, 3, 1, 0]
[5, 3, 2, 0]
[5, 3, 4, 0]
[5, 4, 1, 0]
[5, 4, 2, 0]
[5, 4, 3, 0]
//중복순열
[1, 1, 1, 0]
[1, 1, 2, 0]
[1, 1, 3, 0]
[1, 1, 4, 0]
[1, 1, 5, 0]
[1, 2, 1, 0]
[1, 2, 2, 0]
[1, 2, 3, 0]
[1, 2, 4, 0]
[1, 2, 5, 0]
...
[5, 3, 5, 0]
[5, 4, 1, 0]
[5, 4, 2, 0]
[5, 4, 3, 0]
[5, 4, 4, 0]
[5, 4, 5, 0]
[5, 5, 1, 0]
[5, 5, 2, 0]
[5, 5, 3, 0]
[5, 5, 4, 0]
[5, 5, 5, 0]
//조합
[1, 2, 3, 0]
[1, 2, 4, 0]
[1, 2, 5, 0]
[1, 3, 4, 0]
[1, 3, 5, 0]
[1, 4, 5, 0]
[2, 3, 4, 0]
[2, 3, 5, 0]
[2, 4, 5, 0]
[3, 4, 5, 0]
//중복조합
[1, 1, 1, 0]
[1, 1, 2, 0]
[1, 1, 3, 0]
[1, 1, 4, 0]
[1, 1, 5, 0]
[1, 2, 2, 0]
[1, 2, 3, 0]
[1, 2, 4, 0]
[1, 2, 5, 0]
[1, 3, 3, 0]
[1, 3, 4, 0]
[1, 3, 5, 0]
[1, 4, 4, 0]
[1, 4, 5, 0]
[1, 5, 5, 0]
[2, 2, 2, 0]
[2, 2, 3, 0]
[2, 2, 4, 0]
[2, 2, 5, 0]
[2, 3, 3, 0]
...
[3, 5, 5, 0]
[4, 4, 4, 0]
[4, 4, 5, 0]
[4, 5, 5, 0]
[5, 5, 5, 0]
//부분집합
4
3
3 4
2
2 4
2 3
2 3 4
1
1 4
1 3
1 3 4
1 2
1 2 4
1 2 3
1 2 3 4
0
0 4
0 3
0 3 4
0 2
0 2 4
0 2 3
0 2 3 4
0 1
0 1 4
0 1 3
0 1 3 4
0 1 2
0 1 2 4
0 1 2 3
0 1 2 3 4
댓글남기기