✅문제 - AC(5430번) ✅아이디어🔵문제 조건시간제한이 1초 이므로 연산을 2000만 번 안에 끝내야 한다. (Python 은 1초에 2000만 번의 연산을 한다고 가정하자)이때 함수의 최대 길이가 100,000이므로 시간 복잡도가 O(N^2)을 넘으면 시간 초과에 걸리게 된다.🔵실패 했던 아이디어실제로 R인 경우에는 reverse를 D인 경우에는 pop을 실행했다. 이때 함수의 길이만큼 for문을 돌려야 하고 그 안에서 if 문을 돌려야 하므로 시간 복잡도가 O(N^2)이 된다.정말 처참한 결과다🔵성공한 아이디어실제로 pop 이나 reverse를 진행하지 않는 방법을 생각했다.1. 함수에서 RR이 나오면 순서가 바뀌지 않으므로 입력받은 함수에서 replace("RR","")을 통해 모든 RR을..
✅문제 - 나머지 합 ✅필요 알고리즘 개념 - 누적합🔵Prefix Sum (구간 합)◼ 누적합 문제의 경우 Prefix Sum을 이용해 문제를 푼다. 아래의 예시를 보자num_list = [1,2,3,4,5]accum = 0for i in range(n): accum += num_list[i] print(accum,end=" ")위와 같은 코드를 실행시키면 아래와 같은 결과를 얻을 수 있다.✅코드import sysinput = sys.stdin.readlinen,m = map(int,input().rstrip().split())num_list = list(map(int,input().rstrip().split()))rem_list = [0 for i in range(m)]rem_list[0]..
✅문제 - 평범한 배낭(12865번) ✅필요 알고리즘 개념 - 다이나믹 프로그래밍(Dynamic Programming)🔵What is Dynamic Programming ? ◼다이나믹 프로그래밍이란 한 번 해결된 문제의 정답을 메모리에 기록하여, 한 번 계산한 답은 다시 계산하지 않도록 하는 기법이다. ◼Dynamic Programming Table 을 만들어 상태를 이전 결과들을 저장한다. ◼푸는 방식은 크게 2가지 방법으로 바텀업/탑다운 방식으로 풀고 탑다운 방식은 주로 재귀함수를 이용 한다. ✅코드import sysinput = sys.stdin.readlinen,k = map(int,input().rstrip().s..
✅문제 - 문자열 집합(14425번)✅오늘 배운점문제에서 두 집합 간의 비교를 위해 in method를 사용하였다.하지만 처음에 list에서 in method를 사용한 경우에 시간이 3724ms나 소요 되어 문제가 있다고 판단했다.그래서 list를 set로 변경하였더니 시간이 116ms로 감소하였다.이유는 파이썬 홈페이지에서 확인할 수 있었다set 자료형에서 in method의 시간복잡도는 최선: O(1) 최악: O(N)이고list 자료형에서 in method의 시간복잡도는 O(N)인 것을 확인할 수 있었다. ❗❗❗ 앞으로 성분의 포함 여부를 사용할 때는 set를 사용하자!! ✅첫 코드 - (시간 3724ms)import sysindex = int(sys.stdin.readline().rstrip()..
✅문제 ✅풀이 - (시간 초과)import syssys.stdin.readline()num_list = list(map(int,sys.stdin.readline().rstrip().split()))rank = sorted(set(num_list))for i in num_list: print(rank.index(i),end=" ") 해설입력 받은 수를 set()를 통해 중복을 제거하고 정렬하여 for 문을 통해 index를 찾아 출력하였다. ❗❗❗시간 초과 발생 이유 ( .index() method ) 마지막 출력문에서 num_list 를 탐색하며 index(method)를 사용하는데.index() method는 리스트를 순회하며 값을 찾으므로 시간 복잡도가 O(N)이 된다.👎.index() me..
문제 ✅중요 개념계수 정렬 ( Counting Sort ) 계수 정렬이란 sort 메소드를 이용하는 것이 아니라 정렬하려는 List의 값 중 가장 큰 값을 List의 size + 1을 크기로 가지는 List를 생성하여 index를 정렬하는 숫자의 해당 숫자로 사용하여 Sorting을 하는 방법을 말한다.👍자세한 내용은 링크를 참고해 주세요 -- https://www.programiz.com/dsa/counting-sort Counting Sort (With Code in Python/C++/Java/C)Counting Sort Algorithm In this tutorial, you will learn about the counting sort algorithm and its implement..
