
📎 간략한 문제 정리 주어진 재귀 함수가 속도 이슈 없이 작동하도록 만듭니다. if a 20, then w(a, b, c) returns: w(20, 20, 20) if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1) 📈 문제 분석 전형적인 DP 문제인 피보나치와 유사한 형식입니다. 단순 반복이 아니라 결과를 저장하면서 꺼내오는 구조로 작성해야 합니다. 🙋♂️ 내가 처음 생각한 해결 방법 pseudo code에 나온 그대로 구현하지만 결과를 ..

📎 간략한 문제 정리 N개의 좌표 X1~XN이 있을 때 X1'는 X1보다 작은 서로다른 요소의 개수를 의미합니다. 📈 문제 분석 주어진 배열을 정렬한 후 문제를 처리하면 쉽게 접근할 수 있습니다. 🙋♂️ 내가 처음 생각한 해결 방법 가장 단순하게 생각해보면 전체를 순회하며 기준을 세우고, 자신을 제외한 다른 요소들을 검색해보며 더 작은 값이면 count += 1의 로직을 구현할 수 있습니다. 하지만 이것은 O(N^2)이며 주어진 조건 1 Stack의 전형적인 문제 중 특정 요소의 왼쪽 값 중 자신보다 크면서 인덱스가 가장 큰 요소를 찾는 문제가 있습니다. 이 문제처럼 왼쪽만 관찰하며 더 큰 값일때만 pop하는 해결방식을 활용한다면 O(N)이 가능할 수 있을 것 같습니다. Counting Sort..

📎 간략한 문제 정리 Back Tracking에서 가장 유명한 문제 중 하나인 N-Queen을 다시 풀어보았습니다. 체스에서 Queen은 수직, 수평, 대각선 방향으로 거리의 제한없이 이동할 수 있을 때, N개의 Queen을 배치할 수 있는 모든 경우의 개수를 출력하는 문제입니다. 📈 문제 분석 이 문제의 포인트는 크게 두가지 입니다. BackTracking을 어떻게 구현할 것인가 Queen을 배치 가능한지 여부 판단하기 Back Tracking 부분은 N과 M 문제와 크게 다르지 않습니다. 반복을 하며 조건을 확인하는 BackTracking의 기본 구조를 가지고 있습니다. 방문 여부를 체크하고, 배치가 완성되면 배치 가능한 모양이 한개 생성되므로 결과에 +1을 해줍니다. 더 까다로운 포인트는 2번인데,..

📎 간략한 문제 정리 자연수 N과 M이 주어지고, 아래 조건을 만족하는 길이가 M인 수열을 모두 구합니다. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 📈 문제 분석 N과 M(1)과 거의 비슷한 문제입니다. 오름차순을 이루는 부분 수열을 찾는 문제로 중복이 없고, 부분 수열의 크기가 정해진 것이 포인트입니다. 🙋♂️ 내가 처음 생각한 해결 방법 사실 파이썬에는 모듈인 itertools에 combination 함수가 존재합니다. 그래서 N의 요소에서 M개를 뽑는 것은 어렵지 않지만 일부러 이 방법을 사용하지 않았습니다. 이 모듈을 사용하지 않을 때 필요한 것은 모든 요소를 접근하며 조건에 만족할 경우 결과에 넣는 작업입니다. 이 때 사용되는 백트래킹(Back..

📎 간략한 문제 정리 위의 그림처럼 한 변의 길이가 2의 거듭제곱꼴인 N의 정사각형(NxN)이 존재합니다. 이 사각형은 길이가 1인 단위 정사각형으로 이루어져 있으며 색깔을 가집니다. 만약 이 정사각형이 모두 색깔이 같다면 자르지 않지만, 하나라도 색깔이 다른 부분이 있다면 종이 가로 세로의 가운데를 잘라 4등분하여 위의 작업을 반복합니다. 모든 작업이 완료되면 흰 종이(0으로 마킹)의 개수과 파란 종이(1로 마킹)의 개수를 출력합니다. 📈 문제 분석 전형적인 분할 정복 문제입니다. 특정 시점에서 조건에 맞는지 확인(모두 같은 색)한 후, 조건에 맞으면 추가 작업을 진행하지 않고, 조건을 만족하지 않으면 재귀적으로 문제를 다시 해결해나가는 구조입니다. Merge Sort(병합 정렬)처럼 개념으로 배울 때..

팰린드롬 연결 리스트(Palindrome Linked List - 234 from Leet Code) Reference: Palindrome Linked List 🎯 문제 의의 문제 자체의 난이도는 높지 않았습니다. 연결 리스트로 구현된 자료를 반환하며 리스트에 담아 처리하면 기존의 팰린드롬 문제와 다를게 없기 때문이고, 또한 이러한 풀이가 다른 방식의 풀이와 속도 측면에서 큰 차이가 나지 않기 때문에 이 방법으로도 충분한 풀이입니다. 아래는 제 풀이입니다. node를 순회하며 값을 head_list에 담아 처리하고, head_list의 palindrome 여부를 판단합니다. 위의 return문의 Boolean은 요소를 하나하나 탐색하며 팰린드롬 여부를 파악하는 것보다 더 빠른 효율을 보여줍니다. 기능적..

문제 www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 상황 - 앞서 풀이한 오큰수에서 크기로 비교하는게 아니라 출현 횟수를 기준으로 판단하는 차이밖에 없다. 해결 전략 - stack을 활용하여 왼쪽을 쳐다봐서 횟수의 내림차순을 유지하는 구조로 코딩한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 from sys import stdin from collections import Counter input = stdin.readline n = ..
- Total
- Today
- Yesterday
- NumberofDiscIntersections#Codility#Sort#Python
- 종이자르기#분할정복#BOJ#Python
- django#slicing
- filter#isalnum#lower
- 섬의개수#백준알고리즘#Python
- 순열사이클#BOJ#Python
- 공유기 설치#BOJ#이분탐색#Python
- PassingCars#Codility#Python
- django
- Swift#Tuples#Range
- 나무자르기#BOJ#이분탐색#Python
- Triangle#Sorting#Codility#Python
- 암호코드#dp#BOJ#Python
- 배열합치기#분할정복#BOJ#Python
- 반복수열#백준알고리즘#Python
- Distinct#Codility#Python
- 터틀비치#리콘#xbox#controller
- 날짜 계산#BOJ#완전탐색#Python
- 리모컨#완전탐색#BOJ#Python
- 미로 탐색#백준알고리즘#Python
- Brackets#Stacks and Queues#Codility#Python
- N으로 표현#DP#Programmers#Python
- 파이썬알고리즘인터뷰#4장
- 토마토#백준알고리즘#Python
- API#lazy#
- 쿼드트리#BOJ#분할정복#Python
- 텀 프로젝트#백준알고리즘#Python
- 병든 나이트#BOJ#탐욕법#Python
- 랜선자르기#이분탐색#BOJ#Python
- 백준 알고리즘#BackTracking
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |