본문 바로가기

분류 전체보기448

[Python] 파이썬 순열/중복순열/조합/중복조합 구현 코드 (Backtracking 활용) 1) 순열def permutations(arr, k): cases = [] visited = [False]*(len(arr)) def dfs(elements): if len(elements) == k: cases.append(elements) return for i in range(len(arr)): if not visited[i]: visited[i] = True dfs(elements + [arr[i]]) visited[i] = False dfs([]) return casesp.. 2024. 10. 13.
[삼성 SW 역량테스트 기출] 메이즈 러너 # M명의 참가자가 미로 탈출하기 게임에 참가# 미로는 N×N 크기의 격자# # 1초마다 모든 참가자는 한 칸씩 움직입니다.# 두 위치 (x1,y1), (x2,y2)의 최단거리는 ∣x1−x2∣+∣y1−y2∣로 정의# 모든 참가자는 동시에 움직입니다.# 상하좌우로 움직일 수 있으며, 벽이 없는 곳으로 이동할 수 있습니다.# 움직인 칸은 현재 머물러 있던 칸보다 출구까지의 최단 거리가 가까워야 합니다.# 움직일 수 있는 칸이 2개 이상이라면, 상하로 움직이는 것을 우선시합니다.# 참가가가 움직일 수 없는 상황이라면, 움직이지 않습니다.# 한 칸에 2명 이상의 참가자가 있을 수 있습니다.# # 모든 참가자가 이동을 끝냈으면, 다음 조건에 의해 미로가 회전합니다.# 한 명 이상의 참가자와 출구를 포함한 가장 .. 2024. 10. 12.
[백준 16985번] Maaaaaaaaaze https://www.acmicpc.net/problem/16985# 5×5 크기의 판이 5개 # 이중 일부 칸은 참가자가 들어갈 수 있고 일부 칸은 참가자가 들어갈 수 없다.# 참가자는 주어진 판들을 시계 방향, 혹은 반시계 방향으로 자유롭게 회전할 수 있다. # 회전을 완료한 후 참가자는 판 5개를 쌓는다.# 판을 쌓는 순서는 참가자가 자유롭게 정할 수 있다.# 이렇게 판 5개를 쌓아 만들어진 5×5×5 크기의 큐브가 바로 참가자를 위한 미로# 입구는 정육면체에서 참가자가 임의로 선택한 꼭짓점에 위치한 칸# 출구는 입구와 면을 공유하지 않는 꼭짓점에 위치한 칸# 참가자는 현재 위치한 칸에서 면으로 인접한 칸이 참가자가 들어갈 수 있는 칸인 경우 그 칸으로 이동할 수 있다.# 참가자 중에서 본인이 설계.. 2024. 10. 11.
[삼성 SW 역량테스트 기출] 마법의 숲 탐색 https://www.codetree.ai/training-field/frequent-problems/problems/magical-forest-exploration/description?page=1&pageSize=5 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai# 숲의 동쪽, 서쪽, 남쪽은 마법의 벽으로 막혀 있으며, 정령들은 숲의 북쪽을 통해서만 숲에 들어올 수 있습니다.# 총 K명의 정령은 각자 골렘을 타고 숲을 탐색# 각 골렘은 십자 모양의 구조를 가지고 있으며, 중앙 칸을 포함해 총 5칸을 차지# 골렘의 중앙을 제외한 4칸 중 한 칸은 골렘의.. 2024. 10. 9.
[백준 2212번] 센서 https://www.acmicpc.net/problem/2212import sysimport heapqinput = sys.stdin.readline# 고속도로 위에 N개의 센서를 설치# 고속도로 위에 최대 K개의 집중국을 세울 수 있다# 각 집중국은 센서의 수신 가능 영역을 조절할 수 있다# 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다# N개의 센서는 적어도 하나의 집중국과는 통신이 가능해야함# 각 집중국의 '수신 가능 영역의 길이의 합'을 최소화# 고속도로는 평면상의 직선이라고 가정# 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다# 따라서, 각 센서의 좌표는 정수 하나로 표현# 단, 집중국의 수신 가능영역의 길이는 0 이상이며 모든 센서의.. 2024. 10. 5.
[백준 18428번] 감시 피하기 https://www.acmicpc.net/problem/18428import sysimport copyinput = sys.stdin.readline# NxN 크기의 공간에 선생님(T), 학생(S), 혹은 장애물(O)이 위치# 복도로 빠져나온 학생들은 선생님의 감시에 들키지 않는 것이 목표# 각 선생님들은 자신의 위치에서 상, 하, 좌, 우 4가지 방향으로 감시를 진행# 선생님은 상, 하, 좌, 우 4가지 방향에 대하여, 아무리 멀리 있더라도 장애물로 막히기 전까지의 학생들은 모두 볼 수 있다# 단, 복도에 장애물이 위치한 경우, 선생님은 장애물 뒤편에 숨어 있는 학생들은 볼 수 없다# 학생들은 복도의 빈 칸 중에서 장애물을 설치할 위치를 골라, 정확히 3개의 장애물을 설치# 결과적으로 3개의 장애물을.. 2024. 10. 5.

티스토리툴바