백준 10713 - 기차 여행 시간 제한 1초, 메모리 제한 256MB # 조건 JOI나라에는 N개의 도시가 있고, 각 도시에 1,2,...,N까지의 번호를 갖고 있다. 그리고, 철도가 N-1개 있고, 각 철도에 1,2,...N-1의 번호를 갖고 있다. 철도 i (1 ≦ i ≦ N − 1)는 도시 i과 도시 i+1을 양방향으로 연결시키는 철도를 의미한다. JOI나라의 철도를 타는 방법에는, 티켓을 구입해 승차하는 방법과 IC카드로 승차하는 방법 두 가지가 존재한다. 철도 i에 티켓을 구입해 승차할 때는 Ai 원의 비용이 든다. 철도 i에 IC카드로 승차하는 경우에는 Bi 원의 비용이 든다. 하지만 IC카드로 철도를 탈 때는 IC카드를 미리 구입해둬야만 한다. 철도 i에서 쓸 수 있는 IC카드를 구입하는데..

백준 15684 - 사다리 조작 시간 제한 2초, 메모리 제한 512MB # 조건 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다. 초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다. 단, 두 가로선이 연속하거나 서로 접하면 안 된다. 또, 가로선은 점선 위에 있어야 한다. 위의 그림에는 가로선이 총 5개 있다. 가로선은 위의 그림과 같이 인접한 두 세로선을 연결해야 하고, 가로선을 놓을..

코드트리 - 술래 잡기 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai # 소요 시간 - 70분 # 접근 방법 구현하기 어려웠던 부분은 술래가 움직이는 달팽이 모양의 방향이었다. 정방향과 역방향으로 움직일 때 다음 위치를 미리 나타내줄까 고민하였지만 따로 catcher리스트를 관리하는게 편해보여 정의해주었다. 현재 i, 현재 j, 달팽이 인덱스, 방향, 진행한 칸 수 우선 달팽이 모양으로 움직이는 것을 잘 살펴보면, 현재 위치를 제외하고 1 1 2 2 3 3 4 4 칸씩을 가면서 방향을 회전한다. 조금 더 디테일 하게는 방향을 전환했을 때, 위나 아래..

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

코드트리 - 꼬리 잡기 # 소요시간 - 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방향 중 주어진 조건으로 이동해야 되는 곳을 찾아준다. 이 떄 주의해야 할 점은, 실시간으로 구슬의 위치를 옮겨주는 것이 아닌 저장을 해둔 뒤 빼야된..