백준 온라인저지 18870번 좌표압축 문제풀러 바로가기👇👇👇👇👇👇 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 문제풀이 시간 복잡도가 굉장히 중요한 문제이다. 근본적인 알고리즘은 쉬운 편이다. 중복되지 않은 배열을 정렬해 그 인덱스를 가져오면 된다. 만약 여기서 리스트에서 인덱스를 가져오는 index()메소드를 사용하면 시간복잡도가 O(N)이다. 그런데 문제에서 N의 범위는 무려 1 ≤ N ..
백준 온라인저지 1654 랜선 자르기 문제풀러 바로가기👇👇👇👇👇👇 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제풀이 이 문제는 이분탐색을 이용해야하는 문제이다. start는 1로 잡고, 랜선 중 최대길이를 end로 정한 다음 이분 탐색을 하면 다음과 같다. 첫 번째 mid는 402cm이다. 402cm로 자르면 랜선이 5개 밖에 나오지 않기 때문에 mid를 mid = (start + mid - 1) // 2 로..
1. 스택 스택이란? 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다. 자료를 넣는 것을 '밀어넣는다' 하여 푸쉬(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 푸쉬한 자료부터 나오게 된다. 이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다. 반대로 FILO(First In Last Out)라고 하기도 한다. 파이썬으로 구현 append() 메소드와 pop()메소드만 사용할 수 있으면 간단히 리스트로도 구현할 수 있다. 아래의 예시를 보자 stack = [] stack.append(1) stack.append(2) stack.append(3) sta..
1. rjust() 원하는 문자를 왼쪽부터 채워 본래 값을 오른쪽으로 정렬해서 반환해준다. arr = ['101', '0011', '11111'] print(arr[0].rjust(5, "0")) print(arr[1].rjust(7, "0")) print(arr[2].rjust(5, "0")) -결과값 >> 00101 >> 0000011 >> 11111 2. ljust() 원하는 문자를 오른쪽부터 채워 본래 값을 왼쪽으로 정렬해서 반환해준다. arr = ['101', '0011', '11111'] print(arr[0].ljust(5, "0")) print(arr[1].ljust(7, "0")) print(arr[2].ljust(5, "0")) -결과값 >> 10100 >> 0011000 >> 1111..
1. 경우의 수 permutations() - 순열 순열은 순서를 고려해서 뽑는 경우의 수다. nPr 로 쓰이는데 이를 풀어서 말하면 n개 중 순서를 고려하여 r개를 뽑는 것을 말한다. -예시 num = [2,1,3,4,1] result = list(itertools.permutations(num, 2)) - 결과값 >> [(2, 1), (2, 3), (2, 4), (2, 1), (1, 2), (1, 3), (1, 4), (1, 1), (3, 2), (3, 1), (3, 4), (3, 1), (4, 2), (4, 1), (4, 3), (4, 1), (1, 2), (1, 1), (1, 3), (1, 4)] 1이 2개 있기때문에 중복된 결과가 나온다. combinations() - 조합 조합이라고 하면 nC..
1. 람다식에 대한 기본적인 이해 람다식을 통해 익명함수를 만드는 법에 대해서 알아보자. 람다식은 함수 표현을 간단하게 만들어줄 수 있다. 한 줄 짜리 함수에 많이 사용되는 편이다. 일단 일반 함수와 비교하기 위해 예시를 들도록 하겠다. def square(x): return x * x print(square(4)) >> 16 정사각형의 넓이를 구하는 square다. 이를 아래와 같은 람다식으로 표현할 수 있다. print((lambda x : x*x)(4)) >> 16 람다식을 재할당하고 싶으면 따로 저장할 수도 있다. square = (lambda x : x*x) print(square(4)) >> 16 또한, 한 줄(one-line) 조건문을 사용하여 람다식을 표현하는 것도 가능하다. 아래의 예시를..
