[백준 19238] 스타트 택시(Python)
주어진 조건을 고려하여, 판다가 가장 오래 살 수 있는 일 수를 구하는 문제
4가지 색의 뿌요(R, G, P, Y)가 위에서 아래로 떨어진다. 뿌요들이 바닥에 놓여진 후, 상하좌우로 인접한 같은 색의 뿌요가 4개 이상일 경우, 해당 뿌요들은 폭발한다 그리고 연쇄가 하나 증가한다. 폭발 후, 위에 남은 뿌요들이 있다면 아래로 떨어진다. 차례대로
DSLR 명령어를 이용하여 숫자 A를 숫자 B로 변환할 때, 나올 수 있는 최소 경로를 출력하는 문제.
화면에 이모티콘이 1개가 있는데, 다음 연산들을 이용하여 이모티콘을 S개 만든다.화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장클립보드에 있는 모든 이모티콘을 화면에 붙여넣기화면에 있는 이모티콘 중 하나를 삭제각 연산은 1초가 걸리며, 우리가 해야할 일을 최소 시
글자인 부분을 의미하는 1이 상, 하, 좌, 우, 대각선으로 서로 인접하면 이들은 모두 1개의 글자로 간주한다. 이 때, 주어진 현수막에서 몇 개의 글자가 있는지 찾아보자.
2개의 레이저간의 통신을 하려고한다.(항상 통신이 가능하다고 간주한다.)레이저는 벽을 뚫을 수 없으며, 빈칸을 통행 움직인다. 레이저는 특성상 직진하며, 거울을 설치해서 방향을 90도로 회전시켜 바꿀 수 있다. 설치에 필요한 거울의 최소 개수를 구해보자.
바라보는 방향으로 궤도를 따라 움직이는 로봇이 있다. 움직이는 방향은 동, 서, 남, 북 중 하나이며, 다음 2가지의 명령을 통해 움직일 수 있다.Go k: 현재 향하고 있는 방향으로 k칸 이동한다.Turn dir: 현재 방향에서 오른쪽 또는 왼쪽으로 90도 회전한다.
2칸을 차지하는 파이프라인을 바라보는 방향에 대해 직진 또는 회전 후 직진하여, 파이프의 한 쪽 끝을 (N, N)으로 보낼 때 나올 수 있는 경우의 수를 구하는 문제. 이 때, (y, x)칸이 0일 때만 이동 가능하다.
4개월 동안 방치한 문제를 이제야 풀었다.N\*M 격자판 어딘가에 적이 있고, N+1행, 모든 칸에 성이 있다. 캐슬 디펜스는 궁수 3명을 성에 배치 할 때, 주어진 공격 범위안의 가장 가까운 적 1명을 퇴치하는 게임이다.
배열을 r만큼 반시계 방향으로 돌리는 문제
N개의 구역이있고, 각 구역에 시민들이 살고 있다. 그리고 구역을 묶어서 2개의 선거구를 만들어야한다. 선거구를 만들 때 규칙은 다음과 같다.각 구역은 두 선거구 중 반드시 하나에만 포함되어야한다.선거구는 적어도 구역 하나를 포함해야한다.선거구에 포함된 구역들은 모두
배열돌리기1을 응용한 문제이다. 배열돌리기4의 경우, 시계방향으로 1만큼 회전한다. 그리고 회전 연산이 1개이상 주어지는데, 회전연산의 정의는 아래와 같다.회전 연산은 (r, c, s)로 이루어져 있다.(r-s, c-s) ~ (r+s, c+s) 범위내 원소들을 시계 방
주어진 그래프가 이분 그래프인지 아닌지 확인하는 문제.
문제 참고(https://www.acmicpc.net/problem/16946)NxM 정답 배열을 만들고 임의 좌표 y,x에 대해 정답배열\[y]\[x]가 벽이면 값을 1로 바꾼다.그리고 맵을 탐색하면서 0을 가리키는 위치를 찾고 그 위치가 처음 방문한 곳이면
1. 요약 폭발 문자열과 문자열이 주어질때 문자열 안에 폭발 문자열있으면, 폭발 문자열에 해당하는 문자는 없어지고, 뒤에있는 남은 문자열과 합쳐지게된다. 폭발은 연쇄적으로 발생할 수 있다. 우리가 해야할일은 폭발하고 남은 문자열을 출력해야한다. 만약 남아있는 문자열이
성곽의 크기와 벽이 주어졌을 때, 이 성에 있는 방의 개수, 가장 넓은 방의 넓이, 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기를 구해야한다. 벽은 통과할 수 없다. 서쪽 벽은 1, 동쪽벽은 4, 북쪽 벽은 2, 남쪽 벽은 8이며, 벽에 대한 정보는 벽이
간선에 가중치가 있는 트리에서 임의의 두 노드를 선택할 때, 두 노드 사이의 경로가 가장 긴 것을 찾는 문제긴 경로를 갖는 후보는 두 노드가 모두 리프노드 일 때다. 이들 중 가장 긴 경로를 찾으면 된다.모든 트리의 노드가 갖는 서브트리에 대해 dfs를 한다.dfs의
오랜만에 알고리즘 공부해서 그런지, 구현이 너무 힘들었다움직이는 미로에서 사람이 탈출 가능한지 묻는 문제 구체적으로 설명하면, 사람이 이동한다.(대각선 방향으로 인접한 곳으로 1칸이동, 상하좌우 인접한 방향으로 1칸 이동, 제자리) 그 다음, 벽이 아래 행 방향(↓
N개의 수로된 수열 A\[1], A\[2], ..., A\[N]이 있을 때, i번째 수부터 j번째 수까지의 합, A\[i] + A\[i+1] + A\[i+2] + .. + A\[j]가 M이 되는 경우의 수를 구하는 문제투 포인터를 이용하여 해결했다.배열 A의 인덱스를
매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보는 문제.단순하게 연속적인 며칠에 대한 간격만 맞추는 식으로 구현하면 시간 초과가 난다. 예를 들어 온도를 측정한 전체 날짜 수, N이 10
10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 문제.누적합과 투 포인터를 이용하여 해결한다. 조건에 따라 start 포인터와, end 포인터가
정렬되어있는 두 배열 A와 B가 주어질 때, 두 배열을 합친 다음 정렬해서 출력하는 문제.배열 A의 인덱스를 가리키는 포인터와 배열 B의 인덱스를 가리키는 포인터를 둔다. 각 포인터가 가리키는 배열 값을 서로 비교해서 작은 값을 선택하여 출력한다. 이후 출력된 값을 가
링크드 리스트를 직접 구현하고, 이를 토대로 큐를 만들었다.링크드리스트를 직접 구현하고, 이를 기반으로 큐를 만들 때, header node와 tail node를 추가했다. header node의 data에 큐의 삽입 연산으로 들어간 node의 개수를 기록했다. tai
하나의 마을에서 최소 유지비 합을 갖는 길들을 찾는다. 그리고 그 길들 중 비용이 가장 큰 길을 제거하고 나머지 길들의 유지비 합을 구하면 된다.
우선 가장 먼저 해야할 일이 섬들에게 번호를 부여하는 것이다. 인접한 땅은 동일한 섬에 소속되어야 한다. 이를 구현하기 위해 BFS를 사용한다.다음으로 해야할 일은 섬들을 연결하는 다리를 만드는 것이다. 여기서 주의해야할 점은 섬을 연결할 때, 한 방향으로만 다리를 만
이분탐색으로 해결하는 것은 알겠는데, left와 right를 무엇으로 설정해야할까. 문제를 다시 읽어보자. 요구사항은 K개의 랜선들을 N개이상의 랜선으로 자를 때, 나올 수 있는 최대 길이를 구하는 것이다.(여기서 K <= N)다시 말해, 길이를 찾는 문제이므로
문제에서 원하는 것은 적어도 M미터의 나무를 가져가기 위해, 절단기에서 설정할 수 최대 높이다. 따라서 이분 탐색을 통해 찾아야 하는 값은 절단기의 높이다. 절단기의 높이는 최소 1부터 설정할 수 있으므로, left는 1로 설정한다. 그리고 right는 주어진 나무들
우리가 구해야하는 것은 배정된 예산들 중 최대 값을 구하는 것이다. 문제에서 언급한 것처럼, 총 예산이 한정적이기 때문에 지방의 예산 요청대로 배정할 수 없는 경우가 존재한다. 예산을 만족하면서, 배정된 지방의 예산 중 가장 큰 값은 어떻게 구할까. 바로 총 예산을 만
우리가 찾아야하는 답은 승률이 변하기 위한 최소 게임 판 수 이다. 따라서 최소 게임 판 수를 이분탐색으로 찾아본다.형택이가 앞으로 하는 게임은 전부 이기는 게임이다. 따라서 승률이 변하는 것은 승률이 오른다는 것을 의미한다. 반면, 아무리 게임을 많이 해도 승률이 전
회전 초밥에서 연속적으로 k개의 초밥을 선택하고, 각 초밥 번호를 집합에 넣는다. 집합의 특성상 중복되는 번호는 없다. 쿠폰 번호가 집합에 속하지 않는다면, 집합 크기 + 1 종류의 초밥을 먹었다. 쿠폰 번호가 집합에 속해있다면, 집합 크기종류의 초밥을 먹었다.시작점을
문제에서 요구하는 것은 수열에서 두 수를 선택했을 때, 차이가 M이상이면서 제일 작은 경우를 구하는 것이다. 두 수를 선택하는데 있어, 수열의 형태는 중요하지 않다. 따라서 정렬 후, 문제 유형에서 제시된 것 처럼 투 포인터로 해결한다. 주의해야할 점은 같은 수를 고르
먼저 소수들을 에라토스테네스로 찾는다. 그리고 1번째 피연산자를 바꿔가며, 연속적으로 더해본다.(사용되는 피연산자들은 모두 소수) 그리고 그 결과가 N과 같다면 경우의 수를 하나 추가한다. 연속적으로 소수를 더하는 과정에서 N을 넘어버리게 된다면, 연산을 중단한 후,
문제의 요구사항을 지키면서 스택에 문자를 넣으면 메모리 초과가 발생한다. 예를들어 9(9(9(9(9(9(9(9(99999(1)))))))))가 입력으로 들어온다고 하자. 문자열 '1'이 99만 x 9^8개 찍힌다. 계산해보니 약 42조 5천억이다. 문제의 메모리 제한이
정방향으로 순회하면서 어떻게하면 스택을 이용하여 문제를 해결할 수 있을까하며 30분동안 고민했지만 아이디어가 떠오르지 않았다. 그래서 역방향으로 순회해서 문제 해결을 시도했는데 됐다.배열의 마지막 원소를 stack에 삽입하고 그 다음 원소부터 역방향으로 탐색을 시작한다
투 포인터와 슬라이딩 윈도우를 이용해 해결한다. 처음 딱 1번, 연속된 k개 초밥을 선형탐색하여 초밥의 종류 수와 해당 종류를 몇개 먹었는지 카운트한다. 이후 lp, rp를 사용할 것이기 때문에, 반복문이 필요없다.lp와 rp를 각각 1증가 시키기전에 lp에서 먹은 초
문제의 요구사항대로 구현하면된다. 연속적으로 동일한 낮은 값을 갖는 원소 수를 세는 방법이 낮은 값이 왼쪽에 있을 때와 오른쪽에 있을 때, 세는 방법이 조금 다르다. 짧게 설명을 하면, 낮은 값이 왼쪽에 있을 때는 원소 수를 1증가 시키고, 다음 재귀함수로 넘어간다.
1번째 날에 호랑이가 떡을 먹은 개수를 a, 2번째 날에 떡을 먹은 개수를 b라고 하자. 그러면 3번째 날에 떡을 먹은 개수는 a+b, 4번째 날에 떡을 먹은 개수는 a+2b, 5번째 날에 떡을 먹은 개수는 2a+3b, 6번째 날에 떡을 먹은 개수는 3a+5b... 이
문제에서 제시된 내용대로 따라 구현하면된다. 블록 그룹의 경우 딕셔너리를 활용했다. key는 블록 그룹의 기준 블록을 가리키는 좌표이고 value는 해당 그룹에 속하는 블록들의 좌표들이 들어있는 리스트이다. 격자의 (0,0) 부터 (n-1, n-1)까지 순차적으로 탐색
최근에 화이자 1차 접종을 맞았다. 몸 상태가 별로인 상태에서, 내 자신을 테스트할 수 있었던 기회였다.불에 관한 정보를 배열에 저장하지 않고 딕셔너리에 저장했다. 딕셔너리의 key는 불이 있는 좌표고 value는 (질량, 속력, 방향)을 저장하는 리스트이다. val
주사위의 움직임에 집중해서 설명한다. 나머지 조건은 어렵지 않으므로 생략한다. 주사위는 아래와 같이 2차원 배열로 표현한다.여기서 밑면은 dice\[3]\[1]이다. 주사위를 만들었으니 주사위를 동서남북으로 움직여보자.주사위를 동쪽 방향으로 움직이면 주사위 윗면이 우측