본문 바로가기

분류 전체보기

 (257)
파이썬)구간 합 구하기 - BOJ(세그먼트 트리) https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 우선 세그먼트 트리의 경우 힙 정렬 알고리즘과 상당히 비슷하다. 대신 단순히 트리를 만들어 정렬하는 힙정렬 알고리즘과 달리 세그먼트 트리는 구간 합, 최소, 최대를 구하는데 최적화가 되어있다. 이번 백준 2042번 구간 합 구하기는 도저히 스스로 풀 수가 없어서 다른 이의 코드를 참조했다. 우선 코드를 보자. import sys input..
파이썬)숨바꼭질3 -BOJ https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 우선 이 문제는 BFS로 분류되어 있는 문제이기도 하고, "최소"시간을 구하는 문제이니 BFS가 효율적이라 생각했다. 하지만 어떻게 BFS를 구현할까 생각했다. from collections import deque n, k = map(int, input().split()) visit = [-1] * 100001 visit[n] = 0 q = deque() an..
파이썬) 가장 큰 정사각형 찾기 - 프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/12905 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제를 처음 접했을때 무조건 bfs혹은 dfs로 풀어야겠다 생각했다. 우선 가장 넓은 범위를 구하기 위해 bfs를 사용했다. 그리고 정사각형을 어떻게해서 찾을 것인지 생각해보았다. 단순이 상하좌우가 1인 것만 찾는다면 "정"사각형을 찾지는 못한다. 그래서 생각해낸 방법이 바로 위, 바로 왼쪽, 왼쪽 대각선이 모두 1인 경우를 정사각형이라 보고 그 왼쪽 대각을 q에 담는다. 아래는 위 생각을 그..
파이썬)수들의 합5 -BOJ https://www.acmicpc.net/problem/2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 처음 이 문제를 보았을때, dp를 사용해야 하나 싶었다. 그러나 dp로는 단순히 연속된 수들만 구할 수 있었고, 그 다음으로 생각한 것이 브루트 포스였다. 하지만 n이 10,000,000개라는 점에서 브루트 포스 또한 초과가 나올 것이 분명했다. 그래서 투포인터로 풀어야겠다 생각했다. n = int(input()) arr = [i for i in range(1, n+1)] a..
파이썬) https://www.acmicpc.net/problem/1963 import sys, math from collections import deque def findPrime(): # 에라토스테네스의 체(제곱근 범위까지 조사) for i in range(2, 100): # 소수인 상태에서 소수의 배수를 체크해줘야 함 if prime[i] == True: # 소수의 배수 체크 for j in range(2*i, 10000, i): prime[j] = False def bfs(): q = deque() q.append([start, 0]) visited = [0 for i in range(10000)] visited[start] = 1 while q: now, cnt = q.popleft() strNow =..
파이썬)광물캐기 -프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/172927# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr from collections import deque def solution(picks, minerals): answer = 0 pickable_minerals = minerals[: sum(picks) * 5] tools_len = 0 for i in picks: tools_len += i * 5 # print(tools_len,len(minerals)) # print(tools_len < ..
파이썬) 과제 진행하기 https://school.programmers.co.kr/learn/courses/30/lessons/176962 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr from collections import deque def solution(plans): answer = [] q = deque() for i in range(len(plans)): # 시간을 분으로 변환 = 시간 * 60 + 분 time = plans[i][1].split(':') new_time = int(time[0]) * 60 + int(time[1]) plans[i][1] = new_..
파이썬) 택배 배달과 수거하기 https://school.programmers.co.kr/learn/courses/30/lessons/150369 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr def solution(cap, n, deliveries, pickups): deliveries = deliveries[::-1] pickups = pickups[::-1] answer = 0 have_to_deli = 0 have_to_pick = 0 for i in range(len(deliveries)): have_to_deli+= deliveries[i] have_to_pick += pi..

티스토리툴바