본문 바로가기

분류 전체보기

 (83)
[백준] 19238번 - 스타트 택시 (java) Baekjoon 19238 - 스타트 택시 (클릭 시 이동) 문제 스타트링크가 "스타트 택시"라는 이름의 택시 사업을 시작했다. 스타트 택시는 특이하게도 손님을 도착지로 데려다줄 때마다 연료가 충전되고, 연료가 바닥나면 그 날의 업무가 끝난다. 택시 기사 최백준은 오늘 M명의 승객을 태우는 것이 목표이다. 백준이 활동할 영역은 N×N 크기의 격자로 나타낼 수 있고, 각 칸은 비어 있거나 벽이 놓여 있다. 택시가 빈칸에 있을 때, 상하좌우로 인접한 빈칸 중 하나로 이동할 수 있다. 알고리즘 경력이 많은 백준은 특정 위치로 이동할 때 항상 최단경로로만 이동한다. M명의 승객은 빈칸 중 하나에 서 있으며, 다른 빈칸 중 하나로 이동하려고 한다. 여러 승객이 같이 탑승하는 경우는 없다. 따라서 백준은 한 승객을..
[백준] 1967번 - 트리의 지름 (java) Baekjoon 1967 - 트리의 지름 (클릭 시 이동) 문제 트리(tree)는 사이클이 없는 무방향 그래프이다. 트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재하게 된다. 트리에서 어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것이다. 이럴 때 트리의 모든 노드들은 이 두 노드를 지름의 끝 점으로 하는 원 안에 들어가게 된다. 이런 두 노드 사이의 경로의 길이를 트리의 지름이라고 한다. 정확히 정의하자면 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이를 말한다. 입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해서 출력하는 프로그램을 작성하시오. 아래와 같은 트리가 주어진다면 트리의 지름은 45가 된다. 트리..
[백준] 15684 - 사다리 조작 (java) Baekjoon 15684 - 사다리 조작 (클릭 시 이동) 문제 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다. 초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다. 위의 그림에는 가로선이 총 5개 있다. 가로선은 위의 그림과 같이 인접한 두 세로선을 연결해야 하고, 가로선을 놓을 수 있는 위치를..
[JAVA] 문자열 클래스 String, StringBuffer, StringBuilder String : 불변 / 동기화X StringBuffer : 가변 / Synchronized 가능(Thread-safety) StringBuilder : 가변 / Synchronized 불가능 String 특징 new 연산을 통해 생성된 인스턴스의 메모리 공간은 변하지 않는다.(Immutable) Garbage Collector로 제거되어야 한다. 문자열 연산시 새로 객체를 만드는 Overhead가 발생한다. 객체가 불변하므로, Multi-Thread 환경에서 동기화를 신경 쓸 필요가 없다. String Class : 문자열 연산이 적고, 조회가 많은 멀티쓰레드 환경에서 사용하기 좋다. StringBuffer, StringBuilder 특징..
[JAVA] Wrapper Class 자바에는 기본 자료형(Primitive data type)이 있는데 그에 대한 클래스 표현인 Wrapper Class가 존재한다. 기본 타입 : int, long, float, double, boolean ... 래퍼 클래스 : Integer, Long, Float, Double, Boolean ... 박싱과 언박싱 박싱 : 기본 데이터 타입에 대응하는 wrapper클래스로 만드는 동작 int i = 10; Integer num = new Integer(i); // Boxing 언박싱 : Wrapper 클래스에서 기본 타입으로 변환 Integer num = new Integer(10); int i = num.intValue(); //unBoxing 오토 박싱 편의성을 위해 오토 박싱과 오토 언박싱이 제공..
[JAVA] Call by Value & Call by Reference Call by value & Call by reference Call by value 값에 의한 호출 함수가 호출될 때 메모리 공간 안에서는 함수를 위한 별도의 임시공간이 생성된다. (종료시 반환) Call by value 호출 방식은 함수 호출 시 전달되는 변수 값을 복사해서 함수 인자로 전달한다. 이 때 복사된 인자는 함수 안에서 지역적으로 사용되기 때문에 local value속성을 가진다. 따라서, 함수 안에서 인자 값이 변경되더라도, 외부 변수 값은 변경되지 않는다. Call by reference 참조에 의한 호출 함수 호출 시 인자로 전달되는 변수의 레퍼런스를 전달한다. 함수 안에서 인자 값이 변경되면, 인자로 전달된 객체의 값도 변경된다. 자바의 경우, 항상 Call by value로 값을 ..
[백준] 2573번 - 빙산 (java) Baekjoon 2573 - 빙산 (클릭 시 이동) 문제 지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다. 빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각 부분에 해당되는 칸에 있는 높이는 일년마다 그 칸에 동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다. 단, 각 칸에 저장된 높이는 0보다 더 줄어들지 않는다. 바닷물은 호수처럼 빙산에 둘러싸여 있을 수도 있다. 2차원 배열에서 동서남북 방향으로 붙어있는 칸들은 ..
[백준] 11437번 - LCA (java) Baekjoon 11437 - LCA (클릭 시 이동) 문제 N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다. 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 3 초 256 MB 12641 5564 3271 43.006% 입력 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정점 쌍이 주어진다. 출력 M개의 줄에 차례대로 입력받은 두 ..

티스토리툴바