본문 바로가기
반응형

Computer Science77

이진 검색 binary search의 여러 가지 형태(파이썬 코드) 1. 다음은 가장 잘 알려진 이진 검색 코드다. 찾으려는 값을 target으로 넣어주면 그 값에 해당하는 인덱스를 빠르게 찾아 리턴한다. a= [1,4,5,8,12] def binary_search(target): left = 0 right = len(a)-1 while left target: right = mid -1 else: left = mid + 1 return mid print('target:',4, 'find:',a[binary_search(4)]) print('target:',5, 'find:', a[binary_search(5)]) print('target:',8, 'find:', a[binary_search(8)]) print('target:',12, 'find:', a[binary_se.. 2021. 6. 11.
[네트워크] 네트워크 기초 개념(LAN과 WAN, 프로토콜, OSI계층과 TCP/IP계층) - 컴퓨터 간의 연결을 컴퓨터 네트워크라고 부른다. - 패킷: 컴퓨터 간 데이터를 주고받을 때 네트워크를 통해 흘러가는 작은 데이터 조각 - 큰 데이터는 작은 패킷으로 분할한다. - 랜(Local Area Network, LAN): 건물 안이나 특정 지역을 범위로 하는 네트워크 - 왠(Wide Area Network, WAN): 인터넷 서비스 제공자(ISP, ex) KT, U+)가 제공하는 서비스를 사용하여 구축한 네트워크 - 랜은 왠보다 범위가 좁고 속도가 빠르며 오류 발생확률이 낮다. - 왠은 랜보다 범위가 넓고 속도가 느리며 오류 발생확률이 높다. - 인터넷 서비스 제공자와 네트워크를 연결하기 위해 인터넷 공유기가 필요하다. - 공유기 접속 방식에는 유선 랜 방식과 무선 랜 방식이 있다. - 소규모.. 2021. 5. 22.
[알고리즘 algorithm] 플로이드-워셜 Floyd-Warshall 알고리즘 개념과 예제 그래프 알고리즘에는 대표적으로 다익스트라 알고리즘, 플로이드-워셜 알고리즘이 있다. - 다익스트라 vs 플로이드-워셜 이 둘의 차이점은 다익스트라는 한 노드에서 다른 특정 노드까지의 최단 경로를 구할 때 사용되고, 플로이드-워셜은 모든 노드에서 다른 모든 노드까지의 최단 경로를 구할때 사용된다. 우선순위큐를 활용하여 구현한 다익스트라의 시간복잡도는 O(ElogV)이다. 이때 V는 노드의 개수, E는 간선의 개수이다. 반면 플로이드-워셜은 시간복잡도가 O(n3)이다. n번의 탐색동안 n2번 값을 비교하여 업데이트해준다. 또한 다익스트라는 그리디 알고리즘인데 플로이드-워셜은 다이나믹 프로그래밍이라는 특징이 존재한다. - 플로이드-워셜 알고리즘의 개념 플로이드- 워셜의 결과는 항상 2차원 배열이다. 모든 노드.. 2021. 4. 21.
[알고리즘 algorithm] 다이나믹 프로그래밍 dynamic programming 방법론, 예제 이 글은 '파이썬 알고리즘 인터뷰'라는 책을 참고하여 작성하였습니다. - 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘. - 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우의 문제, 즉 최적 부분 구조를 갖고 있는 문제를 풀이할 수 있다. - 타뷸레이션(Tabulation): 상향식 접근법 - 메모이제이션(Memoization): 하향식 접근법 ex) 피보나치 수열 코드 작성 예제 ## tabulation def fib(n): dp[0]=0 dp[1]=1 for i in range(2,n+1): dp[i] = dp[i-1]+ dp[i-2] return dp[n] ## memoization def fib(n): i.. 2021. 4. 19.
[알고리즘 algorithm] 분할 정복 divide and conquer 활용 예제 분할 정복은 다중 분기 재귀를 기반으로 하는 알고리즘 디자인 패러다임이다. - 대표적인 분할정복 알고리즘으로 병합정렬이 있다. - 문제를 재귀로 쪼개 직접 해결할 수 있을 정도로 만든 다음, 그 하위 문제의 결과들을 조합하여 원래 문제의 결과로 만들어낸다. 분할 정복은 재귀 구조랑 거의 동일하며, 단지 넘겨주는 인자를 점점 분할하여 넘긴다. 이때 윈도우 슬라이싱이 잘 활용된다. - 분할 정렬 : 대표적인 분할 정복 알고리즘 분할 과정) 긴 배열을 정렬해야 한다 => 어렵다. 쪼개자. 두 개의 배열로 쪼갬 => 여전히 어렵다. 더 쪼개자. 각각의 배열이 다시 2개로 쪼개져 총 4개의 배열이 됨. => 계속 쪼개자. 이런 방식으로 계속 진행하다보면 마지막에는 1개의 원소만을 가진 배열로 쪼개짐. 정복 과정).. 2021. 4. 19.
[알고리즘 algorithm] 비트 연산과 비트 조작 출처: 박상길 지음, 정진호 일러스트, 책만, 2020(https://www.onlybook.co.kr/entry/algorithm-interview) - 부울 연산자 >>> True and False False >>> True or False True >>> not True False and, or, not은 기본 부울 연산자로, 이들을 조합하여 다른 보조 연산을 만들어 내는데, XOR 연산이 대표적인 보조 연산에 해당한다. >>> x = y = True >>> (x and not y) or (not x and y) False - 비트 연산자 >>> True & False # and False >>> True | False # or True >>> True ^ True # xor False >>> ~T.. 2021. 4. 15.
반응형

티스토리툴바