백준 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카드를 구입하는데..

이번주 또한 807점의 점수로 마무리 할 수 있었다! 다음 주는 꼭 그 이상의 점수를 받는 걸 목표로 잡으면서 다음 주도 화이팅해야겠다. 이번 주는 S 기업 코딩테스트가 예정되어 있어서 대비할 겸 코드트리의 기출 문제를 여러개 풀어보았습니다. https://www.codetree.ai/training-field/frequent-problems/problems/maze-runner?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 그 중에 올해 상반기 문제 중 1개를 풀며 dx, dy를 ..

백준 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[현재 위치]에 인덱스를 넣어준다. 이동을 하였다면 현재 구슬의 정보를 업..