문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. 풀이 이문제의 핵심은 부모가 표시되지않은 2개의 연결 노드를 어떻게 표현할 것인가 다. 처음에 arr[N][N] 도 생각해서 표시를 해볼까 했지만 N의 최대값이 10만이기에 메모리 초과가 난다. 따라서 이중 배열리스트를 이용하여 두개의 값 연결을 표현해봤다. 이후 BFS를 통해 자식 노드를 찾고 찾은 자식노드의 부모를 앞선 값으로 입력하도록 ..
문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 풀이 뒤에 수부터 반복문을 한번돈다. 각 반복문안에서 i번 앞에 있는 수를 기준으로 반복을 도는데 이때 i보다 작은 값일 경우 기존 값이랑 i번의 cnt+1 한 값이랑 비교하여 큰값을 대입해준다 = ..
package 클래스의 묶음, 클래스를 구분짓는 폴더 개념으로 생각하면 좋을 것 같다 클래스를 패키지로 구분짓는 이유는 이 체계를 유지함으로써 다른 개발자가 개발한 라이브러리의 클래스와 이름 충돌을 피할 수 있다 jdk내부를 살펴서 클래스를 찾을려했지만 아쉽게도 이제는 jdk- jre - lib - rt 구성으로 되어있는데 이때 rt는 Java Runtime Environment이다. rt에서 필요한 패키지를 호출하는 식으로 이루어져있다 (ex. 사용자가 java.util패키지를 호출하면 JVM이 rt.jar 내부에서 해당 피키지를 찾는다) 패키지는 규칙이 있다 패키지 이름과 위치한 폴더의 이름이 같아야 한다 패키지 이름을 java로 시작하면 안된다 모든 클레스에는 정의된 클래스 이름과 패키지 이름 이 ..
이미지를 저장 위치에 대한 고민 프로젝트를 하는 와중에 프로필 이미지 API 구현부분을 맡게 되었다. 이미지 업로드와 저장 관련해서 어디에 해야할지, 이미지를 DB에 저장하는게 맞는건지 외부 server에 저장해야하는건지 조차도 모르는 상태로 시작했다. AWS도 생각을 해보았지만 아직까지 배포 계획이 없는 프로젝트에서 금액부담은 그러했다. 따라서 외부 클라우드 서비스를 찾아보다가 구글 드라이브를 통해 저장을 하기로 마음먹었다. 이미지 업로드 방식의 큰 틀 이미지 업로드부터 url반환까지 과정 1. 프론트엔드에서 이미지 업로드: Node.js를 통해 프론트엔드에서 이미지를 선택하고 업로드한다. 이때 이미지는 URL 형태로 서버로 전송된다. 2. Spring Boot REST API: 스프링부트에서 1번에서..
에러메시지아래와 같이 세팅하고 실행을 했다postman을 통해 이미지 파일을 보내는 과정에서 이런 에러 메시지가 떴다. - Couldn't upload file Make sure that Postman can read files inside the working directory.아래 오류는 보통 작업 디렉토리로 폴더를 설정하지 않는 경우에 생긴다. 해결법- 세팅에 들어가 폴더 지정을 해줘야 한다.상단에 세팅버튼을 눌러주고 Settings - General 로 들어가고 목록에 보면 Working directory가 있을거다.이때 Working directory를 현재 쓰고자 하는 사진이 있는 폴더로 설정해주면 된다. 이후 다시 실행해보면 제대로 작동하는 것을 볼 수있다.
문제 다솜이는 유료 고속도로를 가지고 있다. 다솜이는 현재 고속도로에 휴게소를 N개 가지고 있는데, 휴게소의 위치는 고속도로의 시작으로부터 얼만큼 떨어져 있는지로 주어진다. 다솜이는 지금 휴게소를 M개 더 세우려고 한다. 다솜이는 이미 휴게소가 있는 곳에 휴게소를 또 세울 수 없고, 고속도로의 끝에도 휴게소를 세울 수 없다. 휴게소는 정수 위치에만 세울 수 있다. 다솜이는 이 고속도로를 이용할 때, 모든 휴게소를 방문한다. 다솜이는 휴게소를 M개 더 지어서 휴게소가 없는 구간의 길이의 최댓값을 최소로 하려고 한다. (반드시 M개를 모두 지어야 한다.) 예를 들어, 고속도로의 길이가 1000이고, 현재 휴게소가 {200, 701, 800}에 있고, 휴게소를 1개 더 세우려고 한다고 해보자. 일단, 지금 이..
상속 상속 정의 상속이란, 기존의 클래스를 재사용하여 새로운 클래스를 작성하는 것이다. 상속을 통해서 적은 양의 코드로 새로운 코드를 작성하고 코드를 공통적으로 관리할 수 있어 생산성과 유지 보수에 크게 기여한다 상속 받기 구현방법은 키어드 ‘extends’와 함께 써주기만 하면 된다 class Parent{ int age; } class Child extends Parent{ //부모 클래스를 상속받는 자식 클래스 } ※생성자와 초기화 블럭은 상속되지 않는다. 멤버만 상속된다. 가지 알아두어야할점은 초기화 블럭을 상속안받기는 하지만 하위 클래스 생성시 상위클래스의 블럭과 생성자가 호출되기는 한다. 단일 상속 C++에서는 다중 상속을 허용하지만 자바에서는 하나의 조상클래스만을 상속받는 단일 상속만을 허용..
문제 수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.) 수강신청 대충한 게 찔리면, 선생님을 도와드리자! 입력 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) 출력 강의실의 개수를 출력하라. 풀이 n의 최대수가 20만이고 시간제한 1초이므로 시간복잡도 O(nlogn)또는 O(n)만에 풀어야 하는 문제이다. 각 강의실 시작시간과 도착시간에..
문제 민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다. 단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다. 예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다. N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. ..
문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 2의 31승-1보다..
