본문 바로가기

코딩테스트 연습/백준 Boj51

[Python] 백준 16968번 (차량 번호판 1) 문제 상도시의 차량 번호판 형식이 주어졌을 때, 가능한 차량 번호판의 개수를 구해보자. 번호판에 사용할 수 있는 숫자는 0, 1, 2, ..., 8, 9이다. 사용할 수 있는 문자는 a, b, c, d, ..., y, z이다. 차량 번호판의 형식은 최대 4글자이고, c와 d로 이루어진 문자열로 나타낼 수 있다. c는 문자가 위치하는 자리, d는 숫자가 위치하는 자리이다. 같은 문자 또는 숫자가 연속해서 2번 나타나면 안 된다. 예를 들어, 형식이 "cd"이면, a1, d4, h5, k4 등이 가능하다. 형식이 "dd"인 경우에 01, 10, 34, 69는 가능하지만, 00, 11, 55, 66은 같은 숫자가 2번 연속해서 불가능하다. 입력 첫째 줄에 차량 번호판의 형식이 주어진다. 형식은 길이가 4보다 .. 2021. 11. 24.
[Python] 백준 16924번 (십자가 찾기) 문제 십자가는 가운데에 '*'가 있고, 상하좌우 방향으로 모두 같은 길이의 '*'가 있는 모양이다. 십자가의 크기는 가운데를 중심으로 상하좌우 방향으로 있는 '*'의 개수이다. 십자가의 크기는 1보다 크거나 같아야 한다. 아래 그림은 크기가 1, 2, 3인 십자가이고, 빈 칸은 '.'이다. ...*... ..*.. ...*... .*. ..*.. ...*... *** ***** ******* .*. ..*.. ...*... ..*.. ...*... ...*... 크기가 N×M이고, '.'과 '*'로 이루어진 격자판이 주어진다. 이때, 십자가만을 이용해서 격자판과 같은 모양을 만들 수 있는지 구해보자. 십자가는 서로 겹쳐도 된다. 사용할 수 있는 십자가의 개수는 N×M이하이어야 한다. 격자판의 행은 위에서.. 2021. 11. 23.
[Python] 백준 1043번 (거짓말) 문제 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다. 사람의 수 N이 주어진다. 그리고 그.. 2021. 11. 21.
[Python] 백준 9465번 (스티커) 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 .. 2021. 11. 21.
[Python] 백준 18234번 (당근 훔쳐 먹기) 꽉꽉나라의 농부 오리는 아무것도 심어져 있지 않은 텃밭을 하나 가지고 있다. 오리는 그 텃밭에 N종류의 당근을 하나씩 심고 T일 동안 재배할 예정이다. 당근 i(1 ≤ i ≤ N)는 처음에는 wi의 맛을 가지고 있고, 각 당근 i에 사용할 pi만큼 맛을 증가시켜주는 영양제가 당근 종류별로 T개씩 준비되어 있다. 오리는 당근이 본래의 맛보다 훨씬 맛있어지기를 바라기 때문에 pi는 항상 wi이상의 값을 가지도록 준비했다. 잠이 많은 오리는 매일 오전에만 텃밭에 나와 당근들을 관리한다. 오리는 각 당근 i에 대해 당근 i가 자리에 없다면 당근 i를 심고, 그렇지 않다면 당근 i에 영양제를 하나 준다. 꽉꽉나라에 놀러 온 토끼는 오리가 오전에만 당근을 관리한다는 사실을 알고 오리의 텃밭을 찾아가 당근을 훔쳐 먹.. 2021. 11. 18.
[Python] 백준 (소수&팰린드롬) 문제 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. 출력 첫째 줄에 조건을 만족하는 수를 출력한다. 예제 입력 1 31 예제 출력 1 101 문제풀이 팰린드롬 == 123321, 가나다나가 등 뒤집어도 같은 수 소수를 판별하는 함수를 만들어 둔다.(isPrime) 입력한 숫자부터 1000000까지 팰린드롬 수를 찾는다. 만약 n이 커서 출력이 10000000이 넘는 경우가 생길 수 있다. 반복문을 다 도는 동안 r.. 2021. 11. 4.
[Python] 백준 (분산처리) 1009번 문제 재용이는 최신 컴퓨터 10대를 가지고 있다. 어느 날 재용이는 많은 데이터를 처리해야 될 일이 생겨서 각 컴퓨터에 1번부터 10번까지의 번호를 부여하고, 10대의 컴퓨터가 다음과 같은 방법으로 데이터들을 처리하기로 하였다. 1번 데이터는 1번 컴퓨터, 2번 데이터는 2번 컴퓨터, 3번 데이터는 3번 컴퓨터, ... , 10번 데이터는 10번 컴퓨터, 11번 데이터는 1번 컴퓨터, 12번 데이터는 2번 컴퓨터, ... 총 데이터의 개수는 항상 ab개의 형태로 주어진다. 재용이는 문득 마지막 데이터가 처리될 컴퓨터의 번호가 궁금해졌다. 이를 수행해주는 프로그램을 작성하라. 입력 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 정수 a와 b가 주어진다... 2021. 11. 2.
[Python] 백준 (LCS 최장 공통 부분 수열) 9251번 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다. 예제 입력 1 ACAYKP CAPCAK 예제 출력 1 4 문제 풀이 문제를 처음 본 생각: 무슨 말이지...? 결국 부분 수열 중 길이가 가장 긴 것을 구하자! LCS에는 최장 공통 문자열(Longest Common Substring)과 최장 공통 부분 수열(L.. 2021. 11. 1.
[Python] 백준 (바이러스) 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수.. 2021. 10. 27.
[Python] 백준 (트리 순회) -전위 순회, 중위 순회, 후위 순회 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오. 예를 들어 위와 같은 이진 트리가 입력되면, 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식) 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식) 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트) 가 된다. 입력 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파.. 2021. 10. 26.
[Python] 백준 (1, 2, 3 더하기) 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. 예제 입력 1 3 4 7 10 예제 출력 1 7 44 274 풀이방법 점화식을 추론하자 A1 A2 A3 A4 1 1+ A(1) -> (A1) = 1가지 1+(A2) -> (A.. 2021. 10. 25.
[Python] 백준 (다리놓기) DP, 조합 문제풀이 조금 생각하다 보니 조합 문제임을 알 수 있었다. n < m 이기 때문에 최대 연결할 수 있는 다리는 n개 이다. m개 지역에 n개의 다리를 연결하는 경우의 수 조합: 집합에서 서로 다른 n개의 원소 중에서 순서에 상관없이 r개를 선택하는 것이다. mCn이 만들어짐 itertools의 combinations를 쓰면 제한시간(0.5초)에 걸려 해결 할 수 없음 직접 만들어쓰자..! 분자 denominator은 m*(m-1)*(m-2)*...*(m-n) 까지의 값 분모 numerator은 n! import sys T = int(sys.stdin.readline().rstrip()) answer = [] for i in range(T): denominator = 1 numerator = 1 N, M .. 2021. 10. 25.

티스토리툴바