분류 전체보기
[이코테]CHAPTER 06 정렬 - 퀵정렬- 파이썬(Python)
[이코테]CHAPTER 06 정렬 - 퀵정렬- 파이썬(Python)
2022.05.151) 퀵 정렬 : 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸기. 피벗(Pivot)(교환하기 위한 기준) 사용 - 호어 분할 방식(Hoare Partition) 1. 리스트에서 첫번째 데이터를 피벗 설정 2. 리스트 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서는 피벗보다 작은 데이터를 찾기 3. 큰 데이터와 작은 데이터 교환 1. '5'보다 큰 데이터를 선택하므로 왼쪽에서부터 '5'보다 큰 '7' 오른쪽에서부터 '5'보다 작은 '4' 둘이 변경 2. '5'보다 큰 데이터를 선택하므로 왼쪽에서부터 '9' 선택 오른쪽에서부터 '2' 둘이 변경 3. '5'보다 큰 데이터를 선택하므로 왼쪽에서부터 '6' 선택, 오른쪽에서부터 '1' 선택하였는데 이렇게 두 값이 엇갈린 경우 ..
[이코테] CHAPTER 07 이진탐색- 순차 탐색, 이분탐색/이진탐색, 이진탐색트리
[이코테] CHAPTER 07 이진탐색- 순차 탐색, 이분탐색/이진탐색, 이진탐색트리
2022.05.131. 순차 탐색( Sequential Search ) : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 - 주로, 정렬되지 않는 리스트에서 데이터를 하나씩 차례대로 확인하는 방법 - 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소(데이터)를 찾을 수 있다는 장점 - 리스트에 특정 원소가 있는 지 체크할 경우, 리스트에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드 이용할 경우 import sys #순차 탐색 def sequentail_search(n,target,array): # n : 들어오는 숫자의 개수 # target: 현재 비교하고 싶은 원소 # array: 비교하고 싶은 list #하나씩 원소를 확인 for ..
리스트 안에 map 넣기 - list(map(int,input().split()))
리스트 안에 map 넣기 - list(map(int,input().split()))
2022.05.13( 참고자료 : https://dojang.io/mod/page/view.php?id=2286 ) list(map(함수, 리스트)) if 실수로 저장된 리스트를 정수 리스트로 바꾸고 싶은 경우 : a = [1.2, 2.5, 3.7, 4.6] for i in range(len(a)): a[i] = int(a[i]) print(a) #[1, 2, 3, 4] 이런 형태로 for 반복문을 활용하여 리스트 원소 하나씩 접근하여 변환해야한다. 이 때, map(함수,리스트)을 사용하여 변경할 경우 함수 안에 int, 리스트를 넣으면 한 줄로 실수형 리스트를 정수형 리스트로 변환이 가능하다 a = [1.2, 2.5, 3.7, 4.6] a = list(map(int, a)) print(a) #[1, 2, 3, 4] 또,..
백준 1920( 수 찾기 ) - Python(파이썬)
백준 1920( 수 찾기 ) - Python(파이썬)
2022.05.131) 이진탐색으로 하지 않은 코드 시간 초과난 코드: import sys sys.stdin.readline() #필요 없으므로 그냥 명시 A = list(map(int,sys.stdin.readline().split())) sys.stdin.readline() #필요 없으므로 그냥 명시 B = list(map(int,sys.stdin.readline().split())) for i in B: if i in A: print(1) else: print(0) list -> set으로 변경 import sys sys.stdin.readline() #필요 없으므로 그냥 명시 A = set(map(int,sys.stdin.readline().split())) sys.stdin.readline() #필요 없으므로 그..
백준 6198(옥상 정원 꾸미기 ) - Stack , Python
백준 6198(옥상 정원 꾸미기 ) - Stack , Python
2022.05.13dd 자바 풀이의 경우 백준 -6189 (옥상 정원 꾸미기) - Java - 스택 문제 이해 ) 예제 6개의 빌딩 수 입력 [10, 3, 7, 4, 12, 2 ] 10의 경우 3, 7, 4 까지 보는 것이 가능하고 ... blog.naver.com 풀이 0. br.readLined으로 10 읽음. result=0, stack 안에는 10이 들어와 [10] 1. 3 읽음. result=1 (들어온 수 3은 10보다 작으므로 그대로) -> 3을 볼 수 있는 숫자는 10 하나이다 -> 10은 3을 볼 수 있다. 즉, 3의 관점에서 10으로부터 보임을 당한다.그래서 +1이다 stack 안에는 [10,3] 2. 7 읽음. result=1+1 ( 들어온 수 7은 3보다 크므로,3 pop | 7은 10보다 작으므로 ..
백준 15829(Hashing)-Python(파이썬)
백준 15829(Hashing)-Python(파이썬)
2022.05.12* mod M : 모듈러 연산으로 시그마로 계산한 연산을 M으로 나눈 나머지를 의미 = %와 동일( 단, 나머지는 양수 ) ex ) 17 mod 3 17 = 3*5+1 이므로 17 mod 3 = 1 -14 mod 5 -14 = 5* ( - 3) +1이므로 -14 mod 5 = 1 자바(Java) 풀이 백준 15829(Hashing)-Java(자바) * mod M : 모듈러 연산으로 시그마로 계산한 연산을 M으로 나눈 나머지를 의미 = %와 동일( 단, 나... blog.naver.com 자바의 경우 overflow 문제가 있어서 Math.pow를 사용하지 못하는 문제점이 있었지만 Python에서는 L = input()#문자열 길이 M=1234567891 s = input() sum=0 for i in r..
백준- 11399( ATM )- Python(파이썬)
백준- 11399( ATM )- Python(파이썬)
2022.05.11그리디 설명 [ '1', '2', '3', '4', '5'] map( int, input().split()) : 문자로 처리되어 있는 것을 Int형으로 모두 바꾸기 위해서 map( int, input().split()) = map( int, [ '1', '2', '3', '4', '5'] ) = map ([ 1, 2, 3, 4, 5]) sort 사용 input();#5 숫자 받기 array=list(map(int,input().split())) array.sort() count=0 total=0 for i in array: count+=i total+=count print(total) 정렬알고리즘 사용 1. 선택정렬을 이용한 경우 ( Selection Sort ) input();#5 숫자 받기 array..
[이코테] CHAPTER 03 그리디(Greedy)
[이코테] CHAPTER 03 그리디(Greedy)
2022.05.11그리디(Greedy) 알고리즘 탐욕적으로 문제를 푸는 알고리즘( 현재 상황에서 지금 당장 좋은 것만 고르는 방법) 기준에 따라 좋을 것을 선택하는 알고리즘이므로 문제에서 "가장 큰 순서대로","가장 작은 순서대로"와 같은 기준을 제시 -> 이 기준들은 정렬 알고리즘을 사용하였을 경우 만족시킬 수 있으므로 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝 지어 출제 대표적인 예제 : 거스름돈 가정 ) 거스름돈으로 사용할 돈은 500,100,50,10원짜리 동전이 무한히 존재 손님에게 거슬러 줘야할 돈 N원일 때 거슬러 줘야 할 동전의 최소 개수 구하기 ( 단, 거슬러 줘야할 돈 N원은 항상 10의 배수 ) 문제 해설 ) 가장 큰 화폐 단위부터 돈을 거슬러 준다. -> 이때, 정렬 알고리즘을 활용하여 사용한다..
백준 -2750 (수 정렬하기) - 선택정렬, 삽입정렬, 계수정렬
백준 -2750 (수 정렬하기) - 선택정렬, 삽입정렬, 계수정렬
2022.04.262750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 정렬 설명 정렬 - 선택정렬,삽입정렬 정렬 : 데이터를 특정한 기준에 다라서 순서대로 나열 하는 것 1) 선택정렬(selection sort) 데이터가 무작위로 여러 개 있을 때, 이중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, coooco.tistory.com 1) 선택정렬로 푼 경우 #선택 정렬 a = int(input()) arr=[] for i in range(a): arr.append(int(input())) for i in range(len..
[이코테] CHAPTER 06 정렬- 선택정렬,삽입정렬- 파이썬(Python), 자바(Java)
[이코테] CHAPTER 06 정렬- 선택정렬,삽입정렬- 파이썬(Python), 자바(Java)
2022.04.26정렬 : 데이터를 특정한 기준에 다라서 순서대로 나열 하는 것 1) 선택정렬(selection sort) : 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정 반복 데이터가 무작위로 여러 개 있을 때, 이중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복 ex ) 파이썬(Python) #파이썬- 선택 정렬 array = [7,5,9,0,3,1,6,2,4,8] for i in range(len(array)): min_index=i #가장 작은 원소의 인덱스 for j in range(i+1,len(array)): if array[min_inde..