전체 글
-
백준 1920번 수 찾기 파이썬 pythonAlgorithm/Baekjoon 2022. 4. 29. 16:04
선행 지식 1. List 와 Set에서의 in 연사자 성능 차이 더보기 list 자료형에서는 in 연산자의 시간 복잡도는 O(n)이다. ==> 앞에서 부터 차례로 하나하나 비교해 나간다. set 자료형에서는 in 연산자의 시간 복잡도는 O(1)이다. ==> 어떤 숫자를 찾던 같은 시간이 걸린다. ex) list(range(1,1000000))와 set(range(1,1000000)) (1번 상황) 숫자 1을 찾아라 1 in 리스트 >>> 0초에 가까운 시간 1 in set >>> 0.5초 (예시) (2번 상황) 100000 in 리스트 >>> 100초 100000 in set >>>0.5초 정리 List 자료형은 선형적으로 시간이 늘어나고, Set 자료형은 일정하다. 결론 많은 양의 데이터에서의 in을 ..
-
백준 7568번 python 파이썬, 덩치카테고리 없음 2022. 4. 28. 19:48
-문제 요약- 키와 몸무게 둘 다 커야 덩치가 크다고 판단한다. 자신보다 더 큰 덩치의 사람이 k명이라면 그 사람의 덩치 등수는 k+1이 된다. -문제 풀이 방법- 1. 몸무게와 키를 묶어서 배열에 넣는다. 2. 순회하면서 비교해 등수를 매긴다. 3. 출력. m = int(input()) tupli = [tuple(map(int,input().split())) for i in range(m)] #listcomprehension for i in tupli: rank = 1 for n in tupli: if i[0] < n[0] and i[1] < n[1]: # 시간 복잡도 O(n^2) rank += 1 print(rank, end=' ') 다른 문제 풀이 -- 대부분 비슷 N = int(input()) p..
-
백준 1526번 python 가장 큰 금민수Algorithm/Baekjoon 2022. 4. 19. 15:52
https://www.acmicpc.net/problem/1526 문제 금민수는 어떤 수가 4와 7로만 이루어진 수를 말한다. N이 주어졌을 때, N보다 작거나 같은 금민수 중 가장 큰 것을 출력하는 프로그램을 작성해라. ---------- 입력 첫째 줄에 N이 주어진다. N은 4보다 크거나 같고 1,000,000보다 작거나 같은 자연수이다. ------- 출력 첫째 줄에 N보다 작거나 같은 금민수 중 가장 큰 것을 출력한다. ------ 간결한 답: n=input() while True: for i in n: if i not in'47': n=str(int(n)-1) break else: #for문이 break 등으로 끊기지 않고, 끝까지 수행 되었을 때 수행하는 코드는 else문에 담는다. print..
-
[백준 파이썬 1259번] 팰린드롬수 알고리즘 pythonAlgorithm/Baekjoon 2022. 4. 14. 18:46
문제 : 어떤 단어를 앞에서 뒤에서 읽어도 똑같은 것을 팰린드롬이라고 한다. 수도 팰린드롬으로 취급할 수 있는데, 앞에 무의미한 0이 올 수도 있지만 이번 문제에서는 올 수 없다고 한다. 답 : while True: a = input() count=0 if a =='0': break for i in range(len(a)//2): #반절만 비교 if a[i] != a[-(i+1)]: count+=1 break print('yes' if count==0 else 'no') 주목할 점 : 반만 확인하면 전부 확인하는 것이다. a =input() for i in range(len(a)//2) 주어진 숫자의 길이가 홀수, 짝수일 경우 생각하는 것. for i in range(len(a)//2): # 반으로 나누..
-
[백준 파이썬 1225번] 이상한 곱셈 알고리즘 pythonAlgorithm/Baekjoon 2022. 4. 14. 16:17
문제 : 정수 A, B가 주어지고 A에서 한자리 B에서 한자리를 뽑아 곱한다. 가능한 모든 조합을 더한 수를 출력한다. 답 : #입력 예시) 123 45 a,b = map(list, input().split()) # ['1','2','3'], ['4','5'] b_sum = sum(map(int,b)) # 데이터 값이 문자열이므로 형변환 필수 a_sum = sum(map(int,a)) print(a_sum*b_sum) 주목할 점 : A, B를 문자열로 받아 단순하게 이중 for 문을 사용하면 최대 길이가 10000자릿수라서 아직 복잡도를 잘 모르긴 하지만 복잡도가 O(n^2)이 되고 시간 초과가 뜬다. (10000자리를 10000이하로 보고 싶은 대로 보지 말자)
-
[백준 파이썬 1100번] 하얀칸 알고리즘 pythonAlgorithm/Baekjoon 2022. 4. 13. 23:44
문제 : 체스판이 8*8로 주어지고 하얀칸 위에 몇 개의 말이 있는지 출력하는 문제 답 : ches=[input() for i in range(8)] count = 0 for row in range(8): # row는 행 인덱싱에 활용 for col in range(8): # col은 열 인덱싱에 활용 if (row+col) % 2 == 0 and ches[row][col] == 'F': #하얀칸 위치 확인과 체스말 존재 확인 count += 1 print(count) 주목할 부분 : 1. 행(row)과 열(col)이 8*8로 정해짐 2. 열과 행의 인덱싱 방법 [문자열,문자열,,,문자열]으로 받아 2차원 배열의 기능을 사용하여 인덱싱한다. 문자열리스트 = ['사과','당근','수박'] 문자열리스트[0]..
-
[백준 파이썬 1110번] 더하기 사이클 알고리즘 pythonAlgorithm/Baekjoon 2022. 3. 31. 19:17
조건 1. 0보다 크거나 같고, 99보다 작거나 같은 정수 >>> 0이 주어질 경우 생각 2.10보다 작으면 앞에 0을 붙여 두 자리 수로 만든다. 3. 각 자리의 숫자를 더하고, 앞 숫자의 오른쪽자리 수와 현재 더한 값의 오른쪽 수를 붙여 새로운 수를 만든다. 발상 처음의 발상 문자열로 받아서 사용하려고 하다가 로직을 머리로 짜려다 보니, 형변환을 자주해줘야하는 점과 헷갈리고 귀찮아진다는 점이 마음에 들지 않아, 숫자로 풀어보려 노력함. 두 번째 발상 10의 몫과 나머지를 활용하면 쉽겠다라고 생각했다. 조건 1번 : 0이 들어올 때, 몫은 0 나머지는 0 두 개의 합 0으로 한 번의 실행으로 종료 조건 2번 : 1~9이 들어올 때, 몫은 0 나머지 1~9로 문자열이 아닌 정수라 0을 붙여준다는 생각을 ..