알고리즘

문제 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 정답 소스코드 (Python) n=int(input()) arr=[] for _ in range(n):arr.append(int(input())) dp=[1]*(n+1) lenth=0 for i in range(n): for j in range(i): if arr[i]>arr[j]: if dp[i]

완전탐색 ( Complete Search) 이란? 완전탐색을 알기 전에 상위 개념인 탐색에 대해 알아야 하는 탐색(Search) 알고리즘은 많은 데이터 중 목적에 맞는 데이터를 찾기 위한 방법이다. 탐색 알고리즘에는 여러 가지 탐색 방법이 존재하는데 완전 탐색은 그중 대표적인 알고리즘 중 하나이다. 완전탐색(Complete Search) 은 말그대로 "모든 경우의 수를 검사" 하는 방식으로 브루트포스( Bruth-Force) 알고리즘으로 불리기도 한다. "brute"는 "무식한", "force"는 "힘"을 의미하는데 무식한 힘 즉 무식하게 전체 모든 경우의 수를 검사하는 알고리즘을 의미한다. 완전탐색(Complete Search)은 전체 모든 경우의 수를 검사하기 때문에 매우 큰 메모리를 사용하며, 시간..

문제 1522번: 문자열 교환 a와 b로만 이루어진 문자열이 주어질 때, a를 모두 연속으로 만들기 위해서 필요한 교환의 회수를 최소로 하는 프로그램을 작성하시오. 이 문자열은 원형이기 때문에, 처음과 끝은 서로 인접해 www.acmicpc.net 정답 소스코드 (Python) arr=input() result=[] size=arr.count('a') #윈도우 크기 for i in range(len(arr)): b_count=0 for j in range(size): index=i+j if index>len(arr)-1:index-=len(arr) #index가 리스트를 넘어간다면 -=리스트크기 해주기-> 원형 유지 if arr[index]=="b":b_count+=1 result.append(b_cou..

문제 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 풀이 (Python) N=int(input()) share=N//5 min_number=N kg5_count,kg3_count=0,0 for i in range(share,-1,-1): if (N-5*i)%3==0: kg5_count=i kg3_count=(N-5*i)//3 if min_number>kg5_count+kg3_count and(kg5_count>0 or kg3_count>0): min_number=kg5_count+kg3_count if kg5_coun..

문제 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 풀이 (Python) n=int(input()) count=0 while n>=0: if n%5==0: #5로 나눠진다면 전부 다 나누기 print(n//5+count) break n-=2 #-2반복 count+=1 #2원을 거슬러 준 횟수를 count에 저장 if n

문제 20365번: 블로그2 neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한 www.acmicpc.net 풀이 (Python) n=int(input()) arr=list(input()) def check(): #전체 원소가 같은 색깔인지 점검하는 함수 for i in range(1,len(arr)): if arr[i-1]!=arr[i]: return False return True def paint_count(): arr_B,arr_R,result=0,0,0 if len(arr)==1 or check(): #예외처리 arr가 1개만 입력되거나 전체 원소가 같은..

문제 20115번: 에너지 드링크 페인은 에너지 드링크를 좋아하는 회사원이다. 에너지 드링크는 카페인, 아르기닌, 타우린, 나이아신 등의 성분이 들어있어 피로 회복에 도움을 주는 에너지 보충 음료수이다. 야근을 마치고 한 www.acmicpc.net 풀이 (Python) #많은 양을 남기고 적은양을 /2값하여 많은 에너지 드링크에 합치면 되는 문제 n=int(input()) arr=list(map(int,input().split())) max_drink=max(arr) arr.remove(max_drink) #제일 큰 값 제외 전부 /2하여 큰값에 더하면 되기 때문에 for ele in arr: #for문을 통해 제일 큰 값에 계속 더해주기 max_drink+=ele/2 print(max_drink) 설..

문제 1343번: 폴리오미노 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. www.acmicpc.net 풀이 (Python) arr=list(input()) def poli(): count=0 for i in range(len(arr)): #x의 개수가 4개 연속으로 있다면 A로 대체하기 위한 for문 if arr[i]=="X": count+=1 else: count=0 if count==4: for j in range(4): arr[i-j]="A" count=0 count=0 for i in range(len(arr)): #x의 개수가 3개가 남아있는 case가 있다면 false리턴을 위한 for문 if arr[i]=="X": count+=1 else: cou..