오묘한

배열의 삽입, 삭제, 탐색에 드는 시간 복잡도 삽입 : 최악의 경우, 가장 앞에 삽입 시 O(N) (새로운 값 들어오면 다른 값들이 하나씩 자리 옮겨야 함. 단 맨 끝에 새로운 값 삽입하는 경우는 O(1)) 삭제: 최악의 경우, 가장 앞에 걸 삭제 시 O(N) (다른 값들이 하나씩 자리 옮겨야 함. 단 맨 끝에 삭제하는 경우는 O(1)) 탐색: 최악의 경우, 찾는 값이 맨 끝에 있을 시 O(N) (처음부터 끝까지 탐색, 그러나 인덱스로 찾을 시 k번째 원소를 찾으려면 (k-1)인덱스를 참조하면 돼서 O(1) 걸림.) 파이썬 배열 메서드의 시간 복잡도 arr.find(x) = 처음부터 끝까지 탐색함.최악의 경우 O(n) arr.remove(x) = 삭제 후 이동. 최악의 경우 O(n) 동적 배열 정적 배열..

1) 시간, 공간 복잡도 공간적 효율성 : 연산량 대비 얼마나 적은 메모리 공간을 요하는가. 시간적 효율성: 연산량 대비 얼마나 적은 시간을 요하는가. 효율성을 뒤집어 표현하면 복잡도가 되며, 이 복잡도가 높을수록 효율성은 낮아진다. 복잡도의 점근적 표기 이전에 재귀식에선 T(n)으로 표시했으나, 주로 Big-Oh 표기법 사용(예: O(n)) 1) 빅 오 표기 빅 오 표기는 복잡도의 점근적 상환이다. 가령 2a² + 2a + 2 라고 수식이 나올 경우, 상수를 빼고 O(n²)로 표기. f(n) = n²+n이고 g(n) = n³일때 f(n) = O(g(n))으로 나타낼 수 있음. f(n)의 차수가 g(n)의 차수보다 같거나 작다는 뜻. 예시) n^100 = O(2^n)은 참임. n이 충분히 크다고 가정했을..

나는 대학에서 광고를 전공한 찐 문과생이다. 하지만 3학년을 마칠 즈음 디지털 광고와 퍼포먼스 마케팅 위주로 광고 시장이 바뀌어가는 것을 보면서 소프트웨어에 대한 이해 없이는 광고 업계에서 살아남을 수 없다는 생각이 들어서, 그리고 UX나 서비스 기획 쪽으로 취업할 때 도움이 될 것 같기도 해서 부랴부랴 대학에서 복수전공으로 '문화예술소프트웨어'라는 과목을 들으며 코딩하는 모두가 아는 문장, "Hello World"를 출력하게 되었다. 나의 첫 언어는 java였다. 쌩기초부터 하나씩 익힐 때는 너무 힘들었지만, 나중에 자바로 안드로이드 앱도 만들며 개발에 흥미를 느꼈고 개발을 더 공부하고 싶다는 생각을 가지게 되었다. 그렇게 해서 대학 졸업 직후 바로 입과한 싸피(SSAFY). 시국이 시국인지라 나는 전..

알고리즘 유형별 문제 모아 풀기 첫번째는 BFS와 Stack. 그간 프로젝트 때문에 자바스크립트와 더 친해져서 알고리즘도, 파이썬도 거의 잊어먹을 지경에 이르러버렸다...! 그래서 다시 꾸준히 알고리즘 공부를 하자! 하고 다짐중. 부분집합의 합, 이 문제는 전에도 DFS로 풀었던 문제였고 경우의 수를 따지기만 해도 풀리는 문제다. 최종적으로 Pass한 정답. 전에 제출한 버전보다 실행시간도, 메모리도 높다. 92,292 kb메모리 5,647 ms실행시간 # DFS로 풀기 # {1,2,3} {2,1,3} 중복문제 => for 문 대신 num에 +1 구조로 만들고 num이 선택 됐는지 아닌지 2가지 경로로 가면 됨. # path는 디버깅용 # 오류(50/37개만 맞음) => # 10번째 라인이 틀렸었음. '..

# import sys # sys.stdin = open("input.txt", "r") from collections import deque # DFS def DFS(now): global N print(now, end=' ') for next in range(1, N+1): if next not in adj[now]: continue if visited[next] == 1: continue visited[next] = 1 DFS(next) # BFS def BFS(s): global N q = deque() q.append(s) while q: now = q.popleft() print(now, end=' ') for next in range(1, N+1): if next not in adj[now]..