푼 날짜 : 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 ..
![]()
푼 날짜 : 2024.08.18푼 문제 : [1326] / 폴짝폴짝사용한 언어 : python 푼 방법 :너비 우선 탐색으로 접근하였다. 어떤 징검다리에서 점프를 할 때는 그 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있다. 이 부분이 중요한데 앞으로 가든 뒤로 가든 현재 위치의 징검다리의 수의 배수만큼만 이동한다는 거 !예시를 들자면 현재위치가 인덱스 4번이고 4번 징검다리에 쓰여 있는 수가 3이라면, 이렇게 1과 7로 이동할 수 있다.만약 배열이 더 길다면 인덱스 7, 10, 13, 16 .... 이렇게 갈 수 있다! 추가적인 테스트케이스를 첨부해보자면, 마지막 3번 테케는 질문게시판에 다른 분이 올려주신 부분을 손으로 그려봤다. 순서대로 N - 징검다리 수..
푼 날짜 : 2024.08.17푼 문제 : [16953] / A → B사용한 언어 : python 푼 방법 :너비 우선 탐색으로 접근하였다. 처음 풀었을 때 메모리 초과가 났다.아무래도 범위가 최대 10^9 이기 때문에 배열을 다 만든다고 하면... 그래서 생각한 방법이 dictionary다.불필요한 visited를 다 만들어 놓지 말고 필요한 값만 저장하기로 했다.사실 리스트에서 딕셔너리로 변경한 것 말고는 크게 BFS문제를 벗어날 정도의 난이도가 아니었기 때문에 코드는 전반적으로 비슷하다. 코드 :import sysfrom collections import dequeA, B = map(int, sys.stdin.readline().split())visited = {} # 딕셔너리로 만들기px =..
