Algorithm/Baekjoon
-
[백준 1158 Python] 요세푸스 문제 파이썬 - ItisFutureAlgorithm/Baekjoon 2022. 9. 13. 20:13
m,n=map(int,input().split()) li = list(range(1,m+1)) step = n - 1 del_idx = step res = [] while len(li)>0: length = len(li) if del_idx > length - 1: del_idx %= length res.append(li.pop(del_idx)) del_idx += step print('') 문제 아이디어 1. 제거할 인덱스는 리스트의 길이 값으로 나눈 나머지 값 2. 다음의 빼야할 인덱스(del_idx)는 하나가 제거 된 리스트가 기준이기 때문에 step은 하나 작은 값이 된다.
-
[백준 18870 Python] 좌표 압축 - ItisFutureAlgorithm/Baekjoon 2022. 9. 11. 22:29
내가 쓴 정답 코드 n = int(input()) n_list = list(map(int,input().split())) n_dic = {i:0 for i in n_list} n_sorted_list = sorted(n_list) cnt = 0 prev = n_sorted_list[0] for i in n_sorted_list: if i == prev: n_dic[i] = cnt else: cnt+=1 n_dic[i] = cnt prev = i for idx,i in enumerate(n_list): n_list[idx] = n_dic[i] print(*n_list) 풀이 아이디어 1. 제일 작은 숫자가 0 임을 파악 2. 오름차순으로 +1씩 2-1. 주어진 값에 대하는 순서를 딕셔너리에 업데이트 3. ..
-
[백준 9020번 python] 골드 바흐의 추측Algorithm/Baekjoon 2022. 9. 5. 19:59
정답 코드 li=[0]*10001 for num in range(2,10001): for i in range(2,int(num**0.5)+1): if num % i == 0: li[num] = 0 break else: li[num]=num for _ in range(int(input())): n = int(input()) st = 0 for i in range(n//2,0,-1): if li[i] != 0: st = i break sosu_list = sorted(set(li[:n+1])) st_idx=sosu_list.index(st) brk=False for idx,i in enumerate(sosu_list[st_idx::-1]): for j in sosu_list[idx:]: if i+j == n..
-
백준 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을 ..
-
백준 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]..