분류 전체보기
-
BOJ) 좋은 친구 (3078 번)알고리즘/백준 2021. 2. 2. 18:37
좋은 친구 3078번: 좋은 친구 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다. www.acmicpc.net N명 학생들의 이름이 성적순으로 주어졌을 때, 좋은 친구가 몇 쌍이나 있는지 구하는 문제다. 좋은 친구는 등수의 차이가 K보다 작거나 같으면서 이름의 길이가 같은 친구 라고 정의하고 있다. 또한, 이름의 길이는 2 ~ 20 사이이다. 풀이 먼저, 이름의 길이에 따라 학생을 저장할 배열 bestFriends와 Sliding Window를 도와줄 Queue를 초기화했다. 위의 배열에는 이름의 길이가 2 ~ 20까지인 학생들이 몇명인지 ..
-
BOJ) 파일 합치기 (11066 번)알고리즘/백준 2021. 2. 2. 18:22
파일 합치기 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net DP로 분류된 문제인데, 정답률에 비해 굉장히 어렵게 느껴졌다. 연속된 소설 파일들을 합치는데, 연속이 되도록 파일을 합쳐야한다. 즉, 인접한 두 파일만을 합칠 수 있을 때, 가장 최소 비용을 구하는 문제다. 이 문제는 풀지 못했다. 정말 모르겠어서 다른 분들의 풀이를 참고해서 블로그를 포스팅한다. 참고한 링크는 하단에 걸어두었다. dp[i][j]는 i부터 j까지 합쳐지는데 최솟값을 저장한다. ( i ~ j 장 까지 합치는데 드는 최소 비용)..
-
Spring IoC/DIJava & Spring/기본 개념 정리 2021. 1. 30. 00:11
Spring IoC/DI 컨테이너 컨테이너 인스턴스의 생명주기를 관리 생성된 인스턴스에게 추가 기능을 제공 ex ) WAS의 Servlet 컨테이너 IoC(Inversion of Control) 제어의 역전 컨테이너가 개발자(코드) 대신 오브젝트의 제어권을 가지고 있어서 제어의 역전이라함 ex) 서블릿 클래스는 개발자가 만들지만, 서블릿을 메소드에 맞게 호출하는 것은 WAS DI(Dependency Injection) 의존성 주입 클래스 사이의 의존 관계를 Bean 설정 정보를 바탕으로 컨테이너가 자동으로 연결 어노테이션을 통해 사용 코드 예시 // 미적용 사례 class 엔진 { } class 자동차 { 엔진 v5 = new 엔진(); } // 적용 사례 @Component class 엔진 { } @C..
-
Array DequeCS 지식/자료구조 2021. 1. 29. 17:37
Array Deque AbstractCollection 클래스와 Deque, Cloneable, Serializable 인터페이스를 상속받는 클래스 특징 사이즈 제한이 없다. ( -> 입력받는 크기에 따라 resize 된다.) 외부 동기화가 없는 상태에서, 멀티 쓰레드에서 동시 엑세스가 안된다. == Thread Safe를 보장하지 않는다.) 요소로 null을 저장할 수 없다. Stack과 LinkedList보다 빠른 속도 Thread-safe 멀티 스레드 프로그래밍에서 일반적으로 어떤 메소드나 변수, 또는 객체가 여러 스레드로부터 동시에 접근이 이루어져도 프로그램 실행에 문제 없음 하나의 메소드가 한 스레드로부터 호출되어 실행 중일 때, 다른 스레드가 해당 메소드를 호출해서 동시에 함께 실행해도 각 스..
-
BOJ) 문자열 폭발 (9935 번)알고리즘/백준 2021. 1. 29. 17:22
문자열 폭발 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 이전에 시도했다가 실패했던 문제다. replaceAll이라는 좋은 메소드를 제공해주는데 굳이 구현을 해야할까? 싶어서 시도했었는데 역시나 시간초과였다. 자바는 문자열에 참 약하다...ㅠ 어떻게 풀어야할까 생각하다가 문제의 하단에 있는 알고리즘 분류를 봤는데 스택이 있었다. 그래서 스택을 이용해서 먼저 문제를 풀었다. 문자열을 돌면서 문자를 스택에 넣어주는데, 넣을 차례의 문자가 폭탄의 마지막 문자와 같은 경우 기존 스택에서 값을 꺼내면..
-
BOJ) 특정한 최단 경로 (1504 번)알고리즘/백준 2021. 1. 29. 17:14
특정한 최단 경로 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 다익스트라를 사용한다는 조건에 노드 두 개를 거쳐야하는 경로에 포함해야하는 문제다. 처음에는, 기본적인 다익스트라로 경로를 이동하면서 입력받은 두 노드를 거쳤는지 정보도 함께 포함했었다. 하지만, 틀린 것을 확인하고 두 경로 모두 거쳐야하는 조건을 제대로 파악하기 어렵다고 생각했다.그래서 경로가 두개만 주어지기 때문에, 해당 경로를 거치는 경우의 수를 다익스트라로 표현하면 된다고 생각했다. 풀이 1번..
-
BOJ) 트리 (1068 번)알고리즘/백준 2021. 1. 29. 17:08
트리 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 풀이 트리의 정보가 주어지고 특정 노드를 제거할 때, 리프노드가 몇 개 인지 찾는 문제다. 먼저, 트리의 각 노드는 하나의 부모를 가지고 있기 때문에 find-union을 사용해야겠다고 생각했다. 이전 find-union과 다른 점은 이미 부모에 대한 정보가 주어졌기 때문에, find할 때 더 상위 부모로 값을 최신화하지 않았다는 것이다. (최신화를 하게되면 루트 노드로 이어지기 때문에, 특정 노드를 제거했을 때, 자식노드를 제거할 수 없음) 다음으로..
-
BOJ) 트리의 지름 (1167 번)알고리즘/백준 2021. 1. 29. 16:56
트리의 지름 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2≤V≤100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. (정점 번호는 1부터 V까지 www.acmicpc.net 이전에 포스팅했던 트리의 지름과 조금 다르게 풀었다. 먼저, 트리기 때문에 어떤 지점에서 시작해도 특정 지점까지 모두 도달할 수 있다는 특징이 있다. 이 말인 즉, 가장 멀리있는 한 특정 지점을 찾을 수 있다는 말이 된다. 위의 조건에 따라, 1에서 가장 먼 vertex를 찾아주었다. 이후, 해당 vertex에서 가장 먼 거리에 있는 지점을 찾으며 최댓값을 갱신해주었다. (만약, 1 -> 찾은 지점이 가장 먼 거리라면, 찾은 지점 -> 1..