본문 바로가기

전체 글

 (46)
이분검색 lt=0rt=n-1while ltm: rt=mid-1 else: lt=mid+1  a라는 정렬된 숫자 리스트가 주어졌을 때lt는 왼쪽 인덱스로 0, rt는 오른쪽 인덱스로 (리스트의 크기-1)로 시작한다. 또한 mid는 lt와 rt를 더한 값을 2로 나누었을 때 몫을 말한다. while문을 lt가 rt보다 작거나 같다면 계속 진행하는데 (lt 반면 lt가 rt보다 커지면 더 이상 탐색할 구간이 없다는 의미이기 때문에 반복문을 종료해야 한다. 이 조건을 설정하지 않으면 탐색 범위가 끝난 뒤에도 불필요하게 반복문이 실행될 수 있다. 아래에서 예시를 들어보았다.'''a=[1, 3, 5, 7, 9, 10, 13, 14, 15]에서 m=5을 찾고자 할 때'''# 1)lt=0rt=8m..
스도쿠 검증 이중 for문과 중 for문을 이용하여 스도쿠의 정답 여부를 판별하였다.for i in range(9): ch1=[0]*10 ch2=[0]*10 for j in range(9): ch1[a[i][j]]=1 ch2[a[j][i]]=1 if sum(ch1)!=9 or sum(ch2)!=9: return Falsefor i in range(3): for j in range(3): ch3=[0]*10 for k in range(3): for s in range(3): ch3[a[i*3+k][j*3+s]]=1 if sum(ch3)!=9: retur..
연속된 부분 수열의 합 (투 포인터 기법 사용) 주어진 배열에서 연속된 부분 수열의 합이 m이 되는 경우의 수를 구해야 할 때.... 브루트 포스(완전 탐색) 방식을 이용한다면 O(n³)의 시간 복잡도로 시간이 초과될 가능성이 있다.# 브루트 포스 - 시간 초과for x in range(n): for y in range(x, n): sum = 0 for i in range(x, y+1): sum += a[i] if sum == m: # 합이 m이면 경우의 수 증가 cnt += 1 반면 투 포인터 방식을 이용한다면 O(n)의 시간 복잡도로 효율적이고 빠르게 답을 구할 수 있다.lt = 0 # 왼쪽 포인터 (부분 수열의 시작점)rt = 1 # 오른쪽 포인터 (부..
append()와 +의 차이 append()append(x)는 리스트의 끝에 하나의 요소 x를 추가한다. 즉 리스트의 길이가 1씩 증가한다.a=[1, 2, 3]a.append(4)a.append(5)print(a) # 출력: [1, 2, 3, 4, 5] + (리스트 병합)+ 연산자는 두 리스트를 합쳐서 새로운 리스트를 반환한다. 즉 기존 리스트가 변경되는 것이 아니라 새로운 리스트를 만들어서 c에 재할당한다.a=[1, 2, 3]a=a+[4]a=a+[5]print(a) # 출력: [1, 2, 3, 4, 5] 근데~~~~~~~~~~~~만약에 아래와 같이 두 리스트를 각각 append()와 + 연산자를 사용한다면 어떤 결과가 나올까a=[1, 2, 3]b=[4, 5]a=a+bprint(a) # 출력: [1, 2, 3, 4, 5]a.appe..
자바와 다른 파이썬 자바에서 arr[0]=0 arr[1]=1 arr[2]=2 ... arr[20]=20 같은 배열을 만들 땐for문을 사용해서 배열에 값을 직접 할당했다.int[] arr = new int[21]for (int i = 0; i  하지만 파이썬에서는 range()를 활용하여 자동으로 값이 들어간 리스트를 만들 수 있다.a=list(range(21))range(21)은 0부터 20까지의 정수 시퀀스(0, 1, 2, ..., 20)을 생성한다. 파이썬에서 range(n)은 기본적으로 0부터 n-1까지의 정수를 순서대로 생성하는 함수이다.여기에 list()를 씌우면 이터레이터에서 값을 하나씩 꺼내 리스트로 변환해준다. 즉 list(range(21))을 실행하면 [0, 1, 2, ..., 20]이 만들어진다.a=10..
회문 문자열 회문이란 앞에서 읽으나 뒤에서 읽으나 동일한 문자열을 의미한다. 어떤 문자열이 주어졌을 때 회문인지 판별하는 방법은 아래와 같다.s=input().upper()size=len(s)for j in range(size//2): if s[j]!=s[-1-j]: print("NO") # 회문 아님 breakelse: print("YES") # 회문 위에서 s[-1-j] 같은 모습을 볼 수 있는데이는 파이썬의 인덱싱 방식 중 하나로, 리스트나 문자열에서 뒤에서 첫 번째 요소(마지막 요소)를 의미한다.s="hello"print(s[-1]) # 'o'print(s[-2]) # 'l'print(s[-3]) # 'l' 반복문 뿐만 아니라 슬라이싱 방식으로도 회문 문자열을 판별할 수 ..
소수 찾기 & 숫자 뒤집기 어떤 숫자 n의 약수는 자기 자신의 절반 이하까지만 존재한다는 점을 기억하자. 즉 자기 자신을 제외한 약수는 항상 n/2 이하라는 의미이다. 예를 들어 숫자 16이 주어질 때1 x 162 x 8 을 보면 1과 자기 자신을 제외하면 16의 약수는 2 x (16의 절반)이기 때문에절반 이하까지만 존재한다.다시 말해 어떤 수 n의 약수는 자기 자신을 제외하면 항상 n/2 이하이다.def isPrime(x): if x==1: # 1은 소수 아님 return False for i in range(2, x//2+1): # x//2+1로 설정해야 x의 절반인 x/2이하까지 탐색 if x%i==0: return False else: return T..
소수 개수 구하기(에라토스테네스의 체) n=int(input())ch=[0]*(n+1)cnt=0for i in range(2, n+1): if ch[i]==0: cnt+=1 for j in range(i, n+1, i): ch[j]=1print(cnt) 1부터 n까지의 소수 개수를 구할 땐 에라토스테네스의 체 알고리즘을 이용하자 1. ch리스트를 만들어 배열을 0으로 초기화한다. (cn[i]==0 이면 소수를 의미)2. i가 2부터 n까지 반복하면서3. ch[i]==0이면 소수이므로 cnt 증가시키고4. i의 배수를 모두 1로 표시하여 소수가 아님을 체크한다.5. 최종적으로 cnt에 소수 개수가 저장되어 출력한다. True, False로 변형 가능1. ch리스트를 만들어 True로 초기화(Tr..

티스토리툴바