728x90 반응형 코테8 [Python] 고대 문명 유적 탐사: 삼성SW역량테스트 2024 상반기 오전 1번 고대 문명 유적 탐사: 삼성SW역량테스트 2024 상반기 오전 1번Information자료구조: 2차원 배열, 큐(queue)알고리즘: BFS, 행렬 돌리기 테크닉, 정렬Setup(5, 5) 행렬을 `box`라고 이름 지었다. 전역변수로 선언함.(1) 탐사 진행: `(row, col)`을 기준으로 2차원 (3, 3) 배열을 90도 회전시킬 함수가 필요할 것 같다. 수험자 배려인지 행렬의 가장자리에서는 회전을 하지 않는다. 그러니가 (4번의 회전) x (9개의 회전축) = 36번 탐색하면 된다.(2) 유물 획득: `box[i][j]`마다 같은 숫자가 있는지 BFS로 탐색한다. 그중에서 조각이 3개 이상인 경우에만 유물을 획득한다. BFS 함수 마지막에 유물 조각의 개수도 담고 있어야 할 것 같다. 그리고 .. 2024. 10. 13. [Python] 코드트리 투어: 삼성SW역량테스트 2024 상반기 오전 2번 코드트리 투어: 삼성SW역량테스트 2024 상반기 오전 2번 Information자료구조: 그래프, 힙(우선순위 큐)알고리즘: 다익스트라Query이 문제는 다양한 쿼리가 인풋으로 들어온다.그래프를 만드는 쿼리 빼고 4개의 쿼리에 대해 처리해야한다.(1) 랜드 건설: 가중치 그래프를 만드는 쿼리이다. 맨 처음 인풋으로만 들어온다.(2) 여행 상품 생성: 현재 출발지 기준으로 매출, 도착지 정보를 바탕으로 수익을 계산한다.(3) 여행 상품 취소: 특정 상품 id가 (2)로 생성되어있다면, 취소한다.(4) 최적 상품 판매: 수익이 가장 큰 상품을 판매하고, 그러한 상품이 없다면 -1을 출력(5) 상품 출발지 변경: 출발지를 새로운 출발지로 변경한다. (2)에서 생성된 정보 업데이트가 필요하다.Setup필요한 .. 2024. 9. 21. [Python] 루돌프의 반란: 삼성SW역량테스트 2023 하반기 오후 1번 루돌프의 반란: 삼성SW역량테스트 2023 하반기, 오후 1번 해설/힌트 없이 채점 테스트 케이스만 보고 3시간 30분 걸렸다.진짜 시뮬레이션 구현이 복잡했다특히 산타끼리의 '상호작용'을 for-loop으로 구했다가 while로 고쳤다 오답이 나는 케이스1. 루돌프가 움직일 때산타를 찾아가는 우선순위가 제대로 되어있는가?산타와 충돌했을 때, 산타가 밀리는 방향이 바뀌진 않았는가? (바뀌면 안된다)2. 산타(들)가 움직일 때상우하좌 순서를 지켰는가?루돌프와 가까워지지 않으면 정지하는가?루돌프와 충돌 후 다른 산타들과 '상호작용'이 제대로 구현이 되었는가?루돌프와 충돌 후 제자리로 돌아올 때에도 상호작용을 하고 있는가? (하면 안된다)상호작용이 끝난 후, 올바르게 위치가 업데이트 되었는가? (덮어쓰기 순서 .. 2024. 9. 20. 최소 공통 조상 (Lowest Common Ancestor, LCA) 최소 공통 조상 (LCA) 알고리즘Problem Setup$N$개의 node로 이루어진 트리가 주어진다. (트리이므로 간선의 개수는 $N-1$개이다)$q$개의 query에 대하여 두 node사이의 거리를 계산한다. 위 그림은 백준 11437 LCA 문제이다. 1번 노드가 루트이다.6번과 11번 노드의 최소 공통 조상은 2번 노드이다. (1번 노드 역시 공통 조상이지만, 최소가 아니다.)10번과 9번 노드의 최소 공통 조상은 4번이다. 즉, LCA(10, 9) = 48번과 15번 노드의 최소 공통 조상은 1번이다. 즉, LCA(8, 15) - 1 루트노드에서 DFS/BFS 알고리즘을 통해 각 노드의 깊이를 계산하여 depth 배열에 저장한다.1의 depth는 0, 2와 3의 depth는 1, 4번~8번 노.. 2024. 7. 11. [Python] 퍼즐 조각 채우기 퍼즉 조각 채우기문제 출처: 프로그래머스난이도: level 3input size: $n \le 50$ (정사각 격자)(주관) 자료구조: 그래프(주관) 알고리즘: 완전탐색, BFS(주관) 시간복잡도: $O(n^2) = O(V+E)$ ($V=n^2, E=2n(n-1)$) 2개의 정사각 배열이 주어진다. 1은 블록 한 조각을, 0은 빈 공간을 나타낸다.game_board의 빈 공간을 table에 있는 블록을 이용하여 채운다.하나의 공간을 여러 블록으로 채우거나, 작은 블록으로 큰 빈공간을 채우고 나서도 빈 공간이 있으면 안된다.이때 채워지는 블록의 면적을 리턴하면 된다.STEP 1. 서로 같은 블록단순히 면적을 구하는 것은 DFS/BFS를 이용하여 구할 수 있다.그리고 블록은 좌표의 리스트로 나타낼 수 있다... 2024. 7. 3. [Python] 최고의 집합 최고의 집합문제 출처: 프로그래머스난이도: level 3참고: 없음input size: $1 \le n \le 10^4$, $1 \le s \le 10^8$(주관) 자료구조: 없음(주관) 알고리즘: 수학(주관) 예상 시간복잡도: $O(n)$합이 $s$인 $n$개의 자연수 집합을 구하고, 그 중 원소의 합이 최대인 집합을 오름차순으로 정렬한다. STEP 1. 관찰과 직관프로그래머스에 주어진 예시가 $n=2$라서 와닿지는 않는다.왜냐면 $n=2$인 경우에 너무 쉽게 찾을 수 있다.$a_1 = x, x_2 = s-x$라 하면 곱 $f(x) = x(s-x)$이고 이차함수의 최댓값은 $x=s/2$인 지점이다.물론 정수이므로 $a_1 = \lfloor s/2 \rfloor$, $a_2 = s-a_1$으로 간단히 찾.. 2024. 7. 2. 이전 1 2 다음 728x90 반응형
