CodeDrive

문제:

풀이방법:

여러가지 푸는 방법이 있겠지만, 가장 단순하면서 쉬운 방법을 사용하고자 한다. 브루트 포스 방식으로 가능한 모든 경우의 수를 만들고 그 중에서 해당하는 조건을 찾는 방법으로 했다.

 우선 python의 itertools의 permutation을 사용해서 모든 경우의 수를 만든다. 그리고 각 조건에 맞는지 확인을 하는데, 조건의 길이와 다르면 바로 False로 가도록 하고, 길이가 같다면 그 때 조건을 비교하도록 한다.

 이렇게 조건에 맞는 경우를 찾았다면 중복을 방지하기 위해서 set으로 값을 넣도록 한다.

문제링크:

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

문제:

 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다.

 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다.

이제 위와 같은 지역에 많은 비가 내려서 높이가 4 이하인 모든 지점이 물에 잠겼다고 하자. 이 경우에 물에 잠기는 지점을 회색으로 표시하면 다음과 같다.

물에 잠기지 않는 안전한 영역이라 함은 물에 잠기지 않는 지점들이 위, 아래, 오른쪽 혹은 왼쪽으로 인접해 있으며 그 크기가 최대인 영역을 말한다. 위의 경우에서 물에 잠기지 않는 안전한 영역은 5개가 된다.(꼭짓점으로만 붙어 있는 두 지점은 인접하지 않는다고 취급한다.)

또한 위와 같은 지역에서 높이가 6이하인 지점을 모두 잠기게 만드는 많은 비가 내리면 물에 잠기지 않는 안전한 영역은 아래 그림에서와 같이 네 개가 됨을 확인할 수 있다.

이와 같이 장마철에 내리는 비의 양에 따라서 물에 잠기지 않는 안전한 영역의 개수는 다르게 된다. 위의 예와 같은 지역에서 내리는 비의 양에 따른 모든 경우를 다 조사해 보면 물에 잠기지 않는 안전한 영역의 개수 중에서 최대인 경우는 5임을 알 수 있다.

어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 프로그램을 작성하시오.

입력:

첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1 이상 100 이하의 정수이다.

출력:

첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

풀이방법:

 bfs를 사용해서 풀수는 있을 것 같지만 dfs를 사용해서 풀었다. 재귀의 깊이가 얼마나 될지 모르고, deepcopy를 사용하기 위해서 sys와 copy를 import 했다.

 지역의 높이 정보 입력값을 받으면서 max 연산을 취해서 지역 내에 가장 높은 영역이 값을 얻도록 했다. (뒤에서 for 반복문에서 사용하기 위해) 입력을 다 받은 뒤에는 이 높이 정보를 deepcopy한 뒤 현재 rain에 맞게(1부터 시작한다.) 값을 빼주고 만약 0 이하로 떨어지게 된다면 0으로 만들고 나머지는 그대로 냅뒀다.

 이제 이렇게 비에 잠긴 영역들을 표시했으니 dfs를 사용해서 살아있는 영역의 개수를 구한다. 각 점을 탐색하며 0이 아닌 곳에서 dfs 탐색을 시작하며 탐색 되는 곳은 0으로 만들어줘서 방문했음을 알려준다. 이렇게 반복해서 하면 영역의 개수를 구할 수 있고 max 연산을 통해 최댓값을 구한다.

문제링크:

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

문제:

2차원 배열이 주어졌을 때 (i,j) 위치부터 (x,y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. 배열의 (i,j) 위치는 i행 j열을 나타낸다.

입력:

첫째 줄에 배열의 크기 N,M (1<=N,M<=300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 합을 구할 부분의 개수 K(1<=K<=10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i,j,x,y가 주어진다. (i<=x,j<=y).

출력:

K개의 줄에 순서대로 배열의 합을 출력한다. 배열의 합은 2^31-1보다 작거나 같다.

풀이방법:

pypy3로 통과했습니다.

문제링크:

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

문제:

어떤 파일 시스템에는 디스크 공간이 파일의 사이즈와 항상 같지는 않다. 이것은 디스크가 일정한 크기의 클러스터로 나누어져 있고, 한 클러스터는 한 파일만 이용할 수 있기 때문이다.

예를 들어, 클러스터의 크기가 512바이트이고, 600바이트 파일을 저장하려고 한다면, 두 개의 클러스터에 저장하게 된다. 두 클러스터는 다른 파일과 공유할 수 없기 때문에, 디스크 사용 공간은 1024바이트가 된다.

파일의 사이즈와 클러스터의 크기가 주어질 때, 사용한 디스크 공간을 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 파일의 개수 N이 주어진다. N은 1,000보다 작거나 같은 자연수이다. 둘째 줄에는 파일의 크기가 공백을 사이에 두고 하나씩 주어진다. 파일의 크기는 1,000,000,000보다 작거나 같은 음이 아닌 정수이다. 마지막 줄에는 클러스터의 크기가 주어진다. 이 값은 1,048,576보다 작거나 같은 자연수이다.

출력:

첫째 줄에 사용한 디스크 공간을 출력한다.

풀이방법:

파일을 클러스터에 넣으려고 할 떄 크게 3가지 경우가 발생한다.

1. 한 파일의 크기가 한 클러스터의 크기보다 큰 경우

2. 한 파일의 크기가 한 클러스터의 크기와 같은 경우

3. 한 파일의 크기가 한 클러스터의 크기보다 작은 경우

그리고 위 3가지 case는 몫과 나머지를 통해서 구할 수 있다.

파일사이즈를 클러스터의 크기로 나눴을 때, 몫이 1보다 커지게 된다면 1의 케이스에 해당하며 몫만큼 클러스터의 개수를 준비하고 나머지가 있을 경우 하나 더 준비하면 된다.

그리고 몫이 0이라면 나머지가 있을 경우에는 한 개를 준비하면 되고, 나머지가 없다면 준비안하면 된다.

몫과 나머지를 구할 수 있는 divmod를 사용해서 알고리즘을 구현하면 된다.

문제링크:

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

문제:

강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다.

스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다.

보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없다. U버튼은 위로 U층을 가는 버튼, D버튼은 아래로 D층을 가는 버튼이다.(만약, U층 위, 또는 D층 아래에 해당하는 층이 없을 때는, 엘리베이터는 움직이지 않는다)

강호가 G층에 도착하려면, 버튼을 적어도 몇 번 눌러야 하는지 구하는 프로그램을 작성하시오. 만약, 엘리베이터를 이용해서 G층에 갈 수 없다면, "use the stairs"를 출력한다.

입력:

첫째 줄에 F, S, G, U, D가 주어진다. (1<=S,G<=F<=1000000, 0<=U,D<=1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다.

출력:

첫째 줄에 강호가 S층에서 G층으로 가기 위해 눌러야 하는 버튼의 수의 최솟값을 출력한다. 만약, 엘리베티어로 이동할 수 없을 때는 "use the stairs"를 출력한다.

풀이방법:

 BFS로 경우의 수를 카운팅하면서 최소의 값을 찾을 수 있다. 우선 S와 G가 같으면 버튼을 누를 필요가 없기 때문에 0으로 답을 출력하도록 했다. 이제 이외의 경우에 대해서 BFS를 사용하기 위해, 초기 시작 층인 S로 state를 초기화 했고, 중복방문을 제거하기 위해서 visited를 초기화 했다.

 이제 갈 수 없는 경우( 0층, F층 초과)만 있을 때까지 계속 반복하기 위해서 while을 len(state) 초기화 했고, 현재 층을 s라고 할 때 다음과 같은 경우에만 이동하도록 한다.

1. s+U가 F층 이하이고, 방문하지 않은 곳이라면

2. s-F가 1층 이상이고, 방문하지 않은 곳이라면

이를 반복하면서 G가 나타나거나, 1,2 케이스가 하나도 없을 떄까지 반복해서 답을 구하도록 한다.

문제링크:

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

문제:

풀이방법:

 문자열을 처리하고 규칙에 따라 정리를 하면 되는 문제이다.

우선 양 끝은 {{~~}}으로 고정이 되어 있다. 따라서 슬라이싱을 통해서 이 부분을 떼어내고 숫자들을 구분하기 위해서    '}.{'로 split을 한다. 이렇게 하면 ['2', '2,1' , '2,1,3' , '2,1,3,4'] 와 같이 분리되게 된다.

 반복문으로 순환을 하면서 다시 ','을 기준으로 분리를 하면 숫자만 남게 되는데 이를 각 원소값이 int인 list로 tuples에 정리하게 된다. 이 단계까지 마치면 문자열을 규칙에 적용할 수 있도록 정리가 마무리 되었다.

규칙은 다음과 같다.

1. 각 list들을 길이가 짧은 순으로 정렬을 한다.

2. list의 숫자 값을 탐색하며 answer list에 없는 값이라면 answer에 넣고 break를 한 뒤 다음 list를 탐색한다.

따라서 이 규칙을 끝까지 적용하면 answer를 얻을 수 있다.

문제링크:

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

문제:

풀이방법:

문제에서 주어진대로 구현을 해도 되지만 stack을 활용해서 풀었다. 각 열별로 newboard에 stack으로 정리를 하며, move를 이용해서 각 열에 있는 값들을 pop을 해서 빼온다. move에 해당하는 열에 값이 없다면 continue로 행동을 넘기며 값이 있다면 basket에 값을 넣는다.

 basket에 값을 넣었다면 위의 두 값이 같은지 확인하고 같다면 pop을 사용해서 빼고 answer 카운트를 2 증가시킨다. (두 값이 같아 없어지는 행위를 세는 것이 아니라 없어진 것의 개수를 구하는 것이므로 2를 더하는게 맞다.)

이 행위를 moves에 있는 행동대로 다 하고 난 뒤의 answer를 반환한다.

문제링크:

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

문제:

상근이는 덧셈과 나눗셈을 엄청나게 못한다. 이런 상근이를 위해 정인이는 상근이에게 다음과 같은 문제를 냈다.

정인이는 양의 정수 A,B,C,D로 이루어진 2*2 표를 그렸다.

위와 같은 표가 있을 때, 표의 값은 A/C + B/D 이다.

상근이는 표를 몇 번 돌리면 표의 값이 최대가 되는지 궁금해졌다.

표는 90도 시계방향으로 돌릴 수 있다.

문제 상단의 표를 1 번 회전시키면 다음과 같다.

2번 회전 시키면 다음과 같이 된다.

표에 쓰여 있는 A,B,C,D가 주어졌을 때, 표를 몇 번 회전시켜야 표의 값이 최대가 되는지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 A와 B가 공백으로 구분되어 주어진다. 둘째 줄에 C와 D가 공백으로 구분되어 주어진다. 모든 수는 100보다 작거나 같은 양의 정수이다.

출력:

첫째 줄에 표를 몇 번 돌려야 표의 값이 최대가 되는지 출력한다. 만약, 그러한 값이 여러개라면 가장 작은 값을 출력한다.

풀이방법:

사실 경우의 수가 4개 밖에 없기 때문에 0,90,180,270도 순으로 배열을 구성하도록 했다.

그리고 max 값의 index를 찾도록 했는데, 최대인 값이 여러개라고 하더라도 index는 가장 먼저 나오는 index를 반환하기 때문에 출력조건에 위배되지 않는다.

문제링크:

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

문제:

상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다.

각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다.

상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다.(2<=n<=10^6) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고, "enter"나 "leave"가 주어진다. "enter"인 경우는 출근, "leave"인 경우는 퇴근이다.

회사에 동명이인이 없으며, 대소문자가 다른 경우에는 다른 이름이다. 사람들의 이름은 알파벳 대소문자로 구성된 5글자 이하의 문자열이다.

출력:

현재 회사에 있는 사람의 이름을 사전 순의 역순으로 한 줄에 한 명씩 출력한다.

풀이방법:

 동명이인이 없고, 대소문자가 다른 경우에는 다른 이름이기 때문에 한 사람이 출근하고 퇴근하는 것은 독립적이다. 따라서 python의 dict을 이용해서 해쉬를 구성하도록 했다. 

 "enter"와 "leave"와 상관 없이 처음 이름이 등장한다면 출근이고, 두 번째로 이름이 등장한다면 퇴근하는 것이라 생각하고, 처음 등장하면 True로 값을 새로 저장하고, 다시 등장하면 False로 바꿔주도록 했다.

 모두 확인했다면 dict의 items()를 사용해서 key, value 쌍으로 묶어주고, 역순 정렬을 한 뒤 , value 값이 True인 것만 출력하도록 했다.

문제링크:

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

문제:

Vigenere cipher이라는 암호화 방법은 암호화하려는 문장(평문)의 단어와 암호화 키를 숫자로 바꾼 다음, 평문의 단어에 해당하는 숫자에 암호 키에 해당하는 숫자를 더하는 방식이다. 이 방법을 변형하여 평문의 단어에 암호화 키에 해당하는 숫자를 빼서 암호화하는 방식을 생각해 보자.

예를 들어 암호화 키가 love이고, 암호화할 문장이 "nice day"라면 다음과 같이 암호화가 이루어진다.

제시된 평문의 첫 번째 문자인 'n'은 해당 암호화 키 'l'의 알파벳 순서가 12이므로 알파벳상의 순서에서 'n'보다 12앞의 문자인 'b'로 변형된다.

변형된 문자가 'a'이전의 문자가 되면 알파벳 상에서 맨 뒤로 순서를 돌린다. 예를 들면 평문의 세 번째 문자인 'c'는 알파벳 상에서 3번째이고 대응하는 암호화키 'V'는 알파벳 순서 22로 'c'에서 22 앞으로 당기면 'a'보다 훨씬 앞의 문자이어야 하는데, 'a' 앞의 문자가 없으므로 'z'로 돌아가 반복되어 'g'가 된다. 즉 평문의 문자를 암호화키의 문자가 알파벳 상에서 차지하는 순서만큼 앞으로 뺀 것으로 암호화한다.

평문의 문자가 공백 문자인 경우는 그 공백 문자를 그대로 출력한다.

이과 같은 암호화를 행하는 프로그램을 작성하시오.

입력:

첫째 줄에 평문이, 둘째 줄에 암호화 키가 주어진다.

평문은 알파벳 소문자와 공백문자(space)로만 구성되며, 암호화 키는 알파벳 소문자만으로 구성된다. 평문의 길이는 공백까지 포함해서 30000자 이하이다.

출력:

첫 번째 줄에 암호문을 출력한다.

풀이방법:

암호화 키와 평문의 차이를 알아야 하므로 ascii코드 값으로 바꿔 주는 ord 함수를 사용한다. 이를 이용해서 암호화 키와 평문의 차이를 구하고 이 값이 0보다 큰지 작은지를 결정한다.

0보다 크다면 해당 차이 값이 96을 더해주도록 한다.(소문자 'a'의 ascii는 97이다.)

만약 작다면 26을 추가로 더해서 뒤에서 부터 이동하도록 한다. 

문제링크:

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