개발노동자

문제 오늘도 서준이는 너비 우선 탐색 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자 N개의 정점과 M개의 간선으로 구성된 무방향 그래프가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비우선 탐색으로 노드를 방문할 경우 노드의 방문 순서를 출력하자 인접 정점은 내림차순으로 방문한다. 풀이 방법 -> 1번 인접 리스트로 주어진 간선들을 받아 생성 -> 2번 인접 리스트를 모두 내림차순으로 정렬한다. -> 3번 BFS 방식 그대로 적용하여 탐색을 시작한다. -> Queue에 시작점 담고 while에서 poll하고 poll한 값 for문 돌리는식으로 진행 -> 4번 진행 하기 전에 count 배열을 만들어 순서를 ..

문제 N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)가 주어진다. 정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다. 정점 R에서 시작하여 너비우선 탐색으로 만들어 지는 트리를 너비우선 탐색 트리라고 하자. 너비 우선 탐색 트리에 있는 모든 노드의 깊이(depth)를 출력하자. 시작 정점 R의 깊이는 0이고 방문 되지 않은 노드의 깊이는 01로 출력하자 문제에서 트리라는 표현을 이해 못해 계속 틀리고 억지로 맞췄는데 출력초과로 계속 틀렸다.... 결국 이 문제는 자식노드를 다 같은 depth로 보고 풀어야 한다. 그렇기 때문에 일반적으로 bfs를 표현할 때 시작 점부터 큐에 담고 하나씩 뽑으면서 while(!q.isEmpty())를 돌리며 큐를 하나씩 뽑아 f..

원래 기존 코드는 Querydsl을 사용하여 이런식으로 작성자와 Room에 연관된 Hotel에 writer 열을 현재 로그인한 사용자가 맞는지 체크하는 메소드를 만들어서 사용하려 했는데 이렇게 사용할 경우 컨트롤러에서는 쿼리가 두 번 생성되어 날라간다. 기존 자세히 보기로 필요한 select from where id =? 쿼리 하나와 작성자가 맞는지 체크하는 쿼리 이런식으로 날라간다. 쿼리 한 번으로 해결할 수 있을 거 같아 합쳐봤다. FETCH JOIN은 기본적으로 OneToMany 관계는 하나 초과해서 같이 못 부르지만 ManyToOne은 부를 수 있다. 여기서 RoomImage는 Room과 OneToMany이다. Hotel은 ManyToOne의 관계를 갖는다. 메소드를 동작시켜 본다면 left ou..

문제 서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까? 입력 첫째 줄에 자연수 S가 주어진다. (1 ≤ S ≤ 4,294,967,295) https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 일단 S의 범위가 크므로 long을 받아서 해야한다. 처음에 int로 했었는데 시간초과... 문제 풀이 - 1부터 주어진 숫자까지 for루프를 돌면서 num에 루프 인덱스를 계속 더해 나간다. 그러면 num은 점점 값이 커질 것이고 결국 주어진 값을 넘어갈 것이다. 주어진 값을 넘긴 순간 break를 걸어야 한다. - 여기에 문제 조건은..

문제 https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net 이 부분이 잘 이해가 안 갔는데 이 부분을 코드로 보면 사이클을 이런식으로 만들 수 있다. 이렇게 만들어진 사이클을 구해 출력하는데 여기서 테스트 케이스 숫자도 주어진다. 1. arr을 만들어 주어진 숫자를 배열에 넣는다. 2. visited 배열을 만들어 방문처리를 하는데(여기서 visited 인덱스가 그래프를 나타냄..

문제 총 N개의 시험장이 있고, 각가의 시험장마다 응시자들이 있다. i번 시험장에 있는 응시자의 수는 A명이다. 감독관은 총감독관과 부감독관으로 두 종류가 있다. 총감독관으,ㄴ 한 시험장에서 감시할 수 있는 응시자의 수가 B명이고, 부감독관은 한 시험장에서 감시할 수 있는 응시자의 수가 C명이다. 각각의 시험장에서 총감독관은 오직 1명만 있어야 하고,, 부감독관은 여러 명 있어도 된다. 각 시험장마다 응시생들을 모두 감시해야 한다. 이때 필요한 감독관 수의 최솟값을 구하는 프로그램을 작성하시오 풀이 처음 while문으로 전부 순회하며 푸니 당연하게 시간초과.. 순서 1. 총감독은 한명은 무조건 있어야 하고 그 이상은 존재할 수 없다. 결국 주어진 교실만큼 총감독이 들어감 2. 학생이 100명일 경우 총감..

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