본문 바로가기
반응형

Algorithm/파이썬 알고리즘 문제풀이 (코딩테스트대비)20

[파이썬 알고리즘 문제풀이] : 이분 검색 문제 n개의 숫자가 주어진다. n개의 수를 오름차순 정렬하고 n개의 수 중 한 개의 수인 m이 주어지면 이분 검색으로 m이 정렬된 상태에서 몇 번째에 있는지 구하라. 해결 주어지는 수의 총 개수는 n 정렬하고 몇 번째에 있는지 찾아야 하는 수는 m n의 수 만큼 주어지는 랜덤 수는 a --- m은 a에 꼭 포함되어 있다. 조건을 먼저 잘 생각해 본다. a.sort() 정렬된 상태에서 m이 몇 번째에 존재하는지 찾아야 한다. 주어지는 수들이 들어있는 list인 a를을 일단 정렬한다. lt = 0 rt = n - 1 처음(lt)과 끝(rt)를 선언해 준다. while lt m: rt = mid - 1 else: lt = mid + 1 a[mid]가 m과 같으면 값을 출력하고 브레이크를 걸어준다. n, m =.. 2022. 5. 4.
[파이썬 알고리즘 문제풀이] : 봉우리 코딩 테스트 문제 풀이 문제 이름 : 봉우리 지도 정보가 N*N 격자판이 주어진다. 격자판에 있는 숫자 중 상하좌우에 있는 숫자보다 큰 숫자는 봉우리 지역인데 이 봉우리 지역이 몇 개인지 구하라. 격자의 가장 자리는 0으로 초기화가 되어 있다고 가정한다. n = int(input()) a = [list(map(int, input().split())) for _ in range(n)] dx=[-1, 0, 1, 0] dy=[0, 1, 0, -1] a.insert(0, [0]*n) a.append([0]*n) for x in a: x.insert(0, 0) x.append(0) cnt = 0 for i in range(1, n+1): for j in range(1, n+1): if all(a[i][j] > a.. 2022. 1. 19.
[파이썬 알고리즘 문제풀이] : 사과나무 문제 n*n 격자판으로 된 과수원에서 다이아몬드 모양의 격자판만 수확하고 수확한 것의 총 수를 구한다. 주의 풀이 n = int(input()) a = [list(map(int, input().split())) for _ in range(n)] res = 0 s = e = n//2 for i in range(n): # j for문은 e까지 돈다. for j in range(s, e+1): res += a[i][j] if i < n//2: s -= 1 e += 1 else: s += 1 e -= 1 print(res) 2022. 1. 2.
[파이썬 알고리즘 문제풀이] : 격자판 최대합 문제 n * n의 격자판이 주어지면 각 행, 열, 두 대각선의 합 중 가장 큰 합을 출력한다. 주의 풀이 n = int(input()) a = [list(map(int, input().split())) for _ in range(n)] # 전역 변수 largest = -2147000000 for i in range(n): sum1 = sum2 = 0 #sum1은 행, sum2는 열 for j in range(n): sum1 += a[i][j] sum2 += a[j][i] # 가장 큰 경우를 구해야 하니 largest에 큰 값을 계속 갱신해 준다. if sum1 > largest: largest = sum1 if sum2 > largest: largest = sum2 # 대각선 값 구하기 sum1 = su.. 2021. 12. 31.
[파이썬 알고리즘 문제풀이] : 수들의 합 문제 N개 수로 된 수열이 있을 때 i번째 수부터 j번째 수 까지의 합이 주어지는 값과 같은 경우의 수를 구하시오. 주의 풀이 # 입력 받는 변수 n, m = map(int, input().split()) a = list(map(int, input().split())) # 알고리즘 풀이에 사용 될 전역 변수 lt = 0 rt = 1 tot = a[0] cnt = 0 # 알고리즘 로직 while True: # while문에 True값을 줘서 무한 반복문을 완성시킨다. if tot 2021. 12. 31.
[파이썬 알고리즘 문제풀이] : 두 리스트 합치기 문제 오름차순으로 정렬이 된 리스트가 주어지고 두 리스트를 그대로 합쳐 오름차순이 정렬된 형태로 출력한다. 주의 풀이 n = int(input()) a = list(map(int, input().split())) m = int(input()) b = list(map(int, input().split())) p1 = p2 = 0 c = [] while p1 < n and p2 < m: # 오름 차순으로 정렬하기 위해 하나씩 값을 비교한다. if a[p1] 2021. 12. 30.
[파이썬 알고리즘 문제풀이] : 카드 역배치(정올 기출) 문제 1부터 20까지 오름차순 정렬 된 카드가 주어지고 주어지는 두 수의 범위 내 카드들을 역으로 배치해준다. 주의 풀이 #a, b = map(int, input().split()) # 스왑하는 방법이다. # a, b = b, a # print(a, b) a = list(range(21)) #_를 통해 변수 없이 반복을 하게 된다. => 시간이 좀 더 단축하게 된다. for _ in range(10): s, e = map(int, input().split()) # +1을 더해줘서 반복하는 수를 맞춰준다. for i in range((e-s+1)//2): # 스왑을 해준다. a[s+i], a[e-i] = a[e-i], a[s+i] a.pop(0) for x in a: print(x, end=' ') 2021. 12. 30.
[파이썬 알고리즘 문제풀이] : 숫자만 추출 문제 문자, 숫자가 섞인 문자열을 입력받고 숫자만 추출해 자연수로 만들어 약수를 출력해 준다. 주의 풀이 s = input() # 누적을 위한 전역변수 res = 0 for x in s: # isdecimal은 0부터 9까지만 찾아준다. # isdigit은 제곱까지 다 찾아준다. if x.isdecimal(): res = res*10+int(x) print(res) cnt = 0 for i in range(1, res+1): if res%i==0: cnt += 1 print(cnt) 2021. 12. 29.
[파이썬 알고리즘 문제풀이] : 회문 문자열 검사 문제 문자열을 입력 받고, 회문 문자열 검사를 한다. 단, 대소문자 구분을 하지 않는다. 주의 파이썬 특징을 살리는 코드로 간단하게 작성할 수도 있으나 가능하면 풀어서 쓰는 게 좋다. 풀이 n = int(input()) for i in range(n): s = input() # s를 대문자화 시켜준다. s = s.upper() ############ 풀어서 쓴 코드 이 코드로 이해하는 게 좋다. #################### #s열의 길이를 구해준다. size = len(s) # 처음과 끝, 짝지어 비교하면 되므로 나누기 2를 해준 수 만큼 비교해 준다. for j in range(size//2): # 맨 뒤에서 리스트에 접근할 때 -1이 먼저인데 j는 0이라 -1-j를 해준다. if s[j] !.. 2021. 12. 28.
[파이썬 알고리즘 문제풀이] : 점수계산 문제 문제 수가 주어지고, 문제를 맞추면 처음엔 1 그 다음은 2 그 다음은 3..이렇게 1씩 증가하며 점수가 누적된다. 중간에 문제가 틀리면 다시 1점이 쌓이게 된다. 주의 풀이 n = int(input()) a = list(map(int, input().split())) # 점수를 합해야 한다. sum = 0 # 가중치 cnt = 0 # 리스트 a에서 첫 번째 인덱스 값부터 끝까지 하나씩 뺴준다. for x in a: # x가 1이랑 같다면 == 점수가 1점일 때 if x == 1: # 연속으로 정답을 맞추면 1씩 증가된 값을 더해야 하기 때문에 cnt에 가중치를 준다. cnt += 1 # 가중치 값을 sum(합계)에 담아준다. sum += cnt # x가 1이 아닐 때 == 정답이 아닐 때 else.. 2021. 12. 28.
[파이썬 알고리즘 문제풀이] : 주사위 게임 문제 1~6까지 있는 주사위 3개를 던져서 규칙에 맞게 상금을 받고, 가장 큰 수를 출력하는 프로그램을 작성하시오. // 저작권 관련 때문에 문제를 간략하게 설명해야 하기 때문에 완전한 문제를 적을 수 없습니다. 주의 풀이 import sys n = int(input()) res = 0 for i in range(n): tmp = input().split() # tmp를 오름차순 정렬해 준다. tmp.sort() # tmp가 지금 문자열로 받아졌기 떄문에 int 형으로 변환해서 받아준다. a, b, c = map(int, tmp) if a == b and b == c: # a, b, c 모두 같은 값이라 아무 값이랑 1000이랑 곱해준다. money = 10000 + (a * 1000) elif a ==.. 2021. 12. 23.
[파이썬 알고리즘 문제풀이] : 뒤집은 소수 문제 숫자를 뒤집고 뒤집은 숫자가 소수이면 출력하시오. 주의 풀이 import sys def reverse(x): # 초기화 하나 한다. res=0 # while 문으로 x가 0보다 클 때 항상 반복문을 돌려준다. while x>0: # x의 1의 자리 숫자가 t가 된다. t=x%10 res=res*10+t # x는 10으로 나눈 몫으로 바꿔진다. x=x//10 # res를 리턴한다. return res def isPrime(x): # x의 값이 1일 수 있다. if x==1: # False 시켜줘야 한다. return False # 소수를 구하려면 값의 반 정도까지만 구하면 된다. # 그 뒤쪽은 어차피 다 걸러진다. # 2로 나눈 몫의 +1을 해줘 절반까지 돌게 한다. for i in range(2, .. 2021. 12. 22.
[파이썬 알고리즘 문제풀이] : 소수 구하기 (에라토스테네스의 체) 문제 소수의 개수를 출력하는 프로그램을 작성하시오. 주의 풀이 import sys n=int(input()) ch=[0]*(n+1) cnt=0 for i in range(2, n+1): if ch[i]==0: cnt+=1 for j in range(i, n+1, i): ch[j]=1 print(cnt) 2021. 12. 21.
[파이썬 알고리즘 문제풀이] : 자릿수의 합 문제 N개 자연수를 입력 받고 각 자릿수를 더해서 제일 큰 값의 자연수를 출력하시오 주의 풀이 import sys n = int(input()) a = list(map(int, input().split())) def digit_sum(x): sum=0 # str() 함수는 받은 값을 다 쪼개서 문자열로 받는다. 123을 넣으면 1 2 3을 따로 따로 값을 문자열로 가져오는 것이다. for i in str(x): sum+=int(i) return sum max = -2147000000 # for x in a: 형식으로 작성하면 a리스트에 일일이 접근해 값을 가져온다. 리스트에 1 12 123이 있다면 그대로 1 12 123 따로따로 값을 가져오는 것이다. for x in a: tot=digit_sum(x).. 2021. 12. 20.
[파이썬 알고리즘 문제풀이] : 정다면체 문제 두 값을 더해서 나오는 합 중 가장 많이 나오는 합의 숫자를 출력하시오. 주의 풀이 # 정다면체 import sys n, m = map(int, input().split()) # n과 m의 합의 값을 담아둘 리스트를 만들고 크기를 n과 m을 더하고 좀 여유있게 3만큼 추가한 크기를 주었습니다. cnt = [0]*(n+m+3) # 정수 자료형 최소값을 넣어줍니다. max=-2147000000 for i in range(1, n+1): for j in range(1, m+1): # cnt에 n과m의 합을 인덱스 넘버로 설정하고 값은 합이 같을 때 1씩 증가시켜 줍니다. cnt[i+j] += 1 # 최대 값을 찾기 위해 max에 누적시켜줍니다. for i in range(n+m+1): if cnt[i]>.. 2021. 12. 16.
[파이썬 알고리즘 문제풀이] : K번째 수 문제 n개 숫자로 이루어진 숫자열이 주어지면 s번째부터 e번째까지의 순을 오름 차순으로 정렬했을 때 k번째로 나타나는 숫자를 출력하시오. 주의 출력문에 있는 #%d는 출력 예제에 #이 있기 때문에 #자체를 출력하기 위해 넣은 것 입니다. 풀이 T = int(input()) for i in range(T): n, s, e, k = map(int, input().split()) #값을 입력 받아서 split기준으로 나누고 int로 바꿔준다. #int형으로 바뀐 입력 받은 값들은 a라는 list안에 담기게 된다. a=list(map(int, input().split())) #s~e까지 받는데 0번째 인덱스부터 순서대로 배정받기 위해 [s-1:e]를 해줍니다. #마지막 e는 자신을 포함하지 않으므로 추가 연산자.. 2021. 12. 10.
[파이썬 알고리즘 문제풀이] : 대표값 문제 n명의 학생 수학 점수가 주어지고, 학생들의 평균을 구하고 평균에 가장 가까운 학생은 몇 번째 학생인지 출력하시오. 단, 평균과 가장 가까운 점수가 여러개 일 경우 점수가 높은 학생의 번호를 출력하고, 높은 점수를 가진 학생이 여러명일 경우 학생 번호가 가장 빠른 번호를 출력하시오. 주의 평균을 구하기 위해 합계를 구하는 함수 | sum() 소수 점 첫째 자리까지 구하는 함수 | round() 절대 값을 구하는 함수 | abs() 리스트의 인덱스 값과 실제 값을 쌍으로 대입해 주는 함수 | enumberate() ++추가사항 round() 함수가 소수 점 첫째 자리까지 구하는 함수라고 적었는데 파이썬에서는 round_half_up 방식이 아닌 round_half_even 방식을 택하고 있기 때문에 .. 2021. 12. 10.
[파이썬 알고리즘 문제풀이] : k번째 큰 수 문제 1부터 100사이 자연수가 적힌 n카드 중 3장을 뽑아 각 카드에 적힌 수를 합한 값을 기록한다. 기록한 값 중 K번째로 큰 수를 출력하는 프로그램을 작성하시오. 1 1 1 2 2 3 4 5 중 2번째 큰 수는 2 입니다. ( 중복은 제거 ) 주의 set()은 중복을 제거할 때 사용합니다. set()은 sort가 없기 때문에 정렬을 하려면 list에 담아 정렬을 해야 합니다. set() 값을 list에 담아 sort로 정렬을 해주면 오름차순이 디폴트 값이고 reverse=Ture를 통해 내림차순 정렬을 할 수 있습니다. 풀이 n, k=map(int, input().split()) a=list(map(int, input().split())) #set은 중복 제거에 사용합니다. res=set() #첫 .. 2021. 12. 8.
[파이썬 알고리즘 문제풀이] : 최소 값 구하기 문제 arr =[5, 3, 7, 9, 2, 5, 2, 6]의 최소 값을 구하시오 주의 그냥 최소 값을 구하면 < 부호를 사용하면 되지만 가장 최신의 최소 값을 구해야 한다면 2021. 12. 8.
[파이썬 알고리즘 문제풀이] : K번째 약수 문제 N과 K라는 자연수가 주어졌을 때 N의 약수 중 K번째로 작은 수를 출력하시오. K번째 약수가 존재하지 않다면 -1을 출력하시오. 풀이 n, k=map(int, input().split()) cnt=0 for i in range(1, n+1): if n%i==0: cnt+=1 if cnt==k: print(i) break else: print(-1) 두 개의 숫자를 읽기 위해 map 함수에서 split을 통해 띄어쓰기를 기준으로 구분하여 두 값을 받고 그 값을 int화 시키라는 뜻 입니다. 6과 3을 넣는다면 6이 n에 3이 k에 들어가게 됩니다. 약수이면 cnt를 1 증가시킵니다. 그러다 k번째 약수가 발견되면 멈춥니다. 만약 찾지 못 했다면 -1을 해 줍니다. for , else문이 있는데 브레.. 2021. 12. 5.
반응형

티스토리툴바