개발노동자

문제 눈금의 간격이 1인 MxN크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 작사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다. 예를 들어 M=5,N=7인 모눈 종이 위에 과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 와 같이 3개의 분리된 영역으로 나누어지게 된다. M,N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그릭 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오 5 7 3 0 2 4 4 1 1 2 5 4 0 6 2 풀이 visited 배열을 생성해서 하려했는데 굳이 필요가 없을 거 같아 다시 지..

문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 NxN인 그리드의 각 칸에 R, G, B중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또 , 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다) 예를 들어, 그림이 아래와 같은 경우에 RRRBB GGBBB BBBRR BBRRR RRRRR 적록색양이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2, 파랑 1, 초록 1) 하지만, 적록색약인 사람은 구역을 3개 볼 수 있다 그림이 입력으로 주어졌..

문제 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사혀라고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연 수이다. 예를 들어, 다음은 N=5인 지역의 높이정보이다. 이제 위와 같은 지역에 많은 비가 내려서 높이가 4이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 표..

문제 루트 없는 트리가 주어진다. 이떄 트리의 루트를 1이라고 정했을 떄 각 노드의 부모를 구하는 프로그램을 작성하시오 7 1 6 6 3 3 5 4 1 2 4 4 7 풀이 주어진 노드들을 연결해보면 원을 막 뒤엉키게 되는데 루트를 1로 보면 이진트리로 볼 수 있다. 그렇게 보면 결국 주어진 값에서 루트 노드 1에 연결된 그래프는 4와 6이다. 이 두 값에 노드는 부모는 1인 걸 알 수 있다. 이 말을 보자마자 bfs로 풀면 금방 풀 수 있을 거 같았는데 dfs 로 한 번 도전해봤다. parent ,visited , graph 배열을 통해 값들을 받는데 핵심은 static void dfs(int index){ visited[index] = true; //1이 들어오면 1을 방문처리하고 그의 자식들을 탐색한..

문제 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 n명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 한다. 이긴 사람은 다음 라운드에 진출하고, 진 사람은 그 라운드에서 떨어진다. 만약 그 라운드의 참가자가 홀수명이라면, 마지막 번호를 가진 참가자는 다음 라운드로 자동 진출한다. 다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다. 이떄 번호를 매기는 순서는 처음 번호의 순서를 유지하면서 1번부터 매긴다. 이 말은 1번과 2번이 스타를해서 1번이 진출하고, 3번과 4번이 스타를 해서 4번이 진출했다면, 4번 다음 라운드에서 번호 2번을 배정받는다. 번호를 다시 배정 받은 후에 한 명만 남을 떄까지 라운드를 계..

문제 지민이는 세계에서 가장 유명한 사람이 누구인지 궁금해졌다. 가장 유명한 사람을 구하는 방법은 각 사람의 2-친구를 구하면 된다. 어떤 사람 A가 또 다른 사람 B의 2-친구가 되기 위해선, 두 사람이 친구이거나, A와 친구이고,B와 친구인 C가 존재해야 된다. 여기서 가장 유명한 사람은 2-친구의 수가 가장 많은 사람이다. 가장 유명한 사람의 2- 친구의 수를 출력하는 프로그램을 작성하시오 풀이 문제를 많이 읽어봤지만 이해를 못해 결국 답을 봤다. 플로이드 와샬을 통해 각 최단 경로를 구하고 2나 1을 찾아 최댓값을 구한다. 플로이드 와샬에서는 최단경로를 구하기 위해 for(int i = 1; i

문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오 한 정사각형과 가로,세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다. 1 1 0 2 2 0 1 1 0 3 2 1 1 1 1 1 1 5 4 1 0 1 0 0 1 0 0 0 0 1 0 1 0 1 1 0 0 1 0 5 4 1 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 1 5 5 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 풀이 bfs로 풀었는데 주의..

문제 등산가 김강산은 가족들과 함께 캠핑을 떠났다. 하지만 캠핑장에는 다음과 같은 경고문이 쓰여있었다. 캠핑장은 연속하는 20일 중 10일동안만 사용할 수 있습니다. 강산이는 이제 막 28일 휴가를 시작했다. 이번 휴가기간 동안 강산이는 캠핑장을 며칠동안 사용할 수 있을까? 강산이는 조금 더 일반화해서 문제를 풀려고 한다. 캠핑장을 연속하는 P일 중,L일동안만 사용할 수 있다. 강산이는 이제 막 V일 짜리 휴가를 시작했다. 강산이가 캠핑장을 최대 며칠동안 사용할 수 있을까 풀이 L 5 P 8 V 20 이다 처음에 그냥 20/8하고 해당 값 곱하기 L을 한다음 나머지를 더했는데 이러면 안되었던게 V%P 값이 L보다 클 수 있다. 그니깐 주어진 5값이 20을 8로 나눈 나머지 값보다 작을 수 있다는 소리다...

문제 괄호 문자열은 두 개의 괄호 기호인 ')'와 ')' 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 "()" 문자열은 기본 VPS라고 부른다. 만일 X가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 "(x)"도 VPS 된다. 그리고 두 VPS x와 y를 접합(concatenation)시킨 새로운 무낮열 xy도 VPS가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 입력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 ..

문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적있는 숫자 카드를 상근이가 몇개 가지고 있는지 구하는 프로그램을 작성하시오. 풀이 일단 처음 이진탐색으로 접근했는데 주어진 입력으로 풀었을 때는 답이 나왔는데 제출하고 나니 틀렸다. 처음 접근했던 방법은 List를 통해 주어진 10개에 입력을 받고 이진탐색으로 찾는 숫자카드를 먼저 하나 찾으면 true를 리턴하고 N-1 한 다음 찾은 그 값을 remove를 통해 제거했다. 그러면 10개였던 배열이 9개가 되면서 N도 그에 맞게 9가 된다. 그 다음 한 번 찾았을 경우 다시 이진탐색을 해서 탐색을 시도해서 값이 없다면 해당 숫자로는 탐색을 멈춘다. 그렇게 탐색횟수를 카운트하여..