백준 15558 - 점프 게임시간 제한 2초, 메모리 제한 512MB# 조건상근이는 오른쪽 그림과 같은 지도에서 진행하는 게임을 만들었다.지도는 총 2개의 줄로 나누어져 있으며, 각 줄은 N개의 칸으로 나누어져 있다. 칸은 위험한 칸과 안전한 칸으로 나누어져 있고, 안전한 칸은 유저가 이동할 수 있는 칸, 위험한 칸은 이동할 수 없는 칸이다.가장 처음에 유저는 왼쪽 줄의 1번 칸 위에 서 있으며, 매 초마다 아래 세 가지 행동중 하나를 해야 한다.한 칸 앞으로 이동한다. 예를 들어, 현재 있는 칸이 i번 칸이면, i+1번 칸으로 이동한다.한 칸 뒤로 이동한다. 예를 들어, 현재 있는 칸이 i번 칸이면, i-1번 칸으로 이동한다.반대편 줄로 점프한다. 이때, 원래 있던 칸보다 k칸 앞의 칸으로 이동해야 한..

백준 16508 - 전공책시간 제한 1초, 메모리 제한 512MB# 조건곧 졸업을 앞둔 민호는 대학교 생활 동안 구매만 해놓고 한 번도 펴보지 않은 전공책에 먼지가 쌓여 있는 것을 보고는, 이 책들을 어떻게 처리해야 할지 고민 중이다. 열심히 고민한 끝에 민호는 결국 전공책을 모두 버리기로 마음먹었다. 하지만 그냥 버리기엔 심심한 민호는 전공책 제목에 있는 글자들을 오려서 단어 만들기 놀이를 하려고 한다. 단어 만들기 놀이는 아래 예시와 같다.1번 책 : COMPUTERARCHITECTURE (35,000원)2번 책 : ALGORITHM (47,000원)3번 책 : NETWORK (43,000원)4번 책 : OPERATINGSYSTEM (40,000원)만약 민호가 만들고 싶은 단어가 ALMIGHTY라고 ..

백준 11048 - 이동하기시간 제한 1초, 메모리 제한 256MB# 조건준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다.준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으로 나갈 수는 없다.준규가 (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값을 구하시오.# 접근 방법딱 보자마자 시간 초과를 안 당하기 위해서는 dp로 접근해야 겠다고 ..

백준 1747 - 소수&팰린드롬시간 제한 2초, 메모리 제한 256MB# 문제어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다.어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다.출력첫째 줄에 조건을 만족하는 수를 출력한다.# 접근 방법우선 소수를 구해주었다.이 때 주의할 점은 100001까지가 아닌, 1000000보다 크거나 같은 소수 중 팰린드롬인 수까지 구해야 하므로 여유있게 1500000까지 구해주었다.이후, bisect를 이용하여 N이 들어갈 index를 구해서 해당..

백준 - 2559_수열시간 제한 1초, 메모리 제한 128MB# 문제입력첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다.첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다.N은 2 이상 100,000 이하이다.두 번째 정수 K는 합을 구하기 위한 연속적인 날짜의 수이다.K는 1과 N 사이의 정수이다.둘째 줄에는 매일 측정한 온도를 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다.이 수들은 모두 -100 이상 100 이하이다.출력첫째 줄에는 입력되는 온도와 수열에서 연속적인 K일의 온도의 합이 최대가 되는 값을 출력한다.# 접근 방법누적합과 투 포인터를 활용해주면 된다.우선 입력받은 온도의 누적합을 cumulative_sum에 저장해준 후 0번 인덱스에 0을 삽입해..

코드트리 - 고대 문명 유적 탐사 # 소요 시간 : 2시간 # 접근 방법 설계를 대충했더니 디버깅 하기 힘들었던 문제였다. 마주했던 큰 문제 2개는 new_arr과 temp_arr 간의 얕은 복사, 90도씩 회전시킨 배열을 저장해주지 않은 점이었다. 우선 탐색을 시작하며, 가장 큰 1차 유물 획득 최대 값을 비교해줄 변수들을 선언해주었다. 또한, 원본 배열을 temp_arr에 deepcopy해주고 (0,0) 부터 (2, 2)까지를 왼쪽 상단으로 설정한 뒤 before_rotate에 복사해준다. 90도씩 총 3번 회전을 시키며 after_rotate에 저장해주고 before_rotate를 after로 갱신해준다. temp_arr에 after_rotate의 결과를 적용시켜주고 gain_score 함수를 실행..

코드트리 - 나무 타이쿤 소요 시간 : 30분 # 접근 방법 구현, 시뮬레이션 유형 중 기본적인 문제라고 생각한다. 문제에서의 핵심은 영양제가 이동할 때 격자가 이어진다는 점(0과 N-1)과 주어지는 이동 칸 수를 N으로 나눈 나머지로 변경해주는 것이라 생각한다. 주어지는 로직 대로 아래 함수들을 사용하여 풀었다. move_m(d, al) 이동시킨 위치를 기록한 temp 빈 리스트를 생성해주고 loc_m을 순회해준다. 영양제의 다음 위치는 (전체 길이 N + 현재 위치 + 이동할 방향 * 칸수를 더한 뒤 N으로 나눈 나머지)로 구해주었다. temp에 append 해준 후 모든 순회가 끝나면 temp를 리턴해준다. grow_l(temp) 위 함수에서 return 받은 이동 후의 위치를 순회하며 먼저 +1씩..

코드트리 - 정육면체 한번 더 굴리기 소요시간 : 1시간 30분 # 접근 방법 구현 문제 중에는 조금 쉬운 편이었던거 같다. 문제에서 중요한 점은 주사위의 상,하,좌,우,앞,뒤를 헷갈리지 않고 잘 기록하는 것이다. move_dice 함수를 시작하면서 다음 위치를 결정해준다. 이 때, 격자를 벗어나게 되면 방향을 +2 % 4를 통해 반대방향으로 돌려주고 ni, nj를 dice_i, dice_j에 기록해준다. bfs를 통해서 이번 턴에 얻게 되는 점수를 score에 더해주고 주사위를 돌려준다. 직전의 진행 방향에 따라, 주사위의 상, 하, 좌, 우, 앞, 뒤의 값을 변경해주고 주사위의 아랫면과 격자의 값을 비교하여 다음 방향도 결정해주면 된다. import sys sys.stdin = open('input...

코드트리 - 팩맨 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 소요시간 : 3시간 30분 # 접근 방법 첫 풀이가 맞왜틀로 계속 헤매었던 문제였는데 사실 시간 초과가 발생했을 것 같다. 2시간이 경과한 후에 다시 로직을 점검하면서 코드를 수정하여 맞출 수 있었다. 처음엔 모든 칸을 빈 리스트로 만든 후, 몬스터들의 방향으로 추가해주었지만, 변경 후엔, 각 칸을 8 크기의 리스트로 만든 후 각 방향에 몬스터들의 수로 기록해주었다. 또한, 시체 존재 유무를 위한 4x4 크기의 리스트를 생성해주었다. T턴 동안 아래 로직으로 진행하였다. 몬스터 복제를 ..