반응형 알고리즘5 [백준] 18352번: 특정 거리의 도시 찾기(Python) | LIM 1. 문제 2. 첫 번째 시도( 메모리 초과 발생 ) 3. 두 번째 시도( 시간 초과 발생 ) 3. 세 번째 시도( 틀린 원인과 정답 ) 📚 문제 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다. 예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자. 이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4번 도시 뿐이다. 2번과 3번 도시의 경우, 최단 거.. 2022. 12. 18. Linked List vs Array List | LIM 💡 List란 순서가 있는 데이터의 집합 📌 List 의 종류 List의 종류로는 Array List와 Linked List 가 있는데 두 개의 차이를 한번에 설명해주는 그림이 있어서 가져와 보았다. java의 ArrayList, LinkedList 비교 (출처: 생활코딩) ✔️ Array List 연속적인 공간에 순차적으로 데이터를 저장 🙂 장점 - indexing 가능 😓 단점 - 데이터 추가/삭제가 LinkedList에 비해 오래 걸린다. - 삽입/삭제가 빈번하게 일어날 시 시간이 오래 걸릴 수 있다. ✔️ Linked List 비연속적인 공간에 순서대로 데이터를 저장 🙂 장점 - 데이터의 추가/삭제가 쉽다 😓 단점 - Array List에 비해 인덱스 조회가 오래걸린다. - 순차탐색으로 조회해야하.. 2022. 10. 3. [Programmers] 전화번호 목록 (Lv.2) 프로그래머스에 '전화번호 목록' 문제는 코딩테스트 고득점 Kit에 해시 카테고리에 있다. https://school.programmers.co.kr/learn/courses/30/lessons/42577 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📚 해시 알고리즘이란? https://amazelimi.tistory.com/30?category=990184 [Python] 해시(Hash)란 무엇인가(feat. Dictionary 자료구조) | LIM 📚 해시함수 해시함수란 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매.. 2022. 9. 9. [백준] 14888번: 연산자 끼워넣기 Python (DFS, BFS) | LIM 이 문제의 경우는 순서대로 연산자에 상관없이 계산해야하기 때문에 연산자를 하나씩 뽑아서 즉, popleft를 사용하여 구현해야 한다고 생각했다. 즉 BFS를 사용하여 문제를 해결하였다. 1. 숫자는 순서의 바뀌지 않고 연산자의 순서만 바뀌기 때문에 연산자의 조합이 어떻게 올 지 부터 먼저 구해야 한다. (조합은 permutation을 이용하여 구했다. 다만, permutation의 경우 ['+','+','+','+']의 경우 모두 다르게 인식하여 경우의 수를 많이 만들기 때문에 set을 사용하여 조합을 unique한 상태로 변경해야 한다.) 2. 연산자의 특성 중 나눗셈 부분이 기존 나눗셈의 개념과는 다르기 때문에 나같은 경우 함수로 사칙연산을 구현해주었다. (생각보다 시간이 오래 걸리지 않았다..) 3.. 2021. 9. 12. [백준] 14502번: 연구소 Python (DFS, BFS) | LIM DFS와 BFS에 관련하여 설명은 너무 많기에 내가 기억하고 싶은 것만 정리하고자 한다. DFS - Depth-First Search(깊이 우선 탐색) 즉, 깊은 부분부터 탐색하겠다는 이야기이다. 깊은 부분부터 탐색한다는 말이 사실 잘 이해가 되지 않기에 그냥 DFS는 스택을 사용한다로 외웠다. DFS는 스택을 이용하는 알고리즘이기 때문에 실제 구현은 재귀함수를 이용했을 때 매우 간결하게 구현할 수 있다. 스택은 박스 쌓기에 비유할 수 있다. 박스를 쌓다가 아래에 있는 박스를 치우기 위해서는 위에 박스부터 먼저 치워야 한다. 이러한 구조를 선입후출, 후입선출 구조라고 한다. 그냥 먼저 들어온게 나중에 나간다고 생각하면 쉽다. 왜냐하면 쌓기 때문이다. DFS가 동작하는 과정은 다음과 같다. 1. 탐색 시작.. 2021. 8. 31. 이전 1 다음 반응형
