알고리즘/메모4 DFS / BFS 차이 두가지 모두 그래프를 탐색하는 방법이다. DFS 가장 깊은 곳까지 탐색을 마치고 돌아와서 탐색하는 방법. 예를들면 미로찾기를 할 때 한 방향으로 쭉 가고, 막다른 길이 나오면 다시 가장 가까운 갈림길로 돌아와서 다시 그 방향으로 쭉 가는 방법. 특징) DFS는 모든 노드를 방문해야할 때 사용하면 좋다.★★★ (다만, 모든 정점을 방문할 땐 DFS나 BFS나 편한걸 사용하면 되지만 DFS의 코드가 더 짧아서 보통 DFS를 추천하고, 속도는 BFS가 더 빨라서 제한시간이 빡세게 잡혀있다면 BFS를 사용하는게 좋은 경우도 있다.) DFS는 Stack 또는 재귀함수를 사용하는데 보통은 스택을 사용하길 권장한다.★ 경로마다 특징이 있는 경우 DFS를 사용해야한다. 탐색할 그래프가 엄청 크다면 DFS를 사용한다. .. 2023. 2. 4. 구) 브론즈~실버 백준 다시 볼법한 문제 예전에 실버 5 안팎의 문제들 중에 틀렸던 문제들인데, 근데 이제는 안볼듯... 그래도 정리는 해본다. 1929 - 소수 빠르게 구하기 힌트 : 소수라는 건 결국 약수를 다루는 거고, 약수들은 대칭이다. 2941 - 크로아티아 알파벳 힌트 : 변경된 알파벳들로만 이루어진 리스트를 만든다. 1157 - 단어 공부 힌트 : set을 이용. 1152 - 단어의 개수 힌트 : 공백으로 나누고, 덩어리 개수 참고 : 왜 ord == 32나 == ' ' 로는 안되는가?? -> 공백하나만 입력값으로 줄 수도 있으니 2839 - 설탕 배달 힌트 : 5의 배수가 될때까지 설탕 3kg씩 빼기 // 또는 5kg을 0봉지 1봉지 2봉지 ... list로 경우의 수 다 만들어놓기 2108 - 통계학 中 최빈값 모르겠다 ... .. 2023. 2. 2. 코딩 문제들 느낀점 list[index+1]나 list[index-1] 처럼 다룰 때는 쉽게 out of index 나곤 함. for문을 length - 1까지만 돌리는 것들이 하나의 방법이 됨 ★★중요★★ 코드 작성할 때 주의할 것은 경계값이다. 시작지점과 끝지점에서도 정상작동 하는지 체크하는 게 중요. 안그러면 IndexError: list index out of range 가 쉽게 난다. ex. index가 0일때, 1일때 혹은 끝 인덱스일 때 등등. 테스트 케이스에서 입력값이 1억처럼 큰 경우도 있으니 for문 돌릴 때 혹은 list 초기화 할 때 함부로 입력값만큼 돌리게끔 해놓으면 안됨 그럼 시간이나 메모리 초과 날 수도 있다. 3번과 같은 맥락으로, 그래서 무지성 리스트로 풀 게 아니라, 가지고 있는 값들을 어떻.. 2022. 11. 17. 코딩테스트 시간초과 해결법 (백준) 1. 코드를 PYPY3로 돌려본다. pypy3도 파이썬으로 만든거지만 속도도 빠르고 문법이 동일해서 pypy3로 바꿔주기만 하면 된다. 2. 입력을 받을 때 input()대신에 sys.stdin.readline()을 사용하자. 거의 2배는 빠르다고 한다. input()은 rstrip()을 적용해 반환하기 때문에 느리다. ※ 주의) sys.stdin.readline()는 \n도 받아오기 때문에 항상 .strip()을 해줘야한다. 3. 반복문 줄이기, 특히 중첩 for문 4. 재귀함수를 쓰는 경우, 메모이제이션 기법을 활용해보자. ▶ 이전에 계산한 값을 중복 계산하지 않기 위해 저장해놓는 기법. 팩토리얼이나 피보나치수열 처럼 기존에 한번 계산을 했던 것이 나중에 반복적으로 다시 나올 때 사용하면 효율적이다... 2022. 10. 28. 이전 1 다음