핵심을 파악하는 탐욕법 알고리즘

핵심을 파악하는 탐욕법 알고리즘

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/86491?language=python3 코딩테스트 연습 - 최소직사각형 [[10, 7], [12, 3], [8, 15], [14, 7], [5, 15]] 120 [[14, 4], [19, 6], [6, 16], [18, 7], [7, 11]] 133 programmers.co.kr 명함 지갑을 만드는 회사에서 지갑의 크기를 정하려고 합니다. 다양한 모양과 크기의 명함들을 모두 수납할 수 있으면서, 작아서 들고 다니기 편한 지갑을 만들어야 합니다. 이러한 요건을 만족하는 지갑을 만들기 위해 디자인팀은 모든 명함의 가로 길이와 세로 길이를 조사했습니다. 아래 표는 4가지 명함의 가로 길이와 세로 길이를 나..

  • format_list_bulleted 알고리즘/알고리즘 일반
  • · 2022. 1. 12.
  • textsms
코딩테스트에서 유용한 Counter와 deque

코딩테스트에서 유용한 Counter와 deque

1. Counter 시퀀스 타입 데이터의 원소 개수를 dict형으로 반환해주는 아주 유용한 함수 from collections import Counter로 불러온다 집합 연산도 가능함 근데 큰 의미가 있을까? 리스트 내에서 개별 원소들의 빈도수를 세는 것에는 분명히 의미 있다 2. deque 스택과 큐를 동시에 구현한 자료형 from collections import deque로 불러온다 append, extend, pop 등을 모두 지원하는데 list가 $O(n)$이라면 deque는 $O(1)$이라는 점에서 유용하다 append로 오른쪽에 데이터를 넣어주고 appendleft로 왼쪽에 데이터를 넣어준다 extend로 오른쪽에 리스트 데이터를 넣어주고 extendleft로 왼쪽에 리스트 데이터를 넣어준다..

  • format_list_bulleted 프로그래밍/Python
  • · 2022. 1. 12.
  • textsms
핵심 알고리즘 파악하기

핵심 알고리즘 파악하기

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/12909 코딩테스트 연습 - 올바른 괄호 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 "()()" 또는 "(())()" 는 올바른 괄호입니다. ")()(" 또는 "(()(" 는 올바르지 않은 programmers.co.kr 괄호가 바르게 짝지어졌다는 것은 ‘(‘ 문자로 열렸으면 반드시 짝지어서 ‘)’문자로 닫혀야 한다는 뜻입니다. 예를 들어 ‘()()’ 또는 ‘(())()’는 올바른 괄호입니다. ‘)()(‘ 또는 ‘(()(‘는 올바르지 않은 괄호입니다. ‘(‘ 또는 ‘)’로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올..

  • format_list_bulleted 알고리즘/알고리즘 일반
  • · 2022. 1. 12.
  • textsms
파이썬의 튜플(Tuple), 집합(set), 사전(dict)에 대하여

파이썬의 튜플(Tuple), 집합(set), 사전(dict)에 대하여

1. 튜플(tuple) 리스트랑 비슷하지만 [1,2,3] 대신 (1,2,3)같이 ()을 사용 리스트가 사용하는 대부분 연산이 가능하나 원소의 변경이 불가능하다 이러한 특징때문에 프로그램 동작하면서 절대 변경되어서는 안되는 데이터(예:학번, 우편번호 등)를 저장할 때 사용한다 사용자 실수에 의한 데이터 변경 에러를 미리 방지 2. 하나의 원소를 가지는 튜플 (1)은 정수로 인식하고 (1,)을 튜플로 인식 a=(1) a 1 type(a) int b=(1,) b (1,) type(b) tuple 3. 집합(set) 데이터를 순서 없이 저장하는데 중복을 허용하고 싶지 않을때 리스트보다 유용하다 s = set([1,2,3,1,2,3]) s {1,2,3} type(s) set ##리스트의 중복을 제거하는 기술 li..

  • format_list_bulleted 프로그래밍/Python
  • · 2022. 1. 11.
  • textsms
deque 잘 활용하기

deque 잘 활용하기

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/17684?language=python3 코딩테스트 연습 - [3차] 압축 TOBEORNOTTOBEORTOBEORNOT [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34] programmers.co.kr 신입사원 어피치는 카카오톡으로 전송되는 메시지를 압축하여 전송 효율을 높이는 업무를 맡게 되었다. 메시지를 압축하더라도 전달되는 정보가 바뀌어서는 안되므로, 압축 전의 정보를 완벽하게 복원 가능한 무손실 압축 알고리즘을 구현하기로 했다. 어피치는 여러 압축 알고리즘 중에서 성능이 좋고 구현이 간단한 LZW 압축을 구현하기로 했다. LZW 압축은..

  • format_list_bulleted 알고리즘/알고리즘 일반
  • · 2022. 1. 11.
  • textsms
시간을 줄이는 효율적인 코딩하기

시간을 줄이는 효율적인 코딩하기

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/12941 코딩테스트 연습 - 최솟값 만들기 길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다. 배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱 programmers.co.kr 길이가 같은 배열 A,B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다. 배열 A,B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더합니다. 이 때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다. 단 각 배열에서 k번째 숫자를 뽑았다..

  • format_list_bulleted 알고리즘/알고리즘 일반
  • · 2022. 1. 5.
  • textsms