CodeDrive

문제:

크기가 N인 수열 A=A1,A2,...,AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3,5,2,7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

입력:

첫째 줄에 수열 A의 크기 N (1<=N<=1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1,A2,...,AN(1<=Ai<=1,000,000)이 주어진다.

출력:

총 N개의 수 NGE(1), NGE(2),... ,NGE(N)을 공백으로 구분해 출력한다.

풀이방법:

for를 두 번 사용해서 문제를 풀 수 있지만 O(n^2) 시간복잡도로 인해서 시간초과가 발생한다. 따라서 효율적인 방법인 스택을 사용해야 한다.

이와 비슷한 문제들은 수열의 값들을 저장하면서 진행을 하지만, 이 문제는 독특하게 인덱스를 저장하면서 진행한다.

조건에 맞는 오큰수가 없다면 -1을 넣어주어야 하므로, 애초에 크기가 len(A)이고, 값이 -1인 answer 배열을 만들어 준다.

이후에는 배열을 한번 순회할 때, idx의 마지막(top)에 해당하는 값과 반복문의 인덱스값과 비교하고, 이 때, 반복문의 인덱스값이 크다면 idx의 top에 해당하는 값을 인덱스로 해서 answer의 값(answer[idx.pop()])을 반복문의 인덱스(i) 값(A[i])으로 바꿔주도록 한다. 그리고 이는 while로 반복된다.

while이 끝나면 지금 반복문 인덱스를 idx에 넣어준다.

www.acmicpc.net/problem/17298

문제:

윤영이는 3의 배수 마니아이다. 그는 모든 자연수를 3개의 3의 배수의 자연수로 분해하는 것을 취미로 가지고 있다. 문득 그는 자신에게 주어진 수를 3개의 3의 배수로 분리하는 경우의 수가 몇 개인지 궁금해졌다. 하지만 윤영이는 마지막 학기이기 때문에 이런 계산을 하기에는 너무 게을러졌다. 그래서 당신에게 이 계산을 부탁했다.

즉, 임의의 3의 배수 자연수 n이 주어졌을 때, 해당 수를 3의 배수의 자연수 3개로 분리하는 방법의 개수를 출력해라. 단, 분해한 수의 순서가 다르면 다른 방법으로 간주한다. 예를 들어 12 = 3+6+3과 12=3+3+6은 다른 방법이다.

입력:

임의의 3의 배수 자연수 n이 주어진다. (3<=n<=3000)

출력:

자연수 n을 분해하는 방법의 개수를 출력하라.

풀이방법:

고등학교 수학이 생각나는 문제다. 이 문제를 변수로 나타내면 x+y+z = n (x,y,z,n은 3의 배수) 와 같고, 이는 조합 문제와 동일하다.

1. 간결하게 표현하기 위해 모든 수가 3의 배수이므로 3으로 나눠준다. (x'+y'+z' = n//3, x',y',z'>=0)

2. 3의 배수의 자연수로 분해를 해야 하기 때문에 좌변에 3을 빼줌으로써 해결한다. (x''+y''+z'' = n//3-3, x''+y''+z''>=1), 이는 nHr을 계산하는 문제와 같아진다.(3Hn//3-3)

따라서 이를 계산하면 답을 구할 수 있다.

문제링크:

www.acmicpc.net/problem/16561

문제:

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력:

첫째 줄에 수의 개수 N(1<=N<=10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력:

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

풀이방법:

숫자가 10,000까지만 있다는 점에서 count를 하는 방식으로 정렬을 한다. 10,000 크기의 배열은 만든 뒤에 들어오는 숫자대로 해당하는 인덱스의 값을 늘려줬다. 이를 마친 뒤에 앞 인덱스부터 출력했다.

문제링크:

https://www.acmicpc.net/problem/10989

문제:

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1<=N<=1,000, 0<=M<=Nx(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1<=u,v<=N, u!=v) 같은 간선은 한 번만 주어진다.

출력:

첫째 줄에 연결 요소의 개수를 출력한다.

풀이방법:

인접리스트와 dfs를 사용해서 이 문제를 사용했다. N, M을 입력받은 뒤에 인접리스트 U를 초기화하고, visited 배열을 초기화 했다. 방문하지 않은 정점에 대해서만 dfs를 수행해서 연결 요소의 개수를 구했다. 

문제링크:

https://www.acmicpc.net/problem/11724

문제:

초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.

집합을 표현하는 프로그램을 작성하시오.

입력:

첫째 줄에 n(1<=n<=1,000,000), m(1<=m<=100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과 b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산이다. a와 b는 n 이하의 자연수 또는 0이며 같을 수도 있다.

출력:

1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no를 출력해도 된다.)

풀이방법:

 단순해 보이지만 정답 비율이 낮았기에 효율적으로 풀어야 하는 것이 중요할 것 같았다. 그리고 알아보니 이 문제는 Union-Find를 사용해서 풀어야 하는 문제였다.

 우선 parents 초기화 함으로써 해당 인덱스의 값이 각 집합을 이루고 있다고 가정했다. union은 합치는 명령을, find는 해당 집합에서 parent를 찾도록 하는 연산으로 정의했다.

이 문제는 다음과 같은 기준으로 해결된다.

1. 초기에는 각 집합이 하나의 값으로 집합을 이루고 있고, 이를 각각 parent라고 정의한다.

2. union 연산이 0 a b와 같이 들어온다면 b의 parent를 a의 parent에 연결한다.(혹은 가리킨다.)

3. find는 parents에서 인덱스를 조회했을 때, 입력 값과 같다면 parent이기 때문에 이를 바로 return해주고(이는 처음 parents의 정의이다.), 그렇지 않다면 find를 재귀적으로 사용해서 입력의 값의 parent를 찾도록 한다.

4. check는 1 a b와 같이 들어왔을 때, a와 b를 각각 find 연산을 사용해서 parent가 같은지 확인한다. (같으면 True, 다르면 Faslse)

문제링크:

https://www.acmicpc.net/problem/1717

문제:

인체에 치명적인 바이러스르 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 NxM인 직사각형으로 나타낼 수 있으며, 직사각형은 1x1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.

바이러스가 퍼진 뒤의 모습은 아래와 같아진다.

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3<=N,M<=8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

출력:

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

풀이방법:

벽을 3개 세우는 방법을 한 눈에 찾는 것은 어렵기 때문에 가능한 모든 경우의 수에 대해 벽을 세워보면서 안전 영역 크기가 최대인 경우를 찾아야 한다. 

input을 모두 받은 뒤에 지도를 한번 탐색해서 0인 점인 빈 칸과, 2인 바이러스가 담겨 있는 배열을 만든다. 그리고 itertools의 combinations를 사용해서 지도에서 빈 칸을 3개를 고르는 모든 경우의 수를 구하고, 0인 점의 배열의 길이를 safeArea라고 정의한다.(안전 영역 계산을 빠르게 하기 위함이다.)

combinations의 각 경우에 대해서 bfs(spreadVirus)를 수행한다. 처음 바이러스가 담겨 있는 배열을 queue로 생각하며 이를 하나씩 빼면서 상하좌우로 이동하는 것으로 생각하며, 바이러스가 이동했다면 이를 다시 배열에 담아서 이 배열의 크기가 0이 될 때까지 반복하도록 했다. 그리고 이 때마다 spreadCount를 하나씩 증가하면서 처음 0인 칸에서 얼마나 바이러스가 펴졌는지 체크하도록 한다.

그리고 최종적으로는 safeArea-spreadCount-3으로 안전영역의 크기를 구한다.(-3은 0에다가 벽을 3개 세웠기 때문이다.)

이렇게 모든 경우의 수에 대해 탐색을 하면서 maxVal을 업데이트해 최댓값을 구하도록 한다.

문제링크:

https://www.acmicpc.net/problem/14502

문제:

도영이는 짜파구리 요리사로 명성을 날렸었다. 이번에는 이전에 없었던 새로운 요리에 도전을 해보려고 한다.

지금 도영이의 앞에는 재료가 N개 있다. 도영이의 각 재료의 신맛 S와 쓴맛 B를 알고 있다. 여러 재료를 이용해서 요리할 때, 그 음식의 신맛은 사용한 재료의 신맛의 곱이고, 쓴맛은 합이다.

시거나 쓴 음식을 좋아하는 사람은 많지 않다. 도영이의 재료를 적절히 섞어서 요리의 신맛과 쓴맛의 차이를 작게 만들려고 한다. 또, 물을 요리라고 할 수는 없기 때문에, 재료는 적어도 하나 사용해야 한다.

재료의 신맛과 쓴맛이 주어졌을 때, 신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 프로그램을 작성하시오.

입력:

첫째 줄에 재료의 개수 N(1<=N<=10)이 주어진다. 다음 N개 줄에는 그 재료의 신맛과 쓴맛이 공백으로 구분되어 주어진다. 모든 재료를 사용해서 요리를 만들었을 때, 그 요리의 신맛과 쓴맛은 모두 1,000,000,000보다 작은 양의 정수이다.

출력:

첫째 줄에 신맛과 쓴맛의 차이가 가장 작은 요리의 차이를 출력한다.

풀이방법:

각 재료에 따라서 넣고 빼고 하는 작업을 재귀로 구현을 했다. mix라는 함수를 재귀적으로 호출하고, sour와 bitter의 배열의 크기를 줄여나가면서 재귀를 진행한다. 이 배열의 길이가 0이 될 때까지 반복하며, 결과값을 global 변수인 answer에 모두 담고, min 값을 출력한다.

https://www.acmicpc.net/problem/2961

문제:

풀이방법:

생각보다 시간에 대한 조건이 넉넉한 편이기 때문에 모든 경우의 수를 확인하면서 풀어도 된다.

가능한 모든 경우의 수를 구하기 위해서 key와 lock의 크기를 기준으로 a라는 배열을 만든다. key와 lock의 크기가 3x3으로 동일하다고 하면 다음과 같이 a를 만들어야 한다.

위 그림에서 노란색으로 색칠한 부분이 lock에 해당하고, 빨간색 박스가 key에 해당한다. 이제 이 배열에서 빨간색 박스 key로 a를 슬라이딩하면서 lock에 해당하는 부분이 모두 채워지는 경우가 있는지 확인하면 된다.

따라서 a를 (len(key)*2+len(lock)-2)x(len(key)*2+len(lock)-2) 크기인 0인 2차원 배열로 초기화 하고 lock에 해당하는 부분만 채워주도록 한다.

위 그림부터 시작해서 현재 key 모양, 90도 회전한 모양, 180도 회전한 모양, 270도 회전한 모양을 각각 넣어보면서(360도는 현재 key 모양과 같다.) lock의 모든 값이 1로 바뀌었는지 확인한다.

이 확인 과정을 슬라이딩 끝까지 진행하며 중간에 True인 경우가 있다면 바로 true를 반환한다. 만약 끝까지 true인 경우가 없다면 false를 반환한다.

문제링크:

https://programmers.co.kr/learn/courses/30/lessons/60059

문제:

KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.

예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면 높이가 4인 다섯 번째 탑에서 발사한 레이저 신호를 높이가 7인 네 번째 탑이 수신을 하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신을 한다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신을 하지 못한다.

탑들의 개수 N과 탑들의 높이가 주어질 때, 각각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지를 알아내는 프로그램을 작성하라.

입력:

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다.

출력:

첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다.

풀이방법:

N이 최대 500,000개 이기 때문에 효율적으로 알고리즘을 구성해야 하고, 따라서 스택 자료 구조를 사용하게 되었다.

알고리즘은 다음과 같은 과정을 반복한다.

1. 현재 인덱스에 존재하는 탑의 높이와 스택의 끝(가장 마지막에 넣은 값)과 비교한다.

    1-1. 만약 스택이 비어 있다면 0을 넣고, 현재 인덱스 값을 (위치, 값) 형식으로 스택에 넣는다.

2. 만약 현재 인덱스 탑 높이가 더 크다면, 스택의 마지막 값이 현재 인덱스의 탑 높이가 커지거나 비워질 때까지 계속 pop한다.

3. 스택의 마지막 값이 현재 인덱스의 탑 높이보다 크다면, 스택의 마지막 값의 위치 값을 answer에 넣고, 스택에 현재 인덱스 값을 (위치, 값) 형식으로 넣는다.

문제링크:

https://www.acmicpc.net/problem/2493

문제:

수현이는 4차 산업혁명 시대에 살고 있는 중학생이다. 코로나 19로 인해, 수현이는 버추얼 학교로 버추얼 출석해 버추얼 강의를 듣고 있다. 수현이의 버추얼 선생님은 문자가 2개인 연립방정식을 해결하는 방법에 대해 강의하고, 다음과 같은 문제를 숙제로 냈다.

다음 연립 방정식에서 x와 y의 값을 계산하시오.

4차 산업혁명 시대에 숙제나 하고 앉아있는 것보다 버추얼 친구들을 만나러 가는 게 더 가치있는 일이라고 생각했던 수현이는 이런 연립방정식을 풀 시간이 없었다. 다행히도, 버추얼 강의의 숙제 제출은 인터넷 창의 빈 칸에 수들을 입력하는 식이다. 각 칸에는 -999 이상 999 이하의 정수만 입력할 수 있다. 수현이가 버추얼 친구들을 만나러 버추얼 세계로 떠날 수 있게 도와주자.

입력:

정수 a,b,c,d,e,f가 공백으로 구분되어 차례대로 주어진다. (-999<=a,b,c,d,e,f<=999)

문제에서 언급한 방정식을 만족하는 (x,y)가 유일하게 존재하고, 이 때 x와 y사 각각 -999 이상 999 이하의 정수인 경우만 입력으로 주어짐이 보장된다.

출력:

문제의 답인 x와 y를 공백으로 구분해 출력한다.

풀이방법:

연립방정식을 푸는 방법은 보통 가감법을 많이 사용한다. 따라서 가감법을 사용해서 x와 y에 대한 식을 계산하면 다음과 같이 정리되고, 해당하는 값을 넣어주면 값이 나올 것이다. 답은 항상 정수이기 때문에 // 를 사용했다.

다른 방법으로는 방정식을 만족하는 해가 유일하게 하나 존재하고, -999~999 사이의 정수라는 조건이 있다. 따라서 반복문을 통해서 모든 값에 대해 체크를 하는 방식으로도 답을 구할 수 있다.

문제링크:

https://www.acmicpc.net/problem/19532