코드트리 - 나무박멸 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai # 소요시간 : 100분 # 접근 방법 구현, 시뮬레이션 문제로서 의사 코드를 탄탄히 작성하는데 집중하였다. 우선 주어진 조건을 정리하며 아래 키 포인트를 위주로 고민하였다. 나무들이 동시에 움직이며, 나무가 성장한 후 번식을 한다는 점 제초제는 가장 많은 나무가 박멸되는 위치에 뿌리고, 빈 칸을 만나는 경우에도 제초제를 뿌리고 종료하는 것 제초제는 c년만큼 남아있고, 다시 뿌리면 c년으로 초기화된다는 점이다. 제초제를 따로 리스트에 보관하지 않고 주어진 arr에 기록하기 위하여 입..

코드트리 - 꼬리 잡기 # 소요시간 - 100분 # 접근 방법 s 기업 코딩테스트 대비 구현, 시뮬레이션 문제를 풀게 되었다. 문제를 읽으면서 주어진 조건을 요약하고 의사 코드로 작성하면서 눈 여겨본 중요한 키포인트는 아래와 같았다. 사람들을 주어진 경로로 이동시키기 라운드에 따른 공을 던지는 시작점과 방향 공을 맞은 사람의 순서와 뒤집기 따라서, 각 팀의 사람들의 위치를 기록할 team_loc리스트와 머리의 위치를 기록할 team_head 딕셔너리를 사용해주었다. 주어진 배열을 순회하며 1을 만나는 경우 idx를 팀 번호로 사용하여 bfs 함수를 실행시켜 각 팀의 머리 ~ 꼬리 순서로 기록해주었다. 이 때, 3을 만난 경우는 따로 temp에 저장해둔 후 마지막에 추가해주었다. 2 1 3이나 3 1 2와..

코드트리 - 합쳐지는 구슬들 # 접근 방법 이동 후 같은 칸에 2개 이상이 존재하는 경우 합치는 것이 문제 해결의 키포인트이다. 우선 벽에 부딪혔을 경우 방향을 반대로 해주기 편하게 di, dj = [1, 0, -1, 0]과 같이 인덱스 2 차이가 나도록 설정해준다. 입력받는 모든 구슬을 순서대로 marbles 리스트에 저장해주는데, 방향을 숫자로 변환해서 넣어준다. 또한 구슬이 이동하고 난 후의 위치를 저장할 location리스트를 빈 크기로 격자 크기와 동일하게 만들어 준다. move 함수 주어진 구슬들을 순회하면서 값이 존재한다면 주어진 방향을 더해준다. 만약 격자를 벗어난다면 (d+2) % 4를 통해 전환 후 location[현재 위치]에 인덱스를 넣어준다. 이동을 하였다면 현재 구슬의 정보를 업..

코드트리 - 숫자가 가장 큰 인접한 곳으로 동시에 이동 ## 소요시간 30분! # 접근 방법 침착하게 문제에서 원하는 조건을 우선 정리해주었다. 구슬은 상하좌우 가장 큰 곳으로 이동하며, 그러한 값이 여러 개일 경우 상하좌우 방향 순서대로 이동한다. 또한, 구슬은 충돌하지 않고 *이동한 후에 * 2개 이상의 구슬 위치가 동일하다면 해당 위치의 구슬은 소멸한다. 따라서, marbles 리스트를 주어진 입력 리스트의 크기와 동일하게 만들어주고, 초기의 구슬 위치를 1로 표시해준다. 이후 t초 동안 marbles를 순회하며 구슬이 존재한다면 입력받은 arr에서 4방향 중 주어진 조건으로 이동해야 되는 곳을 찾아준다. 이 떄 주의해야 할 점은, 실시간으로 구슬의 위치를 옮겨주는 것이 아닌 저장을 해둔 뒤 빼야된..

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

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

코드트리 - 핀볼게임 풀이시간 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번째 열 기준 진행을 해주면 된다. 주의할 점은, 들어가는 시간과 나오는 시간을 포함해주어야 한다는 것과 시작 위치마다 핀볼의 시작 진행 방향이 다르다는 것이다. 들어갈 때부터 카운트를 해주고 이동하는 것을 편하게 하기 위하여..

코드트리 - 최적의 십자 모양 폭발 # 접근 방법 완전 탐색을 활용한 시뮬레이션 문제이다. 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()..