알고리즘

푼 날짜 : 2024.09.14푼 문제 : [9465] / 스티커사용한 언어 : python알고리즘 : DP  점화식 :dp[0][i] = max(dp[1][i-1]+sticker[0][i], dp[1][i-2]+sticker[0][i]) dp[1][i] = max(dp[0][i-1]+sticker[1][i], dp[0][i-2]+sticker[1][i])  점화식 도출 과정은 다음과 같다.아래와 같은 예시가 있을 때를 기준으로 계산해보겠다. 이는 sticker배열이다.501010020403050701060  dp 배열은 초기값을 이렇게 설정해주었다.5040   30100     초기값을 이렇게 설정한 이유는 다음과 같다.스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수..

푼 날짜 : 2024.09.13푼 문제 : [1149] / RGB거리사용한 언어 : python알고리즘 : DP  점화식 :dp[i][0] = colors[i][0] + min(dp[i-1][1], dp[i-1][2]) dp[i][1] = colors[i][1] + min(dp[i-1][0], dp[i-1][2]) dp[i][2] = colors[i][2] + min(dp[i-1][0], dp[i-1][1])   초기값은 dp[0]을 colors[0]을 넣어주고 시작했다.그리고 dp테이블을 하나씩 채워나가는데, i번째의 0번째 요소를 채우기 위해서는 i-1번째의 0번이 아닌 1번과 2번 중 더 작은 값을 더해서 채워준다. 이렇게 해야 값을 최소로 만들며 더해갈 수 있기 때문이다.     코드 :impor..

푼 날짜 : 2024.09.011푼 문제 : [1303] / 전쟁 - 전투사용한 언어 : python  푼 방법 :DFS로 접근하였다. N명이 뭉쳐있을 때는 N*N의 위력을 낼 수 있다.  같은 병사가 몇 명이 뭉쳐있는지를 계산하고 그 인원의 제곱을 구한다.우리 병사와 적국 병사의 위력의 총합을 출력한다. 범위 계산과 추가적으로 현재의 target과 일치하면 지속해서 DFS를 실행하고 아니라면 제곱값을 총합에 더하여 다음 과정을 진행하도록 구현했다.  코드 :import sysN, M = map(int, sys.stdin.readline().split())graph_ = []visited = [[0 for _ in range(N)] for _ in range(M)]for _ in range(M): ..

푼 날짜 : 2024.09.06푼 문제 : [13549] / 숨바꼭질3사용한 언어 : python  푼 방법 :BFS로 접근했다.여기서 이전 문제들과 달랐던 점은 다른 이동은 1초 후 이동, 순간이동을 하는 것은 0초 라는 것! 따라서 계산 순서를 [순간이동(*2칸), -1칸, +1칸] 으로 두고 코드를 작성하였는데 지금 생각해보니 순간이동 가능한 범위(max는 동생의 위치 *2 정도로 잡으면 될 것 같다.)를 먼저 다 계산하고 추후 계산(+1, -1)을 해도 될 것 같다는 생각이 들었다.   코드 :import sysfrom collections import dequeN, K = map(int, sys.stdin.readline().split())dx = ['*', '-', '+']def BFS(vis..

푼 날짜 : 2024.09.05푼 문제 : [2470] / 두 용액사용한 언어 : python  푼 방법 :항상 범위를 잘 확인해야한다.위의 문제처럼 범위가 엄청나게 큰 경우 계산을 어떻게 하면 효율적으로 할지 잘 판단해야한다!! 이번 문제의 경우에는 음수값도 포함이 되며 0에 가까워야 하므로 절댓값이 가장 작아야 한다고 생각했다.또한 인접값을 계산하는 것이 아니라 배열 내 두 요소를 고려하여 0에 가까운 값을 만드는 것이 핵심이므로 절댓값 기준으로 정렬을 하고 시작했다. 이렇게 해서 가장 0에 가까운 값을 만드는 두 요소를 출력하는데, 이 때 값을 오름차순으로 출력해야 한다.  코드 :import sysN = int(sys.stdin.readline())lst = list(map(int, sys.std..

푼 날짜 : 2024.09.04푼 문제 : [1806] / 부분합사용한 언어 : python  푼 방법 :투포인터로 접근하였다.왜냐하면 범위자체가 N (10 ≤ N S (0 10,000이하의 자연수이기 때문에 매번 합을 구하는 것은 비효율적이므로 이전합에 가장 왼쪽 값을 빼주고 오른쪽 값을 더해가는 식의 투포인터로 풀었다. 가장 어려웠던 것은 index 계산이었다.결국... 약간 엉성하게 반례에 맞는 조건을 다시 한 번 걸어줌으로써 문제를 해결했다. 예를들면 아래와 같은 반례이다. 4 26 7 8 9 이런 경우에는 굳이 합을 구하지 않아도 각각의 원소가 S이상이기 때문에 최소의 길이는 당연히 1이 된다. 이번 코드에서는 미리 한 바퀴 돌면서 각 요소가 하나라도 S를 넘는다면 바로 1을 출력하게 하고 아닐..

푼 날짜 : 2024.09.03푼 문제 : [17478] / 재귀함수가 뭔가요?사용한 언어 : python  푼 방법 :(예제 출력의 예시를 바탕으로 작성)  재귀는 Base case 와 Recursive case로 구성된다.Base case는 탈출 조건이기 때문에 잘 설정해주는 것이 중요하다! 따라서, 그림으로 보았을 때 "재귀함수가 뭔가요?" 하고나서 답이 달라지는 순간이 분홍색 박스의 경우이다. 해당 위치에서 달라지는 답을 출력하고 return 시켜 재귀를 탈출해주어야한다. 또한 언더바로 재귀의 깊이를 표현하고 있는데 "____" 를 얼마나 곱해주어야 하나면,recursive(2)일 때 2-2 = 0 번 호출하고 recursive(1)일 때 2-1 = 1 번 호출하고 => ____recursive(..

푼 날짜 : 2024.08.19푼 문제 : [20291] / 파일정리사용한 언어 : python  푼 방법 :dot(.)을 기준으로 파싱하여 딕셔너리에 개수를 함께 저장하였다.확장자를 사전 순으로 정리해야 하므로 딕셔너리의 items()를 기준으로 정렬하여 출력하였다.  코드 : import sysN = int(sys.stdin.readline())myDict = {}for _ in range(N): file = sys.stdin.readline().rstrip() extension = file.split('.')[1] if extension in myDict: myDict[extension] +=1 else: myDict[extension] = 1 for name, num ..