문자열로 슬라이싱해서 sum으로 더해서 구하면 O(n^2)이 된다 또 한쪽의 길이가 0이 되도록 자르면 안되고 무조건 1개 이상의 원소는 포함해야 된다 하나는 하나만 포함하고 하나씩 수를 더해주는 반면 긴 부분에서는 앞에서부터 하나씩 빼서 차이를 구해주면 된다 timecomplexity: O(n) def solution(A): # write your code in Python 3.6 first=A[0] second=sum(A[1:]) res=abs(first-second) for i in range(1,len(A)-1): first+=A[i] second-=A[i] res=min(res,abs(first-second)) return res
Question: https://codility.com/demo/take-sample-test/binary_gap # you can write to stdout for debugging purposes, e.g. # print("this is a debug message") def solution(N): cur,max_gap=0,0 for i,e in enumerate(str(bin(N)[2:])): if e=='1': max_gap=max(max_gap,cur) cur=0 else: cur+=1 return max_gap
한 가지 없는 원소를 찾는 것 (1부터 시작해서) 빈배열일 경우, 마지막이나 첫 원소가 없을 경우, 홀수개의 원소, 짝수개의 원소일 경우를 모두 체크해주는 경우의 수를 공부할 수 있었다 def solution(A): if not A: return 1 # 빈 배열은 당연 1을 리턴 A.sort() # 정렬해서 중간에 없는 수를 찾아보자 num=1 for i,e in enumerate(A): if num!=e: return num else: num+=1 return num # 마지막 원소가 없는 경우 다른 사람 풀이인데 이전에 bitwise로 계산하는 문제같다 def solution(A): length = len(A) xor_sum = 0 for index in range(0, length): xor_sum..
1 ~ x까지 나오면 현재의 인덱스(초)를 리턴해준다 O(n) # you can write to stdout for debugging purposes, e.g. # print("this is a debug message") import collections def solution(X, A): # write your code in Python 3.6 dict=collections.defaultdict(int) for i,e in enumerate(A): dict[e]=1 if len(dict)==X: return i return -1
www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 최소 경로를 bfs로 찾는 법 from collections import deque def bfs(): dq=deque() dq.append((0,0)) vis[0][0]=1 cnt=1 while dq: x,y=dq.popleft() if x==n-1 and y==m-1: return vis[x][y] for k in range(4): xx,yy=x+dx[k],y+dy[k] if xx=n or yy=m: continue if vis[xx][y..
홀수번 등장하는 숫자를 반환하는 대표 문제다 def solution(A): result=0 for num in A: result^=num return result
10진수에서 xor 연산은 0^0 = 0 4^4=0 4^0=4 짝수번 등장은 0으로 초기화되고 홀수번은 다시 자기 자신으로 초기화된다 class Solution: def singleNumber(self, nums: List[int]) -> int: result=0 for num in nums: result^=num return result
이진탐색으로 하나만 정렬하고 bisect으로 찾는 방법이 있고 투 포인터로 둘 다 정렬한 다음 같이 인덱스 0으로 시작해서 작은 배열의 인덱스를 1씩 증가시키는 방법이 있다. 중복이 없어야 되므로 set()을 사용한다 class Solution: def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: nums1.sort() nums2.sort() result=set() i=j=0 while i
가장 작은 원소가 있는 인덱스가 피봇 위치이고 그 위치를 기준으로 값을 찾되, left, right 인덱스는 mid를 기준으로 계산한다 *mid 와 mid_pivot을 따로 계산해준다 class Solution: def search(self, nums: List[int], target: int) -> int: left,right=0,len(nums)-1 while leftnums[right]: left=mid+1 else: right=mid pivot=left left,right=0,len(nums)-1 while left
HTTP http는 www에서 통신하는데 사용하는 프로토콜이다 http는 웹서버로부터 이미지,html 페이지, 텍스트파일, mpeg 동영상 등의 대량의 정보를 사용자들의 pc에 설치된 웹브라우저로 옮겨준다 신뢰성 있는 데이터 전송 프로토콜(TCP)를 사용하기 때문에 전송 중 데이터가 손상되지 않음을 보장한다 웹 클라이언트와 서버 웹 서버는 http프로토콜로 통신하기 때문에 http서버라고 불린다 클라이언트는 http요청을 서버에 보내고 서버는 요청된 데이터를 http응답으로 돌려준다 이 둘은 www의 기본 요소이다 리소스 웹 서버는 웹 리소스를 관리한다 리소스는 정적 파일과 동적 파일이 있다 정적 파일: text파일, html파일, 워드 파일 등 동적 콘텐츠 리소스: 사용자가 누구고 어떤 정보, 몇 시인..