오류에 대한 지적이나 질문, 토의 환영합니다. 자유롭게 댓글 남겨주세요!.!
먼저, 알고리즘 문제를 푸는 것에 있어서 중요한 것
- 문제는 여러가지 풀이 방법이 있을 수 있는 것을 염두해야합니다.
- 항상 예외가 있을 수 있습니다.
- 생각치 못한 예외 상황을 잘 고려할 줄 알아야 합니다.
- 내가 풀어낸 답이 BEST가 아닐 수 있습니다.
- 문제를 풀었어도 다른 사람의 풀이를 보며 방법을 익히는 것이 좋습니다.
- 알고리즘 문제를 풀 때는 알고리즘 기반 지식이 중요합니다.
- 알고리즘 서적을 읽거나, 다른 사람들이 정리해 놓은 많은 웹사이트를 참고하는 것이 좋습니다.
- 풀이 방법을 어딘가에 어떻게 풀었는지 정리하는 것이 좋습니다.
- 3번에서 얘기했듯, 다른 사람의 코드를 많이 보는 것이 많이 도움이 됩니다.
- 생각치 못한 방법을 발견할 수 있고, 그것을 내 코드에도 적용해보는 것이 중요합니다.
- 문제를 풀 때, 쉽게 포기하고 답을 보는 것은 좋지 못한 행동입니다.
- 최대한 고민해보고, 도저히 못풀겠다면 다른 사람이 해결한 코드를 참고하는 것이 좋습니다.
알고리즘 재미있게 공부하기
- 알고리즘의 동작을 시각적으로 보여주는 사이트의 도움 받기
- 공부하는 알고리즘이 어디에 응용될 수 있는지 생각해보기
알고리즘 문제를 잘 푸는 방법
- 자신의 성향을 잘 파악하는 것이 중요합니다.
- 미리 생각하고 푸는게 잘 풀리는 사람
- 일단 코드를 적어야 잘 풀리는 사람
- 코드에 주석을 달거나 노트에 메모하는 습관이 좋습니다.
- 문제를 풀다보면 머리가 복잡해져서 더 잘 안풀릴 수 있기 때문입니다.
- 순서도를 그리면서 정리하는 것이 좋습니다.
- 내 예상대로 동작하지 않는다면, 디버깅을 합니다.
- print문을 활용하여 논리적으로 값이 정상적인지 확인하는 방법
- 디버거를 사용하는 방법
좋은 코드를 만드는 방법
-
간결하고 가독성 좋은 코드 만들기
- 함수형 프로그래밍
- 변수, 함수의 이름 잘 정하기
- 중복 코드 제거하기
-
가지치기
- 낭비되고 있는 로직 없애기
-
각 언어의 장점 및 특징에 맞는 코드로 작성하기
-
일관성있게 코드 작성하기
- 코드 스타일이나 변수명을 짓는 스타일에 일관성 부여하기
알고리즘 복잡도 (Algorithm Complexity)
시간 복잡도 (Time Complexity)
- 문제의 크기와 이를 해결하는 데 걸리는 시간 사이의 관계를 의미합니다.
평균 시간복잡도 (Average Time Complexity)
- 임의의 입력 패턴을 가정했을 때 소요되는 시간의 평균을 의미합니다.
최악 시간복잡도 (Worst-case Time Complexity)
- 가장 긴 시간을 소요하게 만드는 입력에 따라 소요되는 시간을 의미합니다.
Big-O Notation:
- 점근 표기법의 하나로 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현합니다.
- 알고리즘의 복잡도를 표현할 때 쓰입니다.
ex) 등등....
공간 복잡도 (Space Complexity)
- 문제의 크기와 이를 해결하는 데 필요한 메모리 공간 사이의 관계를 의미합니다.
Tip. 온라인 저지(코딩테스트)에서 걸리는 대략적인 시간, 공간
- 대체로 코딩테스트에서는 시간과 공간의 효율성을 제약하기도 합니다.
- 따라서, 제약에 따라 사용할 수 있는 알고리즘도 제한됩니다.
- 공간: int 자료형의 경우 4byte를 차지하며 4MB의 메모리 공간에 Array(List)의 최대 크기는 1,000,000 (백만)입니다.
- 시간:
- Python: C/C++보다 느리며 입력의 크기 N이 2000만에 대략 1초정도 걸린다고 생각하고 문제를 풀어야합니다. (C/C++의 경우 대략 1억이 1초)
- 따라서, 주어진 문제를 풀 때, 입력의 크기 N이 10,000(1만)이라면, 의 알고리즘에서는 Python에서는 1억 회이므로 1초안에 풀지 못합니다. 따라서 다른 알고리즘을 찾아야 합니다.
- 결론: 공간: 4MB = 백만 / 시간: 1초 = 2천만 (대략적인 공간과 시간)
이 글은 프로그래머스 스쿨 인공지능 데브코스 과정에서 공부한 내용을 바탕으로 정리한 글입니다.
주니어