[ 알고리즘 ]36 [ 알고리즘 ] 8. 파이썬 딕셔너리 (Dictionary) 자료형 활용하기 1. Dictionary 자료형 - 키 (Key)와 값 (Value)이 한 쌍이 되어 하나의 대응 관계를 가지고 있는 자료형 - 예를 들어서, '이름': '공춘식 / '나이': 100 같은 쌍이다. - 앞쪽 요소가 Key (이름, 나이), 뒤쪽 요소가 Value (공춘식, 100)이다. - 딕셔너리와 같은 자료형을 연관 배열 (Associative array) 또는 해시 (Hash)라고 한다. - 딕셔너리는 list나 tuple처럼 순차적으로 해당 요소 값을 구하지 않고, key를 통해 value를 얻는다. 즉, 100이라는 값을 얻기 위해 순차적으로 모두 검색하는 것이 아니라 100이라는 값이 있는 곳만 사전에서 펼쳐보는 것이다. 2. Dictionary 만들기 - 기본 딕셔너리 모습은 다음과 같다. .. 2022. 2. 26. [ BOJ 오답노트 ] 18870 파이썬 : 좌표 압축 2022-02-26 1. 틀린 기록 2. 원인 분석 - 일단 문제를 아주 얕잡아 봤다. 그래서 단순히 정렬만으로는 해결할 수 없는 문제라는 것을 알고 좀 더 오랫동안 고민했다. - 입력 범위가 1 ~ 1000000이므로 되게 크기 때문에 단순히 sort를 하고 for문으로 자신보다 작은 것의 개수를 세는 방식으로는 분명히 Time Out 결과가 뜰 것이라고 생각했다. - 입력된 순서대로 출력을 해야하기 때문에, 인덱스 값을 기억해야 했다. 그래서 2차원 리스트를 사용했다. (1) 내가 생각한 풀이 - lst로 입력을 받는다. - lst_premium에 인덱스와 lst의 원소들을 순서대로 2차원 리스트 화해서 저장한다. [ [index, value], [index, value], [index, value].. 2022. 2. 26. [ 알고리즘 ] 7. 백트래킹 알고리즘 1. 백트래킹 알고리즘 - 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 - 해를 찾아가는 도중에 해가 안될 것 같으면 돌아간다. ⓐ 유망하다 (Promising) : 해가 될 가능성이 있다. ⓑ 가지치기 (Pruning) : 해가 될 가능성이 없다. - 가지치기를 얼마나 잘 하는 지에 따라서 효율성이 결정된다. 2. DFS와 백트래킹의 차이 (1) DFS (Depth First Search, 깊이 우선 탐색) - 대표적인 완전 탐색 방법이다. - 현재 지점에서 방문해야 할 곳이 있다면 재귀 호출을 이용해서 계속 이동한다. ⓐ 장점 : 무한히 깊은 곳을 찾아야 할 때 효과적이다. ⓑ 단점 : 모든 곳을 방문해야 하기 때문에 굳이 방문하지 않아도 되는 지점 (목표가 되지 않는 지점)을.. 2022. 2. 25. [ BOJ 오답노트 ] 15649 파이썬 : N과 M (1) 2022 02 24 1. 틀린 기록 2. 원인 분석 - 일단 어떻게 풀지를 모르겠어서.. 틀렸다. 백트래킹 알고리즘 관련된 문제라는데 백트래킹은 아직 접해보지 못했기 때문에... 하하하 - 그래서 이번 기회로 백트래킹 알고리즘을 배워보고, 정리도 해두었다. https://chunshikkong.tistory.com/36 [ 알고리즘 ] 7. 백트래킹 알고리즘 1. 백트래킹 알고리즘 - 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 - 해를 찾아가는 도중에 해가 안될 것 같으면 돌아간다. ⓐ 유망하다 (Promising) : 해가 될 가능성이 chunshikkong.tistory.com - 백트래킹은 dfs의 한 종류이기 때문에 깊이 탐색을 잘 이용해서 풀면 되는 문제였다. - 값들을.. 2022. 2. 24. 이전 1 2 3 4 5 6 7 ··· 9 다음
