- 2
- 이니스프리
- 조회 수 2880
안녕하세요?
프로그래머스 코딩테스트 연습이 전반적으로 예전보다 효율성 심사가 강화되었다고 알고 있는데요.
제가 알고리즘 인강을 수강하고는 있지만 아직 실력이 부족해서 효율성 심사에서 걸리는 경우가 많더군요.
제 짧은 생각으로는 선형탐색보다는 이진탐색이 바람직할 것 같구요.
재귀함수 등을 사용하지 않는 방향으로 해서 함수 호출을 최소화하는 것이 효율적일 것으로 생각되구요.
몇몇 풀이를 보니 리스트의 원소를 remove 하는 방식도 피해야 할 것 같은데요.
제가 아직 알고리즘의 복잡도(Complexity of Algorithms)란 개념에 대해서 충분히 파악하지 못하고 있는 것 같은데요.
어떤 방향으로 코딩을 하는 것이 효율성 측면에서 바람직한지,
그리고 어떤 서적이나 인강으로 공부를 하면 효율적인 알고리즘을 구현할 수 있는지 여쭤봅니다 ^^
구글링해보면 프로그래머스 코딩테스트의 개별적인 문제풀이에서의 효율성을 높이는 방식은 찾을 수 있던데
물론 구체적인 사안도 궁금하지만, 알고리즘의 전반적인 측면에서 질문을 드립니다.
그럼 즐겁고 뜻깊은 연말 되세요!
답변해주실 고수님들께 미리 감사드립니다 :)
작성자
댓글 2
![title : 황금 서버 (30일) title: 황금 서버 (30일)](https://studyforus.com/./files/iconshop/33055af84f02ddedb19db038cdae0d2f.gif)
![profile image](/files/member_extra_info/profile_image/569/001/1569.png?t=1527385219)
![comment menu](/modules/board/skins/comely_board/images/icn_more.png)
![profile image](/files/member_extra_info/profile_image/819/059/59819.png?t=1717193427)
즐거운 크리스마스 보내고 계시는지요?
휴일인데 답변해주셔서 감사합니다 ^^
역시 자료구조가 중요하군요~!
연말이라 무리를 했는지 병원 신세를 지고 있어서, 요새 알고리즘 인강을 수강 못 하고 있거든요 ㅠㅠ
더 공부를 해야 humit 님께서 말씀해주신 내용을 완전히 이해할 수 있을 것 같네요.
Big-O notation에 대한 부분도 인강에서 언급하던데 아직 개념을 완전히 파악하지 못했네요.
앞으로 자료구조에 대한 공부를 더 하겠습니다~
그럼 뜻깊은 연말 되세요!! 감사합니다 ^-^
![comment menu](/modules/board/skins/comely_board/images/icn_more.png)
아무래도 자료구조에 대한 이해가 가장 중요합니다. 어떤 자료형을 쓰느냐에 따라서 수행 시간이 천차만별로 달라지거든요.
예를 들어 ArrayList와 LinkedList가 있는데, 추가/삭제를 하는 경우에 ArrayList는 느리지만 LinkedList는 빠릅니다. 반면 인덱스 조회를 하는 경우에 대해서는 ArrayList는 빠르지만 LinkedList는 느립니다.
특히 노드에서의 최단거리를 찾는 알고리즘인 다익스트라 알고리즘의 경우에 어떤 자료형을 쓰느냐에 따라서 시간 복잡도가 달라집니다.
다만 특수하게 사용되는 자료형들이 있어서 이 경우에는 모르면 풀지 못하는 경우가 있습니다. 예를 들어 2020년 카카오 블라인드 1차 테스트의 경우 효율성 테스트를 통과하기 위해선 trie라는 특수한 자료형을 사용할 필요가 있습니다.
이렇게 전반적인 자료형에 이해를 하시고 나면 그 후에 Big-O notation이라고 하는 방식으로 대략적인 수행시간을 계산합니다. 보통 10^9 이하로 나오면 안전하다고 보시면 되겠습니다.