썸네일 BAEKJOON #11726) 2xn 타일링 | DP | Python 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 0️⃣ 초기화 이 문제를 풀기 위해서는 2x1 타일링 방법 개수와 2x2 타일링 방법 개수를 초기화하고 시작합니다. 2x1을 타일링하는 방법은 아래의 방법으로 1개 입니다. 2x2를 타일링하는 방법은 아래 방법으로 2개 입니다. 1️⃣ 2x3 타일 생각해보기 초기화 한 후, 2x3 타일링은 2x1타일링에 1x2타일 2개를 붙이고, 2x2타일링에 2x1타일 1개를 붙이면 됩니다. 2️⃣ 2x4 타일 생각해보기 2x4 타일 또한 앞의 방법처럼 2x2 타일에 1x2 타일 2개를 붙이고, 2..
썸네일 BAEKJOON #1655) 가운데를 말해요(Python) 숫자를 입력받을 때마다 중앙값(숫자의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수)을 찾아서 출력하는 문제이다. 처음에는 숫자를 입력받을 때마다 배열에 넣고 정렬하여 홀수면 n/2번째 인덱스를, 짝수면 (n-1)/2번째 인덱스를 출력하면 된다고 생각하여 정렬 알고리즘을 구현하여 제출했다. 뚜둥-! 퀵소트로 정렬하면 시간 초과가 나고, 병합정렬(merge sort)을 이용하면 메모리 초과가 난다😇 정렬 알고리즘을 이용하여 풀 수는 없다. 조금 찾아보니 힙을 사용하여 중앙값을 찾는 방법을 이용하면 된다고 한다. Data Structure - Heap (힙) | Python 구현 Heap은 이진트리의 변형된 자료구조라고 할 수 있는데, 최댓값 최솟값을 빠르게 찾아야 할 때 많이 사용된다. 📌Heap ..
썸네일 BAEKJOON #11279) 최대 힙 (Python) 1927번과 마찬가지로 힙을 구현만 하면 해결되는 문제이지만, 파이썬에는 이미 구현되어있는 heapq 라이브러리가 있기 때문에, 함수(heapq.heappush(heap, value), heapq.heappop(value))를 사용만 해준다. import heapq from sys import stdin n = int(stdin.readline()) heap = list() for _ in range(n): input_num = int(stdin.readline()) if input_num == 0: if heap: print(heapq.heappop(heap)[1]) else: print(0) else: heapq.heappush(heap, [-input_num, input_num]) 다만, heapq..
썸네일 BAEKJOON #1927) 최소 힙 (Python) 문제 이름처럼 힙을 구현만 하는 되는 문제라서, 힙을 구현해야겠다고 생각했는데, 파이썬에는 이미 힙을 만들 수 있는 라이브러리가 있었다. 역시 파이썬..,.👍 heapq라는 라이브러리를 import하여 문제가 요구하는대로 사용해주면 끝이다. 📌 힙(heap)이란? Data Structure - Heap (힙) | Python 구현 Heap은 이진트리의 변형된 자료구조라고 할 수 있는데, 최댓값 최솟값을 빠르게 찾아야 할 때 많이 사용된다. 📌Heap : 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 (Com eunbin00.tistory.com 📌 정답 코드(Python) import heapq from sys import stdin n = int(stdin.readline()) ..
썸네일 BAEKJOON #11718) 그대로 출력하기| C, Python 백준 11718번: 그대로 출력하기 입력받은 대로 그대로 출력하면 되는 문제이다. 11718번: 그대로 출력하기 입력이 주어진다. 입력은 최대 100줄로 이루어져 있고, 알파벳 소문자, 대문자, 공백, 숫자로만 이루어져 있다. 각 줄은 100글자를 넘지 않으며, 빈 줄은 주어지지 않는다. 또, 각 줄은 공백으로 시 www.acmicpc.net C #include intmain(void) { char a; while (scanf("%c", &a) != -1) printf("%c", a); return 0; } char형 변수를 선언하고 character 하나하나 입력받는다. scanf 함수에서 에러가 나지 않는 이상 계속 받은 char를 출력한다. Python while True: try: print(in..
썸네일 BAEKJOON #1463) 1로 만들기 | 다이나믹 프로그래밍 | python 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 📌 다이나믹 프로그래밍 [Algorithm] 다이나믹 프로그래밍 | Dynamic Programming | 계속 쓰일 값은 저장해놓고 가져다 쓰자 💡 다이나믹 프로그래밍 (Dynamic Programming, DP) 우리는 연산 속도와 메모리 공간을 최대한 활용할 수 있는 효율적인 알고리즘을 작성해야 한다. 그런데 어떤 문제는 메모리 공간을 약간만 더 사용 eunbin00.tistory.com 1이 될 때까지 주어진 연산을 최소로 사용하는 '1로 만들기' 문제는 다이나믹 프로그래밍 알고리즘을 활용하는 대표적인 유형이다. 이 문제가 다이나믹 프로그래밍 알고리즘을 사용하여 풀 수..
썸네일 [Algorithm 완전 정복] 다이나믹 프로그래밍 | Dynamic Programming | 계속 쓰일 값은 저장해놓고 가져다 쓰자 GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소스코드 저장소입니다. - GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체 소 github.com 💡 다이나믹 프로그래밍 (Dynamic Programming, DP) 우리는 연산 속도와 메모리 공간을 최대한 활용할 수 있는 효율적인 알고리즘을 작성해야 한다. 그런데 어떤 문제는 메모리 공간을 약간만 더 사용하면 연산 속도를 매우 빠르게 증가시킬 수 있는 방법이 있다. 대표적인 방법이 바로 다이..
썸네일 [Data Science from Scratch] Ch4. Linear Algebra Linear algebra is the branch of mathematics that deals with vector spaces. 📌 Vectors 추상적으로, vector는 서로 더하고, scalar를 곱하고, 새로운 벡터를 생성할 수 있는 객체이다. 구체적으로는, vector는 어떤 유한한 차원의 공간에서의 점이다. 지금까지 보았던 data를 vector라고 생각하지 않겠지만, 그 data들은 numeric data를 대표할 수 있는 좋은 예가 된다. 예를 들어, 많은 사람들의 키, 몸무게, 나이 데이터를 가지고 있을 때, 그 데이터는 3차원의 vector로 다룰 수 있다. 혹은 학생들의 시험 성적 데이터를 4차원의 vector(exam1, exam2, exam3, exam4)로 다룰 수 있을 것..
썸네일 [Data Science from Scratch] Ch3. Visualizing Data 데이터 시각화에는 두가지 목적이 있다. To explore data - 데이터 탐색 To communicate data - 데이터 전달 matplotlib from matplotlib import pyplot as plt years = [1950, 1960, 1970, 1980, 1990, 2000, 2010] gdp = [300.2, 543.3, 1075.9, 2862.5, 5979.5, 10289.7, 14958.3] #create a line chart, years on x-axis, gdp on y-asix plt.plot(years, gdp, color='green', marker='o', linestyle='solid') #add a title plt.title('Nominal GDP') #a..
썸네일 [Python] Iterator과 Generator 💡 Iterator 'iteration'은 '되풀이, 순환'이라는 뜻의 단어이다. Python에서도 Iterator는 '순환할 수 있는 것'을 말한는데, 예를들면 리스트를 만들면 for문을 이용해서 리스트의 원소를 하나하나 꺼내 읽어올 수 있다. 즉, 순환하며 item을 하나씩 꺼내어 읽을 수 있는 것을 Iterator라고 한다. >>> mylist = [1, 2, 3] >>> for i in mylist: ... print(i) 1 2 3 여기서 mylist는 iterator이고, 순환할 수 있는 iterable이다. for [item] in [iterator]: 이렇게 for문으로 item을 하나하나 꺼내올 수 있는 모든 것은 iterator이다. (순환하며 하나하나 꺼내오기!) 💡 Generator..
썸네일 BAEKJOON #1026) 보물 알고리즘 분류: 그리디 알고리즘 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 💡 풀이 n = int(input()) lst_a = list(map(int, input().split())) lst_b = list(map(int, input().split())) lst_a.sort() lst_b.sort(reverse=True) result = 0 for a, b in zip(lst_a, lst_b): result += a*b print(result) 가장 작은 S를 만드는 방법은 큰 B의 원소가 크면..
썸네일 [python] 람다 함수 lambda function 💡 람다 함수 lambda function 람다lambda 함수는 함수의 이름 없이, 함수처럼 사용할 수 있는 익명의 함수이다. 즉, 이름을 지정하지 않아도 사용할 수 있는 함수이다. >>> f = lambda x, y : x + y >>> f(1, 4) 5 이렇게 람다 함수를 사용하면 def나 return을 작성하지 않아도 함수를 구현할 수 있다. lamda 뒤에는 매개변수를, ' : ' 뒤에는 반환할 값을 적어주면 된다. >>> (lambda x : x+1) (5) 6 lambda 함수에 바로 인수를 전달할 수도 있다. 💡 람다 함수를 사용하는 이유 람다 함수가 가장 유용할 때는 또다른 함수 안에서 익명의 함수를 사용할 때이다. (The power of lambda is better shown whe..