이것저것 공부 기록하기

https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net n = int(input()) tmp = [] for i in range(n): tmp.append(input().split()) tmp = [[int(x[0]),x[1]] for x in tmp] tmp.sort(key=lambda x:x[0]) for i in range(n): print(*tmp[i]) 정렬문제인데 나는 그냥 sort 써서 했다보니 채점시간이 4000ms이 걸렸다. 이후에 좀 더 ..

오늘부터 나도 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 =..

References https://brunch.co.kr/@mathian/32

둘 다 완전탐색 시 시간초과가 날 때 유용하게 사용될 수 있다. 투포인터 문제 풀다가 차이가 궁금해서 정리해봤다. 투포인터 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

코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 문제 설명 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 'hit', 'target'가 cog, words가 ['hot','dot','dog','lot',..