Tech Log

복잡도는 시간 복잡도와 공간 복잡도로 나뉜다. 시간복잡도 문제를 해결하는 데 걸리는 시간과 입력의 함수 관계. 어떠한 알고리즘 로직이 얼마나 오랜 시간 걸리는지를 나타내는 데 쓰인다. 보통 빅오 표기법으로 나타낸다. 이는 효율적인 코드로 개선하는데 쓰이는 척도가 된다. 빅오 표기법 입력 범위 n을 기준으로 로직이 몇 번 반복되는지 나타내는 것. 가장 영향을 많이 끼치는 항의 상수 인자를 빼고 나머지 항을 없앤 것이다. 속도 비교 O(1)과 O(n^2)는 입력 크기 n이 커질 수록 차이가 많이 나게 된다. 공간 복잡도 프로그램을 실행시켰을 때 필요로 하는 자원 공간의 양. 정적 변수로 선언된 것 말고도 동적으로 공간을 계속해서 필요로 하는 경우도 포함된다. 자료 구조에서 시간 복잡도 위 그림은 자료 구조에..

1. 문제 전화번호 목록 코딩테스트 연습 - 전화번호 목록 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조 programmers.co.kr 전화번호 목록의 배열이 입력으로 주어진다. 전화번호 중에서 한 전화번호 전체를 접두어로 하는 다른 전화번호가 있는지 찾는다. 접두어로 하는 다른 전화번호가 있다면, false를 return한다. 접두어로 하는 다른 전화번호가 없다면, true를 return한다. 전화번호 목록 내에서 같은 전화번호가 중복해서 들어있지 않다. 2. 풀이 해쉬(Hash) 문제이므로, 해쉬 개념을 사용해야 할 것 같다. 물론 해쉬를 사용하지 않고도 풀 수 ..