이것저것 공부 기록하기

오늘부터 나도 1일1문제 시작. 오늘의 문제 : https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net # sys.stdin.readline() 을 사용해야 시간초과 안 나고 통과됨 (같은 풀이일 때 input() 으로 받면 시간초과남) import sys from collections import deque n = int(sys.stdin.readline()) q = deque() for i in range(n): tmp =..

둘 다 완전탐색 시 시간초과가 날 때 유용하게 사용될 수 있다. 투포인터 문제 풀다가 차이가 궁금해서 정리해봤다. 투포인터 vs 이분탐색 투포인터 : left, right 두 개의 포인터를 한 칸씩 이동하면서 알맞은 값을 찾음 이분탐색 : mid를 활용해 매 연산마다 탐색하는 범위를 절반으로 좁혀나감 투포인터(Two Pointer) 이분탐색(이진탐색, Binary Search) 시간복잡도 O(N) O(log N) 가정 특별히 없으나, 일반적으로 배열이 정렬되어있을 때 좀 더 유용 데이터가 정렬되어있어야 함 방식 양 끝단에서 한 칸씩 이동하면서 알맞은 값을 찾음 mid를 활용해서 매 연산마다 탐색하는 범위를 절반으로 좁혀나감 참고 파이썬 알고리즘 인터뷰 https://skesswswkk.tistory.co..

슬라이딩 윈도우(sliding window)란 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘이다. 원래 네트워크에서 사용되던 알고리즘을 문제 풀이에 응용한 경우라고 한다. 슬라이딩 윈도우는 네트워크 용어로, 2개의 네트워크 호스트 간의 패킷 흐름을 제어하기 위한 방법을 지칭하기도 하기 때문이다. 투 포인터와 유사하지만 이와 구분하기 위해 일반적으로 고정 사이즈 윈도우를 사용하는 경우를 슬라이딩 윈도우로 따로 구분하기도 한다. 또한, 투 포인터는 주로 정렬된 배열을 대상으로 하지만, 슬라이딩 윈도우는 정렬 여부에 관계없이 활용된다. 즉, 이름 그대로 생각하면 편하다. 투 포인터는 좌우 포인터가 자유롭게 이동하며 윈도우 사이즈가 가변적인 반면, 슬라이딩 윈도우는..

programmers.co.kr/learn/courses/30/lessons/42746 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 programmers.co.kr 문제 설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 n..

Ice Cream Parlor | HackerRank Help Sunny and Johnny spend all their money during each trip to the Ice Cream Parlor. www.hackerrank.com 문제 풀이 그냥 이중 for문으로 간단하게 풀린다. def icecreamParlor(m, arr): for i in range(len(arr)): for j in range(i, len(arr)): if arr[i] + arr[j] == m and i != j: return i+1, j+1

문제 설명 무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다. 예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다. 구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다. 사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요..