데일리썽

Javascript와 같은 동적 타이핑 언어와는 다르게

Java는 변수 선언 시 타입 명시해줘야 함

lombok에서 제공하는 키워드 val var

val

// final List<String> strs = new ArrayList<>();
val strs = new ArrayList<>();

var

val에서 final 제거된 것

1. 이진 탐색 (Binary Search)

탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법

2. 분할 정복 알고리즘과 이진 탐색

분할 정복 알고리즘 (Divide and Conquer)

• Divide : 문제를 하나 또는 둘 이상으로 나눈다.
• Conquer : 나눠진 문제가 충분히 작고, 해결이 가능하다면 해결하고, 그렇지 않으면 다시 나눈다.

이진 탐색

• Divide : 리스트를 두 개의 서브 리스트로 나눈다.
• Conquer :
  • 검색할 숫자 (search) > 중간값 이면 뒷 부분의 서브 리스트에서 검색할 숫자를 찾는다.
  • 검색할 숫자 (search) < 중간값 이면 앞 부분의 서브 리스트에서 검색할 숫자를 찾는다.

3. 구현

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

@Slf4j
public class BinarySearch {
    public static Boolean binarySearch(List<Integer> dataList, Integer search) {
        log.error("________________ = {}", dataList);

        if (dataList.size() == 1 && search == dataList.get(0)) {
            return true;
        }

        if (dataList.size() == 1 && search != dataList.get(0)) {
            return false;
        }

        if (dataList.size() == 0) {
            return false;
        }

        Integer medium = dataList.size() / 2;

        if (search == dataList.get(medium)) {
            return true;
        } else {
            if (search > dataList.get(medium)) {
                return binarySearch(dataList.subList(medium, dataList.size()), search);
            } else {
                return binarySearch(dataList.subList(0, medium), search);
            }
        }
    }

    public static void main(String[] args) throws Exception {
        Random rand = new Random();
        List<Integer> dataList = new ArrayList<>();
        for (int i = 0; i < 11; i++) {
            dataList.add(rand.nextInt(11));
        }

        Collections.sort(dataList);

        log.error("________________ = {}", binarySearch(dataList, 10));
    }
}

4. 분석

시간 복잡도는 O(logn)

문제:

ArrayList를 for 문으로 반복하며 add 하는 와중에

마지막 객체가 전체 리스트를 덮어쓰기 하는 현상이 발생했습니다.

원인:

만든 객체 클래스에서 변수가 static 으로 선언되었던 것

해결:

static 빼면 됩니다.!

static 변수는 클래스 변수로 객체를 생성하지 않고도 접근 가능

메모리에 고정되어 할당되므로 여러 주소값으로 주어져도 변수의 값은 변하지 않습니다.

예를 들어

게시물의 좋아요 수를 구한다고 가정했을 때

import java.util.*;

public class PostLike {
    public static class Post {
        private static Integer likeCnt1;
        private Integer likeCnt2;

        public Post(Integer likeCnt1, Integer likeCnt2) {
            this.likeCnt1 = likeCnt1;
            this.likeCnt2 = likeCnt2;
        }

        public Integer getLikeCnt1() {
            return this.likeCnt1;
        }

        public Integer getLikeCnt2() {
            return this.likeCnt2;
        }
    }

    public static void main(String[] args) {
        List<Post> postList = new ArrayList<>();

        for (int i = 0; i < 3; i++) {
            postList.add(new Post(i, i));
        }

        for (Post post : postList) {
            System.out.println("POST Like COUT 1 : " + post.getLikeCnt1());
            System.out.println("POST Like COUT 2 : " + post.getLikeCnt2());
            System.out.println();
        }
    }
}

출력

POST Like COUT 1 : 2
POST Like COUT 2 : 0

POST Like COUT 1 : 2
POST Like COUT 2 : 1

POST Like COUT 1 : 2
POST Like COUT 2 : 2

static으로 선언된 likeCnt1은 값이 메모리에 씌어질시 프로그램이 종료될 때까지 메모리의 값이 유지되기 때문에

마지막에 씌어진 2 라는 값이 나오게 됩니다.

클래스에서 변수의 값을 공유하고 싶을 때 static 변수를 사용합시다.

문제 제목 : DFS와 BFS

난이도 : 하

문제 유형 : DFS, BFS

추천 풀이 시간 : 30분 (못하면 2배 60분)

https://www.acmicpc.net/problem/1260

import java.util.*;

public class Main {
    public static Integer n, m, v;
    public static ArrayList<ArrayList<Integer>> adjList = new ArrayList<>();
    public static boolean[] visited = new boolean[1001];

    public static void addEdge(int n, int m) {
        adjList.get(n).add(m);
    }

    public static void dfs(int node) {
        if (visited[node]) return;

        visited[node] = true;
        System.out.print(node + " ");

        for (int i = 0; i < adjList.get(node).size(); i++) {
            dfs(adjList.get(node).get(i));
        }
    }

    public static void bfs(int node) {
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(node);
        visited[node] = true;
        while (!queue.isEmpty()) {
            int now = queue.poll();
            System.out.print(now + " ");
            for (int i = 0; i < adjList.get(now).size(); i++) {
                int adjNode = adjList.get(now).get(i);
                if (!visited[adjNode]) {
                    queue.offer(adjNode);
                    visited[adjNode] = true;
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        v = sc.nextInt();

        for (int i = 0; i < n + 1; i++) {
            adjList.add(new ArrayList<Integer>());
        }

        for (int i = 0; i < m; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            addEdge(x, y);
            addEdge(y, x);
        }

        for (int i = 1; i < n + 1; i++) {
            Collections.sort(adjList.get(i));
        }

        dfs(v);
        System.out.println();
        visited = new boolean[1001];
        bfs(v);
    }
}

문제 제목 : 가장 높은 탑 쌓기

난이도 : 상

문제 유형 : 동적 프로그래밍(DP), LIS

추천 풀이 시간 : 50분 (못하면 2배 100분)

TIP : 가장 적은 경우의 수부터 계산을 해본 후 패턴을 찾아 점화식을 세우자@@

점화식이란? 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식 예를들어 dp[n + 2] = dp[n + 1] + dp[n + 2]

https://www.acmicpc.net/problem/2655

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    public static class Brick {
        public Integer index;
        public Integer area;
        public Integer height;
        public Integer weight;

        public Brick(Integer index, Integer area, Integer height, Integer weight) {
            this.index = index;
            this.area = area;
            this.height = height;
            this.weight = weight;
        }
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        Integer n = sc.nextInt();
        ArrayList<Brick> brickList = new ArrayList<Brick>();

        brickList.add(new Brick(0, 0, 0, 0));
        for (int i = 1; i < n + 1; i++) {
            brickList.add(new Brick(i, sc.nextInt(), sc.nextInt(), sc.nextInt()));
        }

        Collections.sort(brickList, (s1, s2) -> s1.weight - s2.weight);

        int[] dp = new int[n + 1];
        dp[0] = 0;

        for (int i = 1; i < n + 1; i++) {
            for (int j = 0; j < i; j++) {
                if (brickList.get(i).area > brickList.get(j).area) {
                    dp[i] = Math.max(dp[i], dp[j] + brickList.get(i).height);
                }
            }

        }

        Integer maxHeight = Arrays.stream(dp).max().getAsInt();

        int index = n;
        ArrayList<Integer> resultList = new ArrayList<>();
        while (index != 0) {
            if (maxHeight == dp[index]) {
                resultList.add(brickList.get(index).index);
                maxHeight -= brickList.get(index).height;
            }
            index -= 1;
        }

        System.out.println(resultList.size());
        for (int i = resultList.size() - 1; i >= 0; i--) {
            System.out.println(resultList.get(i));
        }
    }
}

문제 제목 : 음계

난이도 : 하

문제 유형 : 배열, 구현

추천 풀이 시간 : 15분 (못하면 2배 30분)

https://www.acmicpc.net/problem/2920

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] arr = new int[8];
        Scanner sc = new Scanner(System.in);
        
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
        }
        
        Boolean asc = true;
        Boolean desc = true;
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i] < arr[i + 1]) {
                desc = false;
            } else if (arr[i] > arr[i + 1]) {
                asc = false;
            }
        }
        
        if (asc) {
            System.out.println("ascending");
        } else if (desc) {
            System.out.println("descending");
        } else {
            System.out.println("mixed");
        }
    }
}

예를 들어 아래와 같은 URL일 경우

http://127.0.0.1:8080/contextpath/servlcetpath/index.jsp?seq=1&name=test

httpServletRequest.getRequestURL()

http://127.0.0.1:8080/contextpath/servlcetpath/index.jsp

httpServletRequest.getRequestURI()

/contextpath/servlcetpath/index.jsp?

httpServletRequest.getContextPath()

/contextpath

httpServletRequest.getServletPath()

/servlcetpath/index.jsp

httpServletRequest.getQueryString()

seq=1&name=test

httpServletRequest.getServerName()

127.0.0.1

httpServletRequest.getServerPort()

8080