반응형 Algorithm/SWEA8 [SWEA/C++] DAG 동전 게임 문제 문제 설명 ">문제 문제 설명 풀이 ">풀이 [문제 풀이] 이 문제는 설명을 잘 이해해야 쉽게 풀 수 있는 문제다. 먼저 조건을 보면 사이클이 있으며 위상 정렬이 되어있다.이를 이용하면 DFS로 1번 노드부터 시작해 N번노드와 N-1번 노드에 도착하는 경우에 돈을 얼마 미만 갖고 있어야 하는지 파악 할 수 있다. 먼저 그림을 통해 예를 들어 보자. 위 그림과 같은 경우에는 N-1과 N으로 바로 가는 방법이 있다.그러므로 다현의 돈의 비율이 나연의 비율과 같은 1:1 미만이면 무조건 나연이 승리한다는 사실을 알 수 있다. 이번에는 조금 다른 경우를 그려보자 위 그림을 보면 N-1과 직접 연결된 경로가 있으면 가진 돈을 전부 제시해 N-1로 가도록 유도할 수 있.. 2024. 11. 26. [SWEA/C++] 돌 추가 게임 (No. 20945) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 풀기 위해서 고민을 좀 많이 했다. 문제에 대해 간단히 설명하자면 Nim 게임이라 불리는 문제에서 응용된 문제다. 여기서 스프라그-그런디 정리를 Nim 게임에 적용하면 돌 무더기에 대해 xor을 계산하는 것으로 누가 이기는지 알 수 있다. 그러므로 후공인 지혜가 이기기 때문에 모든 돌 무더기를 xor값이 0이 되도록 만들기 위해 돌 무더기에 돌을 추가하는데, 이 때 추가해야하는 가장 적은 돌의 양을 계산하면 되는 문제다. 그렇다면 돌을 어떻게 추가해야 가장 적게 돌을 추가할 수 있을까? 먼저 생각해보면 xor.. 2024. 6. 20. [SWEA/C++] 서로소 그리드 (No. 20731) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 GCD를 이용하면 쉽게 풀 수 있는 문제다. 문제를 보면 GCD(k+i, k+j)가 1이면 1, 아니면 ?를 N*N 배열에 기록한다.이때, 이 배열의 조건에 만족하는 k가 존재하는지 판단하는 문제다. 이 문제에서 중요한 점은 K의 범위가 정해져 있지 않기 때문에 모든 조건에 맞는 K가 있는지 확인하면 된다. 그렇다고 모든 K에 대해 탐색할 수는 없다. 그러면 GCD(k+i, k+j)를 어떻게 표현할 수 있을까? i > j의 조건을 만족하는 경우에 GCD(k+i, k+j)가 1이 아니라면 GCD(k+i, i-j.. 2024. 6. 19. [SWEA/Python] 17643번 - 로봇 HTML 삽입 미리보기할 수 없는 소스 [문제] 2차원 평면의 원점에서 로봇이 움직이기 시작하는데 특정 좌표(x,y)에 있을 가능성이 있는지 구하는 문제다. 특징은 로봇은 상하좌우 4방향으로 이동할 수 있고 t초마다 3^t 만큼 고른 방향으로 이동한다. HTML 삽입 미리보기할 수 없는 소스 처음에는 DFS처럼 완전 탐색을 해서 풀려고 했지만 시간 초과가 떴다. 그래서 어떻게 다른 방법으로 풀 수 있을까 생각해봤다. $$\frac{3^t}{2}>\sum_{n=0}^{t-1} 3n\quad (t\neq 0)$$ 그러던 중 위의 식이 항상 성립하는 것을 찾았는데, 쉽게 생각하면 a라는 수에 1/3을 계속 곱한 등비수열은 a/2에 수렴한다는게 떠올랐다. 그렇기 때문에 t=n일 때, t=(0 ~ n-1)까.. 2024. 1. 5. [SWEA/C++] 2112. [모의 SW 역량테스트] 보호 필름Box에 담기 문제 풀기 HTML 삽입 미리보기할 수 없는 소스 [문제 요약] 셀들은 특성 A와 B를 가지고 있으며 보호 필름의 성능은 셀들의 특성이 어떻게 배치되느냐에 따라 달라진다 셀의 특성이 같은 막이 한 열에 연속으로 K개 존재해야 보호 필름의 성능테스트를 통과하며 모든 열이 성능테스트를 통과해야 한다. 약품은 막 별로 투입할 수 있으며(행), 투입하는 막의 모든 셀들은 하나의 특성으로 변경된다. 성능테스트를 통과하기 위해 최소 약품 투입횟수는 몇인지 구하는 문제다. HTML 삽입 미리보기할 수 없는 소스 [풀이] 각 행마다 약품을 주입 하지 않기, A약품을 주입, B약품을 주입 3가지 경우로 경우의 수를 나눴다. 그리고 모든 행의 경우가 정해지면 성능테스트를 통해 보호 성능검사를 통과 여부를 확인하고 통과한다면 약품 주.. 2024. 1. 5. [SWEA/Python] 16606 - 동전 색 찾기 HTML 삽입 미리보기할 수 없는 소스 [문제 요약] n종류의 동전이 있을 때, 동전의 모양은 완전 똑같고 색이 달라서 n종류의 동전을 구분하기 위해 얼마를 요청해야 하는지 구하는 문제다. HTML 삽입 미리보기할 수 없는 소스 [풀이] 서로 다른 동전은 서로 배수관계를 갖고 있다. 만약 V_i와 V_(i+1)이 2배 차이라면 V_i원의 동전의 2배가 되는 돈을 요청 하게 되면 은행은 V_(i+1)원 동전 하나를 주게 된다. 그러므로 V_i원의 동전의 색을 확인하려면 요구하는 돈 X는 V_i HTML 삽입 미리보기할 수 없는 소스 def fx(dic): # n=배수 a=0 ans=[] # 각 배수마다 몇 회차가 필요한지 저장할 리스트 for i in dic.keys(): # dic의 key는 i배수 관계.. 2024. 1. 5. [SWEA/Python] 5250 - 최소비용 HTML 삽입 미리보기할 수 없는 소스 [문제 요약] 출발지에서 도착지까지의 높이가 2차원으로 주어진다. 상하좌우로만 이동 할 수 있으며, 이동시 비용은 1, 만약 이동한 곳이 더 높은 지역이라면 높이의 차이 만큼 비용이 증가한다. HTML 삽입 미리보기할 수 없는 소스 입력으로 받은 값에서 가중치를 2차원 리스트에 저장했고, 가중치를 저장할 2차원 리스트를 큰 값으로 초기화했다. 그리고 for 문을 돌려서 N*N의 좌표 중 방문하지 않은 지점 중 가중치가 가장 작은 지점을 탐색하면 시간초과가 났기 때문에, 방문하지 않은 지점이면서 가중치는 초기값이 아닌 좌표를 now_lst에 저장해 탐색했다. 그리고 그중에서 가중치의 값이 가장 작은 지점이 선택되면 now_lst에서 제거하고 방문 표시를 한 다음 그 .. 2024. 1. 5. [SWEA/Python] 5249 - 최소 신장 트리 HTML 삽입 미리보기할 수 없는 소스 [문제 요약] 노드와 간선의 수가 주어지면 이 그래프로 부터 최소 신장트리를 만들고 최소신장트리를 구성하는 간선의 가중치를 모두 더하는 문제다. HTML 삽입 미리보기할 수 없는 소스 [풀이] 입력으로 받은 값에서 가중치를 2차원 리스트에 저장했고, 그 외의 값들은 최댓값인 10보다 큰 11로 저장했다. 그리고 방문한 지점은 vistied에 True, False로 저장해 구분했다. 처음 시작은 0번 노드에서 시작을 했고, 가중치를 0으로 주었다. 이후 노드의 수 만큼 for문을 돌려 방문을 하지 않은 노드 중 가중치가 가장 노드를 선택해 가중치를 탐색하도록 코드를 작성했다. HTML 삽입 미리보기할 수 없는 소스 def MST_PRIM(node_s): key=[11.. 2024. 1. 5. 이전 1 다음 반응형
