투투

접근 먼저 가로와 세로를 탐색해서 활주로가 가능한지 알아보기 위해 각 열의 세로 정보들을 N행에 이어 붙였다. 이후 각 행마다 활주로 건설이 가능한지 검사를 한다. 먼저 이전 인덱스의 값과 현재 인덱스의 값이 같을 때는 continue를 진행한다. 이전 인덱스와 현재 인덱스의 + 1 값이 같을 때는 내리막이되는 경사로를 설치할 수 있는지 검사하고 설치할 수 없다면 활주로가 안되는 것으로 간주한다. 이전 인덱스의 - 1과 현재 인덱스의 값이 같을 때는 오르막이되는 경사로를 설치할 수 있는지 검사하고 설치할 수 없다면 활주로가 안되는 것으로 간주한다. 경사로를 설치할 때는 범위를 벗어나거나 겹쳐서 사용하면 안되기 때문에 각 인덱스에 경사로 설치유무를 체크하고 맵을 벗어나는지 체크하여 경사로를 설치하도록 한다..

접근 X시간 비활성화 상태 -> X시간동안 활성화 -> 죽음, 활성화 후 1시간 동안 번식을 한다고 한다. 이를 구현하기 위해 다음과같이 접근하였다. 만약 X = 2 라고 해보자. X에 2를 곱하면 4가 되고 4초 = 초기상태 3초 = 비활성화 2초 = 활성화 1초 = 활성화 및 번식 0초 = 죽음 위와 같이 X에 2를 곱하면 X - 1이 되는 시점에 번식이 이루어진다. 이렇게 비활성화 -> 활성 -> 번식을 구현하였다. 이제는 동시에 같은 곳에 번식을 하려고할 때 X가 큰 것이 오도록 해야한다. 이를 위해 X순으로 내림차순 정렬 후에 X가 큰 것부터 처리하도록 하였다. 이를 통해 먼저 처리가 되어있거나 이미 줄기세포가 있다면 continue가 진행되어 더 낮은 X는 같은 곳에 번식이 되지 못하도록 구현..

문제 문자열 S의 부분 문자열이란, 문자열의 연속된 일부를 의미한다. 예를 들어, "aek", "joo", "ekj"는 "baekjoon"의 부분 문자열이고, "bak", "p", "oone"는 부분 문자열이 아니다. 문자열 S와 P가 주어졌을 때, P가 S의 부분 문자열인지 아닌지 알아보자. 입력 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다. 출력 P가 S의 부분 문자열이면 1, 아니면 0을 출력한다. 접근 kmp 알고리즘을 적용하여 부분 문자열을 찾았다. 인덱스 i는 S, 인덱스 j는 P를 가리킨다고 했을 때 S의 길이만큼 i가 순차적으로 증가한다. j는 0부터 시작하여 S[i] == ..

접근 두 명의 일꾼이 각각 가로로 연속으로 M개의 벌통을 선택한다. 이때 두 명의 일꾼이 선택한 벌통이 겹치면 안된다. => 이는 2차원 리스트의 완전탐색을 통해 두 명의 일꾼이 벌통을 선택하는 경우의 수를 구할 수 있을 것이다. 선택한 M개의 벌통 중에서 가중치가 가장 큰 것을 찾아야한다. 예를 들어 5, 5, 9 벌통을 선택했고 C가 10이라고 하자. 그렇다면 최대 수익을 위해 5, 5가 아닌 9를 선택해야한다. => itertools의 combinations를 활용하여 선택한 벌통 중에 최대수익을 찾는다. 구현 - 벌통을 2개 선택했을 때 최대수익을 구한다. - 두 명의 일꾼이 선택한 벌통(storage[0], storage[1])에서 combinations를 통해 최대수익을 구한다. - 이를 re..

https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net 접근 문자열 패턴을 찾는 알고리즘인 KMP를 공부하기위해 위의 문제를 풀었다. 일단 지금까지 KMP 알고리즘을 다음과같이 이해했다. 문자열 S에서 패턴 문자 P를 찾는다고 하자. 이를 S의 처음부터 탐색하고 다른 문자가 나왔을 때 다시 P의 처음부터 탐색을 하면 불필요한 중복이 발생한다. 따라서 P에서 각 인덱스까지의 문자까지 (ABCD가 있을 때 A, AB, ABC, ABCD) 최대 접미사..

첫 번째 접근 모든 위치에 대해 BFS를 진행하였다. BFS를 하면서 집의 개수를 카운트하였고 집의 개수 x M이 운영비용보다 같거나 클 때 최댓값 비교를 진행했다. PASS는 되었지만 시간이 오래 걸렸고 불필요한 곳까지 탐색한다는 것을 알았다. 첫 번째 구현 - K를 N+1 ~ 1까지 탐색하면서 모든 좌표에 대해 BFS를 진행한다. - BFS는 현재 위치를 기준으로 거리를 통해 방문표시를 한다. - 거리가 K이하일 때만 큐에 넣어 다음 위치를 탐색할 수 있도록 하였다. => 마름모 형태 - 이후 현재 위치가 집일 경우 집의 개수인 count를 증가시켰다. - BFS가 종료되고 count x M이 운영 비용보다 크거나 같을 때 최댓값 비교를 한다. from collections import deque d..

문제 마야 문자를 해독하는 일은 예상 외로 어려운 일이다. 현재에도 뜻이 완전히 밝혀진 마야 문자는 거의 없는 실정이며, 그나마 해독에 진척이 시작된 지는 30여 년도 되지 않았다. 마야 문자는 소리를 나타내는 여러 종류의 그림글자로 구성되는데, 이 글자들이 여러 위치에서 결합함으로써 단어를 형성한다. 마야 문자 해독을 어렵게 하는 요인 중 하나는 바로 단어를 읽는 순서이다. 마야 문자를 쓰는 고대인들은 단어를 기록할 때 특정한 규칙 대신, 그들이 보기에 좋게 보이도록 단어를 이루는 글자들을 아무렇게나 배열했다. 그렇기 때문에 고고학자들이 마야 기록에서 단어를 이루는 각 그림글자들의 발음을 알아내더라도 그 단어를 실제로 발음하는 방법은 정확히 알 수 없는 셈이다. 고고학자들은 W라는 특정 단어를 발굴 기..

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 접근 이 문제는 CCTV의 방향을 어떻게 설정할 것인지가 관건이었다. 각각의 CCTV에 따라 감시할 수 있는 방향을 딕셔너리 형태로 선언해주었다. 이후 CCTV의 개수만큼 DFS를 하여 해당 CCTV를 감시할 수 있는 방향을 모두 탐색할 수 있도록하였다. 결론적으로 CCTV의 방향을 어떻게 모델링할 것인지와 DFS를 통한 완전탐색으로 접근하였다. 구현 - CCTV의 위치와 번호를 cct..

문제 회전 초밥 음식점에는 회전하는 벨트 위에 여러 가지 종류의 초밥이 접시에 담겨 놓여 있고, 손님은 이 중에서 자기가 좋아하는 초밥을 골라서 먹는다. 초밥의 종류를 번호로 표현할 때, 다음 그림은 회전 초밥 음식점의 벨트 상태의 예를 보여주고 있다. 벨트 위에는 같은 종류의 초밥이 둘 이상 있을 수 있다. 새로 문을 연 회전 초밥 음식점이 불경기로 영업이 어려워서, 다음과 같이 두 가지 행사를 통해서 매상을 올리고자 한다. 원래 회전 초밥은 손님이 마음대로 초밥을 고르고, 먹은 초밥만큼 식대를 계산하지만, 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공한다. 각 고객에게 초밥의 종류 하나가 쓰인 쿠폰을 발행하고, 1번 행사에 참가할 경우 이 쿠폰에 적혀진 종류의..

문제 윤호는 퍼주기로 유명한 편의점 사장이다. 그의 편의점에는 특이한 임금 체계를 가지고 있다. 각 날마다 일의 차이때문에 일마다 급여가 정해져 있다. 윤호는 오차 없이 일급을 따박 따박 당일에 준다. 정해진 일 수 만큼만 일을 시킨다. 한번이라도 퇴직한 자를 다시 취직 시키지 않는다. (만약 취직을 한다면, 일을 시작 한 날부터 끝날 때까지 하루도 빠지면 안 된다.) 무서운 아르바이트를 짤린 준수는 n+1일 후에 001에 월세를 내야 해서 윤호가 사장으로 있는 편의점에 취직하려 한다. 다행히 주변 퇴직자들의 얘기로 급여에 관련해 파악했다. 또한 퇴직자들의 급여 통계를 통해 당장 n일 후까지 일급 정보를 알아냈다. 하지만 준수는 시험을 준비해야 하기에 최대 m일 밖에 일을 할 수 없다. 어제까지 과제를 ..