코딩테스트준비

🔗 [백준]1504 특정한 최단 경로 📌오늘의 학습 키워드다익스트라 짬뽕✨공부한 내용 본인의 언어로 정리하기다익스트라를 사용하는 문제라고 인식했다.각 정점 별로 start ➡️ v1, v1 ➡️ v2, v2 ➡️ end 까지의 다익스트라 값을 더한다.최소값을 찾는다.📚오늘의 회고다익스트라를 구현할 때 자료구조를 deque로 했다가 heap으로 고쳤다. 1 ➡️ v1 ➡️ v2 ➡️ end 말고 1 ➡️ v2 ➡️ v1 ➡️ end 를 고려하지 않아서 고쳤다.각각의 전체 값을 구하는 과정에서 다익스트라(start, end) 이런식으로 구해서 더해주려고 했으나 그냥 각 점에서의 전체 다익스트라값을 구하고 인덱스를 찾는 방식으로 고쳤다.[🤓문제 해결 코드]import heapqfrom heapq imp..

🔗 백준 17270 연예인은 힘들어  📌오늘의 학습 키워드플로이드 - 워셜조건을 잘 읽자✨공부한 내용 본인의 언어로 정리하기플로이드 - 워셜모든 정점에서 다른 모든 정점으로 가는 최소 거리를 찾는 방법이다.모든 정점 사이의 최소거리를 2차원 배열에 저장할 것이다.2차원 배열을 INF로 초기화 한다.[ i ][ i ] 인 경우 자기 자신 이므로 0으로 설정한다. (이 문제에서는 따로 예외 처리해서 그냥 INF로 놔뒀다)각 정점을 반복문을 돌면서 이 정점를 거쳐서 출발 정점에서 목표 정점으로 향할 때의 거리가 기존 저장되어 있는 배열보다 짧으면 최소거리를 업데이트 해준다.📚오늘의 회고이 문제는 조건을 하나하나 순서대로 구현하는 것이 중요했다.지헌이와 성하의 위치는 약속장소가 되면 안된다.지헌이가 걸리는..

🔗 백준 1253 좋다  📌오늘의 학습 키워드투 포인터✨공부한 내용 본인의 언어로 정리하기투 포인터를 활용하면 N제곱이 걸릴수도 있는 문제를 N만에 풀 수 있다. 숫자 배열이 들어오면 일단 정렬을 해준다. 어떤 값에 대해서 그 값을 뺀 배열을 생성해 준다.해당 배열에서 포인터를 각각 배열의 맨 앞(제일 작은 수), 맨 뒤(제일 큰 수)로 배치한다.만약 두개의 포인터 값을 합친 것이 타겟 숫자보다 작으면 앞 포인터의 숫자를 높혀준다. - 이렇게 해주면 숫자가 커진다.만약 작다면 뒤 포인터의 숫자를 줄여준다.결론적으로 두개의 포인터의 합으로 타겟 숫자를 만들 수 있으면 통과!📚오늘의 회고2중 for문으로 시도했으나 시간 초과투포인터를 적용했으나 틀렸습니다음수인 경우를 고려하지 않아서 생긴 문제였다.[?..

🔗 백준 2211 네트워크 복구  📌오늘의 학습 키워드다익스트라 알고리즘✨공부한 내용 본인의 언어로 정리하기문제를 읽고 다익스트라 알고리즘을 생각하는 것까지는 했다.벨만-포드 알고리즘을 풀었었기 때문에 다익스트라 알고리즘을 구현할 수 있다고 생각했으나, 거리 뿐만 아니라 어떤 간선을 사용했는 지까지 출력해야 해서 비효율적으로 짰더니 시간 초과가 났다. 문명의 도움을 받아 효율을 높히기 위해서는 아래와 같이 해야한다는 것을 알았다.  deque가 아니라 heapqueue를 사용해야 함모든 간선을 각 순환마다 도는 것이 아닌(이건 벨만 포드), 그 정점과 연결된 간선들만 탐색해야 함사용한 자료구조pq: heapqueue    # 정점 탐색 용graph: [ (), () ] tuple array  # 각 ..

🔗 2020 KAKAO RECRUITMENT - 가사검색 📌오늘의 학습 키워드Trie✨공부한 내용 본인의 언어로 정리하기삼중 for문으로 쓰고 당연히 효율성 테스트에서 걸릴 것을 예상했다.질문하기를 좀 뒤져봤는데 트라이(trie)라는 단어가 많이 떠서 공부했다. Trie는 문자열 검색 시 효율을 높이기 위해서 트리 구조를 사용하는 것으로 dictionary를 사용해 구현한다.   트라이를 적용해보려고 어제 공부한 다음에 자기 전에 생각해 보는데, 트리 구조를 사용하는 것까지는 이해를 했는데 단어의 길이를 어디서 알아내는지 모르겠었다. dictionary의 key 값으로 단어의 길이를 사용하며 단어의 길이로 1차 검색 이후 트리를 타고 내려간다. 📚오늘의 회고첫번째로는 삼중 for문을 사용해 해결하려..

🔗 백준 11657 타임머신 📌오늘의 학습 키워드벨만 포드 알고리즘✨공부한 내용 본인의 언어로 정리하기벨만 포드는 최적의 상황(다익스트라)를 포함하고 있다. 벨만 포드는 다익스트라와 달리 모든 간선을 각 순환마다 확인한다. 알고리즘모든 정점의 최단 거리를 sys.maxsize로 초기화 해줬다. for 정점의 수for 간선의 수현재와 다음 정점, 간선 비용을 갖고 만약 다음 정점을 현재 비용 + 간선 비용이 다음 정점의 비용보다 작을 경우 업데이트 해줬다. 💣 음수 순환이 없다면 모든 정점 - 1 를 순환 할 동안 최단 거리가 구해져야 한다. 하지만 음수 간선이 있을 경우 무제한으로 거리를 줄일 수 있으므로 만약 정점 수 만큼의 순환에서도 거리가 업데이트 된다면 그건 순환이 있다는 뜻!📚오늘의 회고..

🔗 피보나치 수 - 프로그래머스 📌오늘의 학습 키워드코딩을 조금 해봤다 하면 꼭 해봤을 피보나치 수 문제, 재귀로 하지 말고 값을 저장해 가자!✨공부한 내용 본인의 언어로 정리하기재귀 말고 메모이제이션 그니까 기록하면서 마지막 결과를 갖다가 쓰면 된다.📚오늘의 회고어떤 문제가 있었고, 나는 어떤 시도를 했는지매우 사소한 것만 이야기해보자면 save 하는 배열에서 계속 값을 추가했었다. 근데 그냥 마지막 두값만 저장해도 문제 푸는 데 문제가 없어서 배열 값이 2개로만 유지되도록 수정해 봤다.[🤓문제 해결 코드]def solution(n): if n == 0 or n == 1: return n save = [0, 1] for i in range(2, n + 1): ..

🔗 큰 수 만들기 - 프로그래머스   📌오늘의 학습 키워드자꾸 그리디랑 완전 탐색을 착각하는 나자신... 그리디는 어려운 점이 어떤 방법이 그리디한지 알기 어려워서가 아닐까 싶다.✨공부한 내용 본인의 언어로 정리하기사실 너무 오래 걸려서 다른 분이 짜신 코드를 참고했다. 스택을 이용해 해결했다.📚오늘의 회고어떤 문제가 있었고, 나는 어떤 시도를 했는지처음에는 재귀로 모든 경우의 수를 탐색 한 다음 큰 수 를 찾으려고 했으나 시간 초과가 떴다.어떻게 해결했는지사실 어떤 것이 큰 수를 만드는 그리디 방식인지 몰라 다른 분들의 코드를 찾아봤고 스택을 통해 해결하는 방법을 찾았다. O(n)의 시간 복잡도를 가지는 방법으로 한 숫자씩 돌아가면서 만약 스택 가장 위에 있는 수가 현재 숫자보다 작으면 다 빼버리..