백준 17142 - 연구소 3 시간 제한 0.25초, 메모리 제한 512MB # 조건 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제되며, 1초가 걸린다. 승원이는 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소는 크기가 N×N인 정사각형으로 나타낼 수 있으며, 정사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽, 바이러스로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다. 예를..

백준 5549_행성 탐사 시간 제한 1초, 메모리 제한 256MB # 조건 상근이는 우주선을 타고 인간이 거주할 수 있는 행성을 찾고 있다. 마침내, 전 세계 최초로 인간이 거주할 수 있는 행성을 찾았다. 이 행성은 정글, 바다, 얼음이 뒤얽힌 행성이다. 상근이는 이 행성에서 거주 할 수 있는 구역의 지도를 만들어 지구로 보냈다. 상근이가 보내온 지도는 가로 Ncm, 세로 Mcm 직사각형 모양이다. 지도는 1cm 크기의 정사각형으로 나누어져 있고, 각 구역의 지형이 알파벳으로 표시되어 있다. 지형은 정글, 바다, 얼음 중 하나이며, 정글은 J, 바다는 O, 얼음은 I로 표시되어 있다. 지구에 있는 정인이는 조사 대상 영역을 K개 만들었다. 이때, 각 영역에 정글, 바다, 얼음이 각각 몇 개씩 있는지 구하..

백준 20364 - 부동산 다툼 시간 제한 2초, 메모리 제한 1024MB # 조건 이진 트리 모양의 땅으로 이루어진 꽉꽉마을에는 오리들이 살고 있다. 땅 번호는 다음과 같이 매겨진다. 루트 땅의 번호는 1이다. 어떤 땅의 번호가 K라면, 왼쪽 자식 땅의 번호는 2 × K, 오른쪽 자식 땅의 번호는 2 × K + 1이다. 어느날 오리들끼리 부동산 다툼이 일어나서 꽉꽉마을 촌장 경완이가 해결책을 가져왔고, 그 내용은 다음과 같다. 오리들을 한 줄로 대기시킨다. 맨 처음 오리들은 1번 땅에 위치해 있다. 오리들이 서있는 순서대로 원하는 땅을 가지도록 한다. 만약, 한 오리가 원하는 땅까지 가는 길에 이미 다른 오리가 점유한 땅이 있다면 막대한 세금을 내야 하는 이유로 해당 땅을 지나가지 못해 그 오리는 땅을..

코드트리 - 핀볼게임 풀이시간 25분 # 접근 방법 dx, dy 테크닉이 중요한 문제이다. 1번과 2번 벽을 만났을 때 어떻게 진행시키는지가 중요하다. di, dj = [1, 0, -1, 0], [0, 1, 0, -1]로 설정해주며 1번을 만난 경우와 2번을 만난 경우를 각각 회전하는 딕셔너리를 만들어준다. first = {0:3, 1:2, 2:1, 3:0} second = {0:1, 1:0, 2:3, 3:2} 0행에서 진행, 0번째 열 기준 진행, N-1번째 행 기준 진행, N-1번째 열 기준 진행을 해주면 된다. 주의할 점은, 들어가는 시간과 나오는 시간을 포함해주어야 한다는 것과 시작 위치마다 핀볼의 시작 진행 방향이 다르다는 것이다. 들어갈 때부터 카운트를 해주고 이동하는 것을 편하게 하기 위하여..

백준 4358 - 생태학 시간 제한 1초, 메모리 제한 256MB # 조건 생태학에서 나무의 분포도를 측정하는 것은 중요하다. 그러므로 당신은 미국 전역의 나무들이 주어졌을 떄, 각 종이 전체에서 몇 %를 차지하는지 구하는 프로그램을 만들어야 한다. 입력 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어진다. 출력 주어진 각 종의 이름을 사전순으로 출력하고, 그 종이 차지하는 비율을 백분율로 소수점 4째자리까지 반올림해 함께 출력한다. # 접근 방법 문제 자체는 쉬운 난이도였다. 입력받는 나무들을 dicttionary에 이름마다 +=1 을 해주고,..

코드트리 - 최적의 십자 모양 폭발 # 접근 방법 완전 탐색을 활용한 시뮬레이션 문제이다. 0, 0부터 N-1, N-1까지 모든 폭탄을 터트린 후, 조건에 맞는지 검사해주면 된다. 항상 느끼는 것이지만, 모든 문제를 풀 때 각 기능을 함수로 나누는 것이 디버깅에도 유리하고 코드를 읽을 때도 잘 읽히는 것 같다. bomb함수 폭탄을 터트리며 터진 곳을 저장해주었다. 시작 위치는 height에 우선적 저장을 해주었는데, 1칸만 터지는 경우 세로로만 복사해주면 되기 때문이다. 시간을 가장 많이 소비한 곳은 폭탄을 터트린 후 격자에 중력을 작용시키는 부분이었다. gravity 함수 가로로 터지는 부분은 최대 1칸이므로 터진 곳을 저장 세로로 터지는 곳은 저장 후 정렬을 통하여 가장 위의 칸과 가장 아래 칸을 변..

코드트리 - 최단 Run Length 인코딩 # 접근 방법 문자열을 비손실 압축 방식으로, 오른쪽으로 shift를 통하여 최소 길이로 만드는 문제이다. 평소에 많이 접해보지 않은 문제이지만 아이디어를 떠올리는 것이 어렵지 않았다. 오른쪽 shift를 통해서 현재보다 짧은 길이로 만들기 위해서는, 가장 먼저 나온 문자열과 가장 마지막에 나온 문자열이 같아야 된다. 우선, 주어진 문자열을 순회하며 비손실 압축을 해준다. 이후 길이가 2인 경우 => 모든 문자열이 1개로 이루어진 경우는 바로 2를 출력해준다. 그렇지 않다면, 뒤에서 2번째 문자와 가장 첫 문자를 비교해준 후, 같다면 개수를 합쳐준다. import sys input = sys.stdin.readline words = input().strip()..

백준 1948 - 임계경로 시간 제한 2초, 메모리 제한 512MB # 조건 월드 나라는 모든 도로가 일방통행인 도로이고, 싸이클이 없다. 그런데 어떤 무수히 많은 사람들이 월드 나라의 지도를 그리기 위해서, 어떤 시작 도시로부터 도착 도시까지 출발을 하여 가능한 모든 경로를 탐색한다고 한다. 이 지도를 그리는 사람들은 사이가 너무 좋아서 지도를 그리는 일을 다 마치고 도착 도시에서 모두 다 만나기로 하였다. 그렇다고 하였을 때 이들이 만나는 시간은 출발 도시로부터 출발한 후 최소 몇 시간 후에 만날 수 있는가? 즉, 마지막에 도착하는 사람까지 도착을 하는 시간을 의미한다. 어떤 사람은 이 시간에 만나기 위하여 1분도 쉬지 않고 달려야 한다. 이런 사람들이 지나는 도로의 수를 카운트 하여라. 출발 도시는..

백준 20183 - 골목 대장 호석 - 효율성2 시간 제한 5초, 메모리 제한 512MB # 조건 소싯적 호석이는 골목 대장의 삶을 살았다. 호석이가 살던 마을은 N 개의 교차로와 M 개의 골목이 있었다. 교차로의 번호는 1번부터 N 번까지로 표현한다. 골목은 서로 다른 두 교차로를 양방향으로 이어주며 임의의 두 교차로를 잇는 골목은 최대 한 개만 존재한다. 분신술을 쓰는 호석이는 모든 골목에 자신의 분신을 두었고, 골목마다 통과하는 사람에게 수금할 것이다. 수금하는 요금은 골목마다 다를 수 있다. 당신은 A 번 교차로에서 B 번 교차로까지 C 원을 가지고 가려고 한다. 호석이의 횡포를 보며 짜증은 나지만, 분신술을 이겨낼 방법이 없어서 돈을 내고 가려고 한다. 하지만 이왕 지나갈 거면, 최소한의 수치심..