본문 바로가기

Algorithm

[Baekjoon]백준 11660 구간 합 구하기 5(실버 1) - Python 문제를 살펴보면 인덱스 두 개를 입력받고, 그 인덱스 구간의 합을 구하는 문제이다이때까지의 문제와 다른 점은 2차원 배열이라는 점, 그리고 x좌표의 범위에 따라 합이 제한된다는 것이다두 번째 말에 대해 다시 말하자면, 예를 들어1 2 3 4 3 2 3 4 1라는 표가 주어져있을때 (2,2)부터 (3, 3)까지의 합을 구하는 것에 (3, 1)은 포함되지 않는다는 점이다 그래서 처음에 이 문제를 풀기 위한 로직으로 각 행마다 누적합을 계산해두고, index를 입력받으면for문을 통해 부분합을 구하여 변수 하나에 해당 값을 계속해서 저장하여 출력하도록 하였다위의 예를 통하여 설명하자면 누적합이 [1, 3, 6], [4, 7, 9], [3, 7, 8]로 저장되어있을텐데,  (2, 2), (3, 3)이 입력되었을.. 더보기
[Baekjoon]백준 10986 나머지 합(골드 3) - Python 문제를 살펴보면 부분합 중에서 입력받은 수로 나누었을 때 나머지가 0인 경우의 수를 출력해야한다일단 혹시나 싶은 마음에 누적 합, 부분 합을 따로 구하여 나머지가 0이 되는 경우의 수를 찾는 코드를 작성해보았다num, div = map(int, input().split())ls = list(map(int, input().split()))cnt = 0prefix_sum = [0] * (num + 1) # 누적 합 계산for i in range(num): prefix_sum[i+1] = prefix_sum[i] + ls[i]result = []for i in range(num): # 구간 합 계산 for j in range(i, num): result.append(prefix_sum[.. 더보기
[Baekjoon]백준 16139 인간-컴퓨터 상호작용(실버 1) - Python 문제를 살펴보면 어떠한 문자열을 입력받게되고, 특정 문자열이 입력받은 index안에 몇개 존재하는지 출력하는 문제이다즉, abacaba 라는 문자열이 있을 때, a 0 4 라고 입력을 받으면첫번째 index부터 4번째 index까지 a가 몇개 있는지 출력해야한다(해당 예시에서는 3이 출력될 것이다)문제를 자세히 살펴보면 하나의 문자에 대해서 질문을 반복하기 때문에 질문을 할때마다index 범위에 따른 개수를 저장하는 것보다 미리 값들을 저장한 리스트를 만들어두고 값을 꺼내오는게 더 간단하다 그래서 하나의 딕셔너리를 만들어 등장하는 문자열을 저장하도록 하였다해당 문자열의 길이만큼 0을 만들어주고 등장하는 문자열의 위치에 1을 넣어준다문자열 s = "abacaba"라면:count['a'] = [1, 0, 0.. 더보기
[Baekjoon]백준 2559 수열(실버 3) - Python 문제를 살펴보면 n개의 수를 입력을 받게 되고, 연속적인 k개의 합 중에서 가장 큰 값을 출력하는 문제이다가장 간단한 방법이라 함은, k개의 index를 묶어 for문을 통해 이동하며 sum함수로 합을 구하는 것이다하지만, 여태까지 백준 문제를 푼 경험으로 보아 그런 문제는 아닐것이다 그래서 효율적인 방법이 뭐가 있을까라는 생각을 하다가 합을 구하는 부분에서 아이디어가 생각났다이전의 index의 값들도 포함하여 더하기때문에, 굳이 해당 index안의 값들을 다 더할 필요가 없다는 것이다다시 말하자면, 1 2 3 4 5 3 2 1 이라는 리스트가 존재하고, k가 3이라고 가정해보자 처음에 말한 간단한 방법으로 수행하면 1 2 3의 합을 구하여 6을 저장하고, 2 3 4 의 합을 구하여 9를 저장할 것이다두.. 더보기
[Baekjoon]백준 15649 N과 M (1)(실버 3) - Python, C++ 문제를 읽어보면 N, M을 입력받아 길이가 M인 수열을 모두 출력하는 문제이다python에는 permutations라는 좋은 함수가 존재하기 때문에 간단하게 이 문제를 풀면 아래의 코드가 나온다from itertools import permutationsnum, length = map(int, input().split())sequences = list(permutations(range(1, num + 1), length))for i in range(len(sequences)): print(*sequences[i])하지만 이 문제는 백트래킹 단계에 존재하는 문제이고, 백트래킹을 배우기 위해 푸는 문제이므로문제의 의도에 맞게 코드를 다시 작성하였다 함수를 재귀적으로 호출하여 문제를 해결하였는데, 먼저 .. 더보기

티스토리툴바