[Python] 백준 알고리즘 1010번 - 다리 놓기 문제 출처: 1010번: 다리 놓기 (acmicpc.net) 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 접근 방법 접근은 조합으로 접근을 하였다. 1 ) 파이썬 자체 내장 팩토리얼 메서드 이용 2 ) 팩토리얼을 동적계획법으로 구하고 그 나온 수를 이용해서 조합의 구조로 답출력 동적계획법을 넣기 위해 2번의 방식을 선택했다. 문제에서 주어진 숫자의 범위는 0

백준 알고리즘 11726 - 2 x n 타일링 문제 출처 : 11726번: 2 ×n 타일링 (acmicpc.net) 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 접근 다이나믹 프로그래밍, 즉 동적 계획법을 바탕으로 접근을 해야 하는 문제이다. n이 늘어나는 경우에 맞춰 점화식을 세우고 그에 맞춰서 코드를 진행하였다. 점화식에 대해 접근을 해보자. 해당 점화식의 경우 피보나치 수열과 유사한 점화식이 등장한다. 점화식의 경우 본인의 인덱스를 i라고 하자. 그럼 i - 2 와 i - 1의 경우의 수를 합산하면 해당 인덱스의 경우의 수..

이진 탐색(binary search) vs 투 포인터(two pointer) 완전 탐색, 즉 브루트 포스로 문제를 풀어나가다 보면 어떤 문제는 시간 초과가 나는 경우가 생긴다. 이럴 경우 이진 탐색 혹은 투 포인터를 사용해서 문제를 풀이하였다. 둘 다 비슷한 방식으로 진행이 되기에 비슷한 알고리즘이라 생각하였다. 둘 다 변수를 통해 값의 이동 및 값의 탐색이기에 탐색의 시작 범위의 차이이지 시간 복잡도와 구성에는 별 차이가 없을 것이라고 생각하였다. 하지만 알고리즘을 공부하면서 알아보니 둘에게는 명확한 차이점이 존재하였다. 이진 탐색 이진 탐색이다. 이진 탐색은 처음과 끝 그리고 중간을 기준으로 탐색을 하는 알고리즘 기법이다. 이 기법은 처음(start), 끝(end), 중간(mid)을 가지고 진행을 하..

[Python] 백준 11728 - 배열 합치기 문제 출처 : https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 문제풀이 두 개의 방법을 가져왔다. 하나는 기존 파이썬의 기능을 사용한 단순 풀이다. 다른 하나는 힙 큐를 활용한 풀이이다. 힙 큐의 경우 처음에는 정렬을 할 수 있다는 점에서 사용을 했지만 생각처럼 들어가는 순서에 맞춰서 정렬이 되지 않아 tmp 임시 리스트를 만들어서 한번 heapq로 사용 후 p..

[Python] 백준 알고리즘 1302번 - 베스트셀러 문제 출처: https://www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 접근 방법 딕셔너리의 키와 값을 이용하여 접근 , sorted 메서드 정렬을 통해서 문제를 풀이하였다. 풀이 코드 import sys input = sys.stdin.readline n = int(input()) book = dict() for i in range(n): cur = input().strip() if book..

[Python] 백준 알고리즘 13417번 - 카드 문자열 문제 출처 : https://www.acmicpc.net/problem/13417 13417번: 카드 문자열 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 처 www.acmicpc.net 접근 방법 문자를 입력받고 사전 순으로 가장 빠르게 정렬해야 하는 문제이다. 문자의 경우 처음에 하나의 집합으로 입력을 받고 나서 이제 그 문자들 사이에서 사전 순으로 왼쪽 혹은 오른쪽으로 정렬하는 부분이 문제가 요구하는 풀이인듯하다. 문자를 사전 순으로 비교해가면서 나열하는 것은 아스키코드를 떠올려서 해결하였다. https..