CodeDrive

문제:

풀이방법:

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

가능한 모든 경우의 수를 구하기 위해서 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

문제:

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

나머지 빈 칸을 채우는 방식은 다음과 같다.

1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

2. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

위의 예의 경우, 첫재 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈칸에는 3이 들어가야 한다.

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

입력:

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

출력:

모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

풀이방법:

pypy3로 통과한 코드입니다. 0인 점에서 가능한 모든 경우의 수를 탐색하면서 백트래킹을 수행해 python3에서 통과하지 못한듯 합니다.

우선 sudoku 배열에 입력을 모두 받아준 뒤에 이를 순회하면서 0인 점을 찾아서 toDoList로 만들어 준다.

이를 인덱스로 접근하는 재귀 함수 check에 넣어주면서 백트래킹을 수행한다.

isPromising를 통해서 가능한 경우의 수를 구해주도록 했다. set 자료형과 차집합을 이용해서 경우의 수를 구하도록 했다. 이 경우의 수를 넣어보면서 dfs 방식으로 답을 구해주도록 한다.

인덱스가 끝까지 진행을 하면 sys.exit()로 바로 종료하도록 했다. (스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않으며, 여럿인 경우여도 하나만 출력하면 되기 때문이다.)

문제링크:

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

문제:

이 사진은 오래전부터 인터넷에 돌아다니는 사진으로, 작년 전대프연 예선 A번에서는 수학을 정말 못 하는 고등학생인 성원이의 시험지로 소개되었다. 저작권이 있는 사진일 수 있어 알아보기 어렵게 가공했음을 양해 바란다.

예선 날짜가 다가오는데도 적당한 A번 문제를 생각하지 못한 출제진은 작년 전대프연 예선 A번을 응용해서 문제를 만들기로 했다. 이를 위해 사진 속 문제를 찾아본 출제진은 해당 문제가 2007학년도 6월 고등학교 1학년 전국연합학력평가 수리 영역 26번임을 알게 되었다.

시험지를 내려받고 문제들을 살펴보던 출제진은 아래와 같은 문제를 발견했다.

예상했겠지만, 여러분은 이제 위의 19번 문제 세 번째 줄에 등장하는 수 '1000'을 임의의 자연수로 바꾸었을 때 그에 해당하는 답을 출력하는 프로그램을 작성해야 한다.

입력:

첫 번째 줄에 자연수 n (1<=n<=10^9)이 주어진다.

출력:

첫 번째 줄에 19번 문제 세 번째 줄에 등장하는 수 '1000'을 자연수 n으로 바꾸었을 때 그에 해당하는 답의 번호를 출력한다. 즉, 1 이상 5 이하의 자연수 중 하나를 출력해야 한다.

풀이방법:

구현을 하는 문제다. 

1~5는 숫자 그대로 답이 되는 경우이기 때문에 따로 처리를 했고, 이를 제외해야지 4의 배수로 나머지 경우를 처리를 하기 쉽기 때문에 따로 처리했다.

 6 이상부터는 4의 배수를 기준으로 왼쪽으로 진행, 오른쪽으로 진행하는 층이 바뀌게 된다. (ex 8은 왼쪽 진행, 12는 오른쪽 진행) 4의 배수중 짝수가 왼쪽으로 진행이고, 홀수가 오른쪽 진행이다. 이를 위해서 n을 4로 나눴을 때, 나머지가 2 이상이면 몫을 하나 늘리고, 그 외는 몫을 그대로 사용해서 현재 층을 파악하도록 했다.

 이제 각 층에서는 나머지에 따라서 답을 나오도록 조건문을 만들어주면 된다.

문제링크:

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

문제:

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

- push X: 정수 X를 큐에 넣는 연산이다.

- pop : 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

- size : 큐에 들어있는 정수의 개수를 출력한다.

- empty : 큐가 비어있으면 1, 아니면 0을 출력한다.

- front : 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

- back : 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력:

첫째 줄에 주어지는 명령의 수 N (1<=N<=2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력:

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

풀이방법:

python의 queue 기능을 사용할 수 있었지만 최근에 알게 된 collections의 deque를 사용해서 풀었다. deque에서 append는 list와 같이 동작을 하고, popleft와 같은 경우에는 맨 앞의 값을 빼는 역할을 수행한다.

문제링크:

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

문제:

정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬으 개수를 세는 프로그램을 작성하시오.

한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다.

두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다.

지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다.

입력:

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다.

둘째 줄부터 h개 줄에는 지도가 주어진다. 1은 땅, 0은 바다이다.

입력의 마지막 줄에는 0이 두 개 주어진다.

출력:

각 테스트 케이스에 대해서, 섬의 개수를 출력한다.

풀이방법:

visited 배열과 bfs를 이용해서 섬의 개수를 세도록 한다.

우선 visited 배열을 만들고, 이를 countLand라는 함수에게 넘겨준다. countLand에서는 주어진 지도를 반복문으로 반복하면서 방문하지 않은 땅이라면 bfs 함수로 들어갈 수 있도록 하며, 이 때마다 count를 하나씩 늘려주는 역할을 한다.

bfs는 일반적인 bfs 함수와 동일하고, 다른점이 있다면 이 문제에서는 대각선까지도 이동이 가능하기 때문에 더 많은 상황을 고려해 줘야 한다.

문제링크:

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

문제:

풀이방법:

 효율적으로 풀어야 하는 문제이기 때문에 O(N^2) 방법으로는 시간초과에 걸릴 것이다. 따라서 투 포인터를 사용하는 슬라이딩 윈도우를 사용해서 풀었다. 

 우선 앞에서부터 뒷 포인터를 이동시키면서 모든 보석을 포함할 때까지 이동한다. 모든 보석을 포함하게 된다면 앞 포인터를 움직여서 가장 앞에 존재했던 보석을 뺀다. 그래도 모든 보석이 포함되어 있다면 앞 포인터를 움직여서 다시 앞을 빼고, 모든 보석이 포함되어 있지 않다면 뒷 포인터를 움직여서 다시 모든 보석을 포함시킬 때까지 움직인다. 

이 과정을 반복하면서 가장 짧은 길이의 포인터들을 저장해두고 최종적으로 출력하도록 한다.

문제링크:

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

문제:

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 남는 카드는 4가 된다.

N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 정수 N(1<=N<=500,000)이 주어진다.

출력:

첫째 줄에 남게 되는 카드의 번호를 출력한다.

풀이방법:

빠른 입출력을 위해서 collections의 deque를 사용했다. 스택과 큐의 기능을 한번에 사용할 수 있다.

문제링크:

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

문제:

풀이방법:

 연산자를 계산하는 방법으로 주로 스택을 사용하기 때문에 스택을 사용하고, 수식의 갯수가 3개이므로 최대 6가지 조합이 가능하기 때문에 브루트 포스 방법을 사용해서 모든 케이스에 대해 계산을 하고 그 중 최대값을 찾는 방법을 사용한다.

 우선 정규표현식과 itertools의 permutations을 사용해서 입력받은 expression에 대해서 숫자와 수식을 분리해내고, 연산자들의 우선순위를 만든다.

 생성된 우선순위별로 숫자와 연산자들을 스택에 넣고, 연산자가 현재 해당하는 우선순위의 연산자라면 숫자 스택에서 두 개를 빼고, 연산자 스택에서 하나를 빼서 연산을 하고 다시 숫자 스택에 넣도록 한다.

 이 과정을 우선순위와 연산자별로 계속 반복해서 하고 이 중 max 값을 찾아서 반환하도록 한다.

문제링크:

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