🐳 문제 - [백준] CCW (11758번) 🐳 알고리즘 - CCW ( Counter Clock Wise ) 🎯 CCW 란 ?CCW 알고리즘은 좌표평면 위의 세 점이 이루는 관계를 알기 위한 알고리즘이다. 먼저 식부터 살펴보면 아래의 식과 같습니다.우선 위의 식이 어디서 나왔는지 알아야합니다. 위의 식은 좌표 평면 위의 세 점이 만드는 삼각형의 넓이를 벡터의 외적을 이용해 구하는 식입니다.먼저 세 점을 이용해 두 벡터를 만듭니다. 저는 (x1,y1) 을 기준으로 두 벡터를 만들어 주겠습니다.그 럼 두 벡터를 v1, v2 라고 합시다. v1 = (x2-x1, y2-y1), v2 = (x3-x1,y3-y1) 이 됩니다.이 두 벡터를 외적해 줍니다. 외적한 결과는 크기와 방향을 가집니다. 외적한 값의..
✅ 문제 - [백준] 문자열 폭발 (9935번) ✅ 처음 풀이 코드 - 시간초과import syssentence = sys.stdin.readline().rstrip()bomb = sys.stdin.readline().rstrip()while True: tmp = sentence.replace(bomb,"") if tmp == sentence: break sentence = tmpif len(sentence) == 0: print("FRULA")else: print(sentence)bomb이 있는 경우 replace 하고replace한 결과 tmp가 sentence랑 같은 경우 반복문을 멈춘다 ❌ 문제점 이런식으로 풀면 replace 메소드가 문자열의 처음부터 끝..
✅문제 - [백준] 타임머신 (11657번) ✅필요 알고리즘 개념 - Bellaman-Ford Algorithm🔵 Bellman-Ford AlgorithmBellman-Ford 알고리즘은 한 node 에서 다른 모든 node 들로 가는 최단 거리를 구하는 알고리즘이다. 🔵 Bellman-Ford Algorithm 와 Dijkstra Algorithm의 차이1. Dijkstra Algorithm는 음의 가중치를 갖지 않는 상황에서 사용한다.이때 순간순간 가중치가 가장 작은 간선을 선택하는 것이 최단거리를 보장하므로 Greedy와 Priority Que를 이용하여 구현할 수 있다. 2. Bellman Ford Algorithm은 음의 가중치를 갖는 상황에서 사용한다.이때는 가중치가 가장 작은 간선을 ..
✅문제 - 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을..
✅문제 ✅풀이 - (시간 초과)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..
