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

백준 17396 - 백도어 시간 제한 2초, 메모리 제한 512MB # 조건 유섭이는 무척이나 게으르다. 오늘도 할 일을 모두 미뤄둔 채 열심히 롤을 하던 유섭이는 오늘까지 문제를 내야 한다는 사실을 깨달았다. 그러나 게임은 시작되었고 지는 걸 무척이나 싫어하는 유섭이는 어쩔 수 없이 백도어를 해 게임을 최대한 빠르게 끝내기로 결심하였다. 최대한 빨리 게임을 끝내고 문제를 출제해야 하기 때문에 유섭이는 최대한 빨리 넥서스가 있는 곳으로 달려가려고 한다. 유섭이의 챔피언은 총 N개의 분기점에 위치할 수 있다. 0번째 분기점은 현재 유섭이의 챔피언이 있는 곳을, N-1 번째 분기점은 상대편 넥서스를 의미하며 나머지 1, 2, ..., N-2번째 분기점은 중간 거점들이다. 그러나 유섭이의 챔피언이 모든 분기점..

백준 19699 - 소-난다! 시간 제한 1초, 메모리 제한 1024MB # 조건 지난 번 헛간 청약의 당첨우(牛)가 발표됐다. 청약에 당첨된 소들은 날아갈 듯이 기뻐하다가 진짜로 하늘을 날았다. 하지만 이후로 소들은 날 수 없었다. 그러던 어느 날, 꿀벌에게 쏘이면 잠깐 하늘을 날 수 있다는 사실을 깨달았다. 이 사실이 퍼지자 소들은 다시 자유롭게 하늘을 날기 시작했다. 소들이 하늘을 날며 우(牛)통사고가 빈번해지자, 농부 존은 소들이 하늘을 나는 것에 제한을 두었다. 소들은 항의했지만 소들의 항의는 받아들여지지 않았다. 농장에는 $N$마리의 소가 있다. 농부 존은 소들의 몸무게의 합이 소수(prime)가 되도록 $M$마리의 소를 선별할 계획이다. 농부 존의 계획에 맞게 소를 선별했을 때 나올 수 있는..

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

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

지난 주와 비슷한 문제에서 틀려 같은 점수를 받았습니다. 곧 있을 삼성 sw 역량 평가에 대비한다고 구현 문제를 위주로 풀었더니.. +1 -1, two pointer와 같은 테크닉이 새롭게 보이더라구요..! 그래서 이번주는 Two Pointer에 대해 개념을 다시보고 문제를 풀어보았습니다. 다른 코딩 테스트 뿐만 아니라, 효율적인 탐색을 하는데 있어 자주 등장하는 유형이므로 꼭 이번 기회에 마스터하겠습니다. https://www.codetree.ai/missions/8/problems/shortest-subtotal?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합..

백준 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번 땅에 위치해 있다. 오리들이 서있는 순서대로 원하는 땅을 가지도록 한다. 만약, 한 오리가 원하는 땅까지 가는 길에 이미 다른 오리가 점유한 땅이 있다면 막대한 세금을 내야 하는 이유로 해당 땅을 지나가지 못해 그 오리는 땅을..