돌 게임 문제는 DP로 쉽게 풀 수 있지만 미니맥스 알고리즘을 사용한 풀이도 가능합니다. 미니맥스 알고리즘 풀이를 찾아봤지만 없어서 직접 구현했습니다. 미니맥스 알고리즘은 서로 게임에 최선을 다하는 알고리즘입니다. 나는 상대방에게 이득이 되는 행동을 하지 않고 상대방도 나에게 이득이 되는 행동을 하지 않도록 탐색하는 알고리즘입니다. minimax(stone, player) 함수는 남은 돌의 개수(stone)과 나 또는 상대방인지를 알 수 있는 player 인자를 갖습니다. 마지막 돌을 가져가는 사람이 지는 것이므로 내가 마지막 돌을 가져가면 0(내가 지면), 상대방이 가져가면(내가 이기면) 1을 반환하도록 작성했습니다. 이제 내가 돌을 (1 or 3 or 4)개를 가져간 후 상대방의 리턴 값은 0(내가 ..
2023 삼성 상반기 코딩테스트 오후 2번 문제입니다. TLE를 해결하지 못해 다른 사람의 풀이를 보고 계속 코드를 고쳐가면서 문제를 풀었습니다. 단순한 구현이 아닌 적절한 자료구조를 사용하고 한번 더 생각해야 해서 개인적으로 잘 만든 문제라고 생각합니다. 우선 어떠한 task가 채점이 될 수 없는 조건은 다음과 같습니다. - 해당 task의 도메인이 현재 채점을 진행중인 도메인 중 하나라면 불가능합니다. - 해당 task의 도메인과 정확히 일치하는 도메인에 대해 가장 최근에 진행된 채점 시작 시간이 start, 종료 시간이 start+gap 였고 현재 시간 t가 start+3×gap 보다 작다면, 부적절한 채점이라 의심되기에 채점이 불가합니다. 채점기로 들어가는 위의 조건때문에 url을 검사해야 합니다..
2023 삼성 상반기 코딩테스트 오후 1번 문제입니다. 출구와 가장 가까운 사람을 포함하는 정사각형 범위를 찾고 이를 회전해야 합니다. 이때 정사각형 범위 내 사람이 있는 경우 같이 회전시켜야 합니다. 정사각형을 찾는 코드는 반복문을 사용했는데 (10,10)인 보드에서 최대 크기 10인 사각형을 찾는 코드라서 크게 시간을 잡아먹지 않는다고 생각했습니다. 그리고 거리가 abs(x1-x2)+abs(y1-y2)로 정의되어 있어 bfs나 dfs를 사용하지 않고도 사람을 이동시킬 수 있습니다. 출구와 같은 거리를 가진 경로가 여러개라면 행 -> 열 방향으로 우선순위를 적용해야 합니다. HTML 삽입 미리보기할 수 없는 소스
성격 유형 검사하기 그냥 구현하면 됩니다. HTML 삽입 미리보기할 수 없는 소스 두 큐 합 같게 만들기 생각보다 헷갈릴 수 있는 문제라고 생각합니다. queue1, queue2의 길이가 최대 300,000이므로 이중for문으로 탐색하면 TLE를 발생시킵니다. 따라서 두 큐를 합쳐 투포인터로 탐색하여 문제를 해결할 수 있습니다. i와 j 포인터는 i ≤ j < len(queue1+queue2)의 조건을 가지고 탐색하는데 이때 몇 가지 경우를 생각해볼 수 있습니다. 첫 번째는 두 포인터가 queue1에서 모두 위치한 경우입니다. 뒤쪽의 j 포인터가 가리키는 값까지 모두 queue2로 옮기고 원래 queue2에 있던 값들과 queue1의 i 포인터 앞까지 queue1으로 옮겨야 하므로 (j+1)+i+len..
신고 결과 받기 그대로 구현하면 됩니다. HTML 삽입 미리보기할 수 없는 소스 k진수에서 소수 개수 구하기 문제에서 주어진대로 n을 k진수로 변환하고 0과 0사이의 수가 소수인지 판별하면 됩니다. python에서 int(), bin() 등과 같이 k진수법으로 표현된 수를 10진수로 변환하는 함수는 있지만 10진수를 k진법으로 표현하는 함수는 없으므로 직접 구현해야 합니다. 변환하는 방법은 10진수를 2진수로 바꾸는 방법처럼 계속 나눠 나머지를 뒤에 추가하여 구현할 수 있습니다. def conv(n,k): base = '' while n > 0: n, mod = divmod(n, q) base += str(mod) return base[::-1] """ tc1 : n = 437674, k = 3 ----..
생각보다 어려운 문제였습니다. 트랙위에 사람이 트랙을 따라가는 것을 구현하기 위해 트랙 전부를 저장하여 회전하는 것으로 구현했습니다. 예를들면, 첫 번째 예시 왼쪽 상단의 트랙에 대해 person=[1,2,3,4,4,4,4,4], track=[(0,2),(0,1),(0,0),(1,0),(2,0),(2,1),(2,2),(1,2)]으로 저장하고 person 배열을 [2,3,4,4,4,4,1]로 회전시키면 트랙위에 사람이 움직인 것과 같습니다. HTML 삽입 미리보기할 수 없는 소스
문제를 그대로 구현하면 됩니다. 어떤 사람이 원하는 편의점에서 가장 가까운 베이스캠프를 지정할 때 이전 사람들이 지정한 베이스캠프를 지나지 못하도록 주의해야 합니다. 따라서 베이스캠프 위치를 정할때는 미리 정하지 않아야 합니다. HTML 삽입 미리보기할 수 없는 소스
문제에 주어진 과정을 그대로 따라가면서 구현하면 됩니다. 처음에는 땅에 하나의 총이 떨어져 있거나 없는 경우가 있지만 라운드를 거치면서 한곳에 여러개의 총이 떨어져 있을 수 있음을 알아야 합니다. HTML 삽입 미리보기할 수 없는 소스
디버깅이 힘든 문제입니다. 그리고 술래가 바라보는 방향을 따로 저장해두는 것이 편했습니다. 도망자가 움직이는 move 함수, 술래가 잡은 도망자의 수를 리턴하는 check 함수, 술래가 바라보는 방향을 계산하는 indexing_m 함수와 m_reverse 함수로 구성했습니다. 술래는 달팽이 방향으로 움직이며 움직이는 방향으로 바라봅니다. 그러나 코너 위치에서 술래는 이동하자마자 방향을 바꿔버리기 때문에 이를 반영해야 합니다. # 상 : 0 # 우 : 1 # 하 : 2 # 좌 : 3 # 정방향 2 1 1 1 2 0 0 1 2 2 0 0 0 2 2 0 0 3 3 2 0 3 3 3 3 # 역방향 2 2 3 3 3 2 2 2 3 0 2 2 0 0 0 2 1 1 0 0 1 1 1 1 0 HTML 삽입 미리보기할 ..
이 문제는 3가지의 함수로 구현할 수 있습니다. 첫 번째는 구슬을 이동하는 move 함수, 두 번째는 연속된 구슬을 폭발시키는 explode 함수, 마지막으로 구슬을 새롭게 배치시키는 make_bids 함수입니다. 구현 시 주의할 점은 구슬이 달팽이 모양으로 배치된 점인데 이는 map와 같이 구슬의 위치에 인덱스를 부여하면 인덱스에 접근하는 것으로 달팽이처럼 구슬에 접근할 수 있게 됩니다. HTML 삽입 미리보기할 수 없는 소스
