🐳 이번 주 한 일 SSAFY 면접 ! 운동기록 서비스 Record Table TDD 구현 1일 1커밋 1일 1알고 알고리즘 2문제 블로그 글 작성 🐳 회고록 이번 주는 알고리즘은 트리에서의 동적 계획법을 시작했다. 단계별 문제 풀어보기 38번 시작 ! 그리고 기하 문제 선분의 교차 문제를 풀어보았다. 삼각형 넓이를 구할 때 사용하는 외적을 이용해 Counter Clock Wise 를 구현해 선분의 교차를 검증하는 문제였다. 쉽지 않은 플레5 문제였지만 결국 해결 ! 요즘 알고리즘이 많이 성장한 기분이다 ! 예전보다 구현실력이 많이 좋아진 것 같다. 이렇게만 가자 ! 그리고 이번 주 화요일에는 대망의 ... 사피 면접이 있었다... 아쉬움이 안남는다면 거짓말이겠지만 그래도 후회없게 준비한 것 같다 ! 일..
🐳 문제 - [백준] 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 메소드가 문자열의 처음부터 끝..
💻문제 5문제 ( 알고리즘 4문제 + SQL 1문제 ) 1. 구현 - 난이도(실버) 2. 그리디 - 난이도(골드5) - ( 도형을 이용한 구현 문제였습니다 ) 3. 구현 - 난이도(골드4) 4. 다익스트라 - 난이도(골드1 이상 ... ? ) - ( 제약 조건이 많은 다익스트라 알고리즘이었습니다. ) 5. SQL : UNION 개념을 물어보는 문제였습니다. 👍후기 그래도 백준 플레티넘까지 공부한 보람이 있었다. 1,3,5번 문제는 풀만 했던 것 같다. 1번은 못 풀면 불합격이라고 생각이 들 정도로 쉬운 문제였고 3번은 살짝 까다로웠습니다. 5번 ( SQL )의 경우 처음엔 Outer Join으로 푸는 문제인 줄 알았으나, SELECT * 를 통해 전체 데이터를 출력해 보니 오류가 있다는 것을 알아냈다. ..
✅문제 - 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을..
문제 ✅중요 개념계수 정렬 ( 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..
