[Python/파이썬] 백준 1806번 - 부분합

[Python/파이썬] 백준 1806번 - 부분합

문제 설명 입출력 예제 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 코드 배열에서 특정한 합을 갖는 부분 연속 수열을 찾는 것은 투 포인터 알고리즘을 활용하는 대표적인 예이다. 투포인터 알고리즘에 대한 설명은 아래 링크를 통해 확인 할 수 있다. [알고리즘] 투 포인터(Two Pointers)란? 투 포인터(Two Pointers) 투 포인터는 말 그대로 두 개의 포인터를 사용하여 문자열, 배열, List에서 원하는 값을 찾는 것 입니다. 투 포인터를 활용하기 위한 조건은 주어진 배열에..

  • format_list_bulleted ◼ 코딩테스트/투포인터 (Two Pointer)
  • · 2023. 7. 19.
  • textsms
[Python/파이썬] 백준 11659 - 구간 합 구하기 4

[Python/파이썬] 백준 11659 - 구간 합 구하기 4

문제 설명 입출력 예제 풀이 코드 이 문제는 현대오토에버 코딩문제에 나온 문제라고 한다. 사실상 실버난이도인 만큼 접근만 한다면 쉽게 풀 수 있는 문제다. 제한 사항을 보면 N, M 입력값의 제한 범위가 100,000이다. 이중 반복문으로 풀면 쉽게 풀수는 있겠지만 2중 반복문은 O(n^2) 시간 복잡도를 갖기 때문에 시간초과가 발생한다. 따라서 O(N)이나 O(logN)의 시간 복잡도로 풀어야 하는데 문제에서도 이미 정답을 말해줬다."구간합" 문제를 푸는 방법은 다음과 같다. 주어진 값들의 누적합을 갖는 리스트를 만든다. PrefixSum 여기서 PrefixSum에 0을 넣어 놓은 이유는 주어지는 구간 i가 1부터 시작하기 때문에 인덱싱에러를 방지하기 위해서이다. 각 수들의 합을 갖는 변수 total을..

  • format_list_bulleted ◼ 코딩테스트/구간합 (Prefix)
  • · 2023. 6. 22.
  • textsms
[Python/파이썬] 백준 1065 - 한수

[Python/파이썬] 백준 1065 - 한수

문제 설명 입출력 예제 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 풀이 코드 처음에는 문제 설명을 이해하는게 어려울 것이다. (문제 설명이 좀 많이 아쉽;) 왜 110을 입력했을 때 결과가 99가 나오는지 이해할 수가 없었다. 하지만 왜 그러한 결과가 나오는지 이해만 한다면 문제는 실버난이도 답게 쉽게 풀 수 있을 것이다. 일단 "한수"라는 것은 각 자리수의 차이가 일정한 수이다. 111 이라는 수가 주어진다면 이 수는 각 자리수 차이가 0이므로 ㅠ이다. 그렇다면 5는 어떨까? 자리수를 비교할 대상이 없지만..

  • format_list_bulleted ◼ 코딩테스트/완전탐색 (Bruteforce)
  • · 2023. 6. 17.
  • textsms
[Python/파이썬] 백준 2589 - 보물섬

[Python/파이썬] 백준 2589 - 보물섬

문제 설명 입출력 예제 풀이 코드 처음에 육지중에 땅의 크기가 가장 큰 섬를 bfs로 구한다음에 가장 큰 섬에서 또 bfs로 보물 사이의 최단거리를 구해야하나? 라고 생각했다. 하지만 그럴 필요 없이 두 섬에서 보물 사이의 거리가 가장 먼 값을 구하면 된다. 정답 코드 from collections import deque import sys input = sys.stdin.readline r, c = map(int, input().split()) board = [list(input().rstrip()) for _ in range(r)] dx = [1, -1, 0, 0] dy = [0, 0, -1, 1] def bfs(x, y): q = deque() q.append((x, y)) visited = [[-..

  • format_list_bulleted ◼ 코딩테스트/DFS,BFS
  • · 2023. 6. 9.
  • textsms
[Python/파이썬] 백준 9019 - DSLR

[Python/파이썬] 백준 9019 - DSLR

문제 설명 입출력 예제 풀이 코드 A와 B는 모두 0 이상 10000이하의 수라고 했으므로 visited 배열의 수를 10000으로 초기화 해주었다. 그리고 방문하지 않은 수는 bfs 탐색을 시작한다. 여기서 핵심은 일반적인 bfs 문제의 dx, dy 상하좌우 이동 처럼 D, S, L, R 을 활용하는 것이다. 큰 난이도가 있는 문제는 아니라서 아래 코드와 주석을 참고하면 이해될 것이다. 참고로 테스트 케이스 반복문 때문인지 파이썬으로 제출하면 시간초과가 났고 PYPY3로 제출하니 통과할 수 있었다. 정답 코드 from collections import deque import sys input = sys.stdin.readline def applyCommand(n, command): if command ..

  • format_list_bulleted ◼ 코딩테스트/DFS,BFS
  • · 2023. 6. 7.
  • textsms
[Python/파이썬] 백준 5014 - 스타트링크

[Python/파이썬] 백준 5014 - 스타트링크

문제 설명 풀이 코드 각 층마다 버튼을 몇번씩 눌려 도달했는지 저장하기 위해 visited[] 배열을 선언하였다. 강호의 위치(S)부터 bfs로 탐색을 시작한다. 강호의 위치(S)가 스타트링크(G)에 도착하면 스타트링크까지 도착하는데 눌린 버튼횟수를 반환한다. visited[cur] 정답 코드 from collections import deque import sys input = sys.stdin.readline f, s, g, u, d = map(int, input().split()) # 층수, 강호, 스타트링크, 위, 아래 visited = [-1] * (f + 1) def bfs(start): q = deque() q.append(start) visited[start] = 0 while q: cur..

  • format_list_bulleted ◼ 코딩테스트/DFS,BFS
  • · 2023. 6. 6.
  • textsms
반응형