개발노동자

문제 세준이는 학교에서 집으로 가려고 한다. 도시의 크기는 무한대이고, 도시의 세로 도로는 모든 정수 x좌표마다 있고, 가로 도로는 모든 정수 y좌표마다 있다. 세준이는 현재 (0,0)에 있다. 그리고 (X,Y)에 위치한 집으로 가려고 한다. 세준이가 걸을 수 있는 방법은 두가지 인데. 하나는 도로를 따라서 가로나 세로로 한 블록 움직여서 이번 사거리에서 저 사거리로 움직이는 방법이고, 블록을 대각선으로 가로지르는 방법이 있다. 세준이가 집으로 가는데 걸리는 최소 시간을 구하는 프로그램을 작성하시오 입력 첫째 줄에 집의 위치 X Y 와 걸어서 한 블록 가는데 걸리는 시간 W와 대각선으로 한 블록을 가로지르는 시간 S가 주어진다. X와 Y는 1,000,000,000보다 작거나 같은 음이 아닌 정수이고, W..

문제 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70, 50, 80, 50] 이고 구명보트의 무게 제한이 100Kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150 이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다. 구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다. 사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution을 작성해주세요 제한사항 배열에서 두 개..

문제 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어 숫자 9124에서 수 두개를 제거하면 19, 12, 14, 92, 94, 24를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요. 1. StringBuilder변수를 생성한다. 2. max, index 변수를 초기화시키고 생성한다. 여기서 for 루프는 이중으로 도는데 주어진 문자열 number의 길이 - k 만큼 for문을 먼저 돌고 내부 for..

문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 사용표를 만들려고 한다. 각 회의에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 긑나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 핵심코드 처음에 계속 시작시간을 기준으로 정렬을 시도하다가 답이 틀렸었다. 저번 강의실 배정과는 큰 차이가 있다. 이 문제는 한 회의실에서 겹치지 않는 회의의 개수를 파악하는 문제이다. 결국 한 회의실로 보고 풀어야 하는 문제다. 여기서 왜 끝나는 시간으로..

https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 어떤 나라에 N개의 도시가 있다. 이 도시 들은 일직선 도로 위에 있다. 편의상 일직선을 수평 방향으로 두자. 제일 왼쪽의 도시에서 제일 오른쪽의 도시로 자동차를 이용하여 이동하려고 한다. 인접한 두 도시 사이의 도로들은 서로 길이가 다를 수 있다. 도로 길이의 단위는 Km를 사용한다. 처음 출발할 때 자동차에는 기름이 없어서 주유소에서 기름을 넣고 출발하여야 한다. 기름통의 크기는..

해당 글은 제가 모르는 부분을 디버깅하며 찾아가는 과정이기에 설명에 부족한 부분이 있을 수 있습니다 문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10이하의 자연수이다. 입력 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정정의 번호 K가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수(u,v,w)가 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다. 테스..

문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세가지이다. - X가 3으로 나누어 떨어지면, 3으로 나눈다. - X가 2로 나누어 떨어지면, 2로 나눈다. - 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력 풀이 3으로 나누거나, 2로 나누거나, 1을 빼서 연산 횟수의 최솟값을 구하는 문제이다. 여기서 배열(arr- DP) 배열의 인덱스는 주어진 숫자를 뜻한다. 즉 arr[10] 이면 10을 만들 때 사용한 연산 횟수의 최솟값이다. 그래서 아래와 같은 3가지 경우가 나올 수 있다. 3으로 나누어 떨어진다 -> arr[N/3] 2로 나누어 떨어진다 -> arr[N/2] 1을 뺀다 -> arr[N-1] 그리고 어떤..

해당 문제는 위상정렬을 알고 풀어야 했던 문제이다. 위상정렬 어떤 일을 하는 순서를 찾는 알고리즘이다. -> 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것 위상정렬(Topological Sort)의 특징 -> 하나의 방향 그래프에는 여러 위상 정렬이 가능하다. (사이클 안됨) -> 위상 정렬의 과정에서 선택되는 정점의 순서를 위상 순서라 한다. -> 위상 정렬의 과정에서 그래프에 남아 있는 정점 중에 진입 차수가 0인 정점이 없다면, 위상 정렬 알고리즘은 중된되고 이러한 그래프로 표현된 문제는 실행이 블가능한 문제가 된다. 위상정렬(Topological Sort)의 진행 1. 진입차수(Indegree)가 0인 정점(자신에게 들어오는 간선의 수 0)을 선택 - ..

1. Graph - 그래프는 정점(Vertex) 또는 노드(Node)와 간선(Edge)로 표현하기 위해 사용한다. 2. Graph 관련 용어 - 노드(Node) 위치를 말한다. 정점(Vertex)라고도 한다. - 간선(Edge): 위치 간의 관계를 표시한 선으로 노드를 연결한 선이라고 보면된다. - 인접 정점(Adjacemt Vertex) : 간선으로 직접 연결된 정점(또는 노드) - 참고용어 -> 정점의 차수(Degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 -> 진입 차수(In-Degree): 방향 그래프에서 외부에서 오는 간선의 수 -> 진출차수(Out-Degree): 방향 그래프에서 외부로 향하는 간선의 수 -> 경로길이(Path Length):경로를 구성하기 위해 사용된 간선의 ..

- 인접한 요소를 정렬기준(오름차순, 내림차순)대로 교환한다. - 안정 정렬이다.(stable sort) => 정렬 후에도 같은 값들 끼리의 순서가 보장된다. - 제자리 정렬(in-place sort) => 데이터에 필요한 공간을 제외하고 추가적인 공간이 필요없음을 의미한다. - 정렬한 데이터의 개수가 적을때는 나쁘지 않은 속도를 보인다. 과정 1. 앞에서부터 현재 원소와 바로 다음의 원소를 비교한다. 2. 현재 원소가 다음 원소보다 크면 원소를 교환한다. 3. 다음 원소로 이동하여 해당 원소와 그 다음원소를 비교한다. JAVA 코드로 보면 만약 {3,5,2}가 주어질 경우 1번 반복 for(int index=0;index < 3 - 1;index++){ boolean swap = false; for(i..