주발이의 개발새발

백준을 풀다보면 알고리즘 분류에 '그리디 알고리즘'이 자주 보인다. 그리디 알고리즘은 가장 기초가 되는 알고리즘이자 복잡한 문제를 단순하고 강력하게 해결해줄 수 있는 알고리즘이다. 1. 그리디 알고리즘이란 ? 그리디 알고리즘은 단순하지만 빠르고 강력하다 ! Greedy는 탐욕적이라는 뜻이다. 즉, 그리디 알고리즘은 탐욕적으로 문제를 푸는 알고리즘이라는 뜻으로 탐욕법이라고도 한다 ! ** 탐욕적 -> 문제를 풀 때 현재 상황에서 가장 좋은 것을 고르는 방법 = 현재 상황에서 '최적'이라고 생각하는 해를 선택하는 방법 말 그대로 현재 상황만 고려하고 앞으로 남은 선택들은 고려하지 않기 때문에 항상 최적해(Global optimum)을 보장하진 않는다. 2. 그리디 알고리즘의 정당성 대부분의 문제는 그리디 알..

1. 문제 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 글만 읽어봤을 땐 이게 뭔말인고 .. 싶었다. 그래서 예제를 적어보고 스스로 답을 찾아보는 과정에서 알고리즘에 대해서 떠올랐다. 브론즈에서는 그냥 무작정 코드를 짜면 풀리는 문제가 많았는데 실버단계 문제부터는 이해가 중요한 문제가 많이 나오는 것 같다. 스스로 예제에 대한 답을 내려보는 과정을 습관들여야겠다. 2. 해결 해결방법을 떠올리는 것은 어렵지 않다. X1, X2, ... 을 배열로 두고 ** 중..

1.문제 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 2. 해결 - 고민이 많이 되었던 문제이다. 버블 정렬을 통해 하나씩 정렬해볼까도 생각해봤는데 .. - 계속 안되다가 힌트를 보고 BruteForce를 이용해보아야겠다 .. ~ 고 생각했다. ** BruteForce Algorithm -비교대상 문자열을 처음부터 끝까지 모두 순회하면서 비교하는 알고리즘 그렇다 .. n개의 덩치들(?)을 나머지 n-1개와 비교해서 본인보다 큰 덩치의 수를 알면 끝나는 문제.. ! 3. 코드 n = int(in..

1. 문제 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 2. 해결 - 소수의 조건을 생각해보았다. 소수는 약수가 2개인 수이다. 소수의 약수는 1과 자기자신인 수인데.. - 주어진 수(num)이 소수임을 확인하기 위해서는 num을 2부터 num-1까지 하나하나 나누어보면서 나머지가 0이 아님을 보이면 되겠다! - for문 if문을 적절히 사용하고 - cnt를 통해 탐색하고 있는 수(num)이 소수일 때 +1씩 해주면 되겠다 ! 3. 코드 n = int(input()) nums = list(map(int,input().split())) def isPrime(num): if n..

1. 문제 8979번: 올림픽 입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 www.acmicpc.net 2. 해결 - 우선 얻은 금메달, 은메달, 동메달 수의 순서대로 리스트를 정렬한다. - sort, lambda함수를 이용하여 정렬하였다. - 등수를 찾을 때 for 문을 돌며 n과 함께 주어진 국가번호 k의 index(정렬한 리스트의 등수 -1) 를 찾는다. - 등수가 중복되는 국가의 공동 등수를 지정하기 위해 for문을 돌며 k국가의 모든 메달 수 가 같은 국가가 나오면 그 국가의 (index+1)등이므로 출력해준다. 3. 코드..

1. 문제 14593번: 2017 아주대학교 프로그래밍 경시대회 (Large) 아주대학교 프로그래밍 경시대회(Ajou Programming Contest, APC)는 2009년 제1회를 시작으로 2014년 제6회까지 개최된 아주대학교 학생들을 위한 프로그래밍 경시대회이다. 2017년, 다른 학교에서 활발히 www.acmicpc.net 2. 해결방법 3개의 정수를 입력받고 각각 내림차순, 오름차순, 오름차순으로 정렬하여 풀어야한다. 만약 람다함수를 몰랐다면 중복 체크때문에 코드가 조금 더 길어졌을 것 같다. 3.코드 n = int(input()) playes = [] for i in range(n): play = list(map(int,input().split())) playes.append(play) p..

1. 문제 15905번: 스텔라(STELLA)가 치킨을 선물했어요 경인지역 6개대학 연합 프로그래밍 경시대회 shake! 는 아주대학교, 경희대학교, 성균관대학교, 인하대학교, 한국항공대학교, 한양대학교ERICA가 함께하는 대학교 자체 연합 대회이다. shake! 는 매 www.acmicpc.net 2. 문제해결 정렬문제이다. 문제는 정렬해야할 대상이 2개라는 것 이때 문제해결을 쉽게 할 수 있는 함수가 바로 람다함수이다. 람다함수에 대해서는 아래 자세하게 설명하겠다 생각해본 알고리즘 - 입력받은 참가자들의 해결한 문제 수와 패널티 총 합을 입력받고 playes(이중 리스트)에 넣기 - playes를 해결한 문제 수 내림차순, 패널티 총 합 오름차순으로 정렬하기 - playes에서 5등의 해결한 문제 수..

1. 문제 5533번: 유니크 첫째 줄에 참가자의 수 N이 주어진다. (2 ≤ N ≤ 200) 둘째 줄부터 N개 줄에는 각 플레이어가 1번째, 2번째, 3번째 게임에서 쓴 수가 공백으로 구분되어 주어진다. www.acmicpc.net 2. 풀이 - 입력받는 세 숫자에 대해 세로로 비교하여 중복된 숫자가 있다면 더할 수 없다 . 3. 코드 n = int(input()) games = [] for _ in range(n): game = list(map(int,input().split())) games.append(game) for i in range(n): ans = 0 for j in range(3): cur = games[i][j] check = 1 for k in range(n): if k == i: ..

1. 문제 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 2. 해결방안 - 입력 받은 단어의 중복 제거 - 입력 받은 단어 알파벳 순으로 정렬 - 입력 받은 단어 길이순으로 오름차순 sort()를 알면 어렵지 않은 문제였다 ! 3. 코드 n =int(input()) words = [] for i in range(n): words.append(input()) words.sort() #알파벳 순 정렬 words.sort(key = len) # 길이 순 정렬 ans = [] #중복제거 for word ..

1.문제 https://www.acmicpc.net/problem/10798 10798번: 세로읽기 총 다섯줄의 입력이 주어진다. 각 줄에는 최소 1개, 최대 15개의 글자들이 빈칸 없이 연속으로 주어진다. 주어지는 글자는 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’ www.acmicpc.net 2. 풀이 해결과제 : 5줄의 단어를 세로로 읽어내야한다. 이 과정을 위해서는 단어를 반복하며 첫번째 열부터 마지막열까지 읽어내야하는데 .. 단어의 길이만큼 5번씩 반복을해야한다. 그런데 이때 문제가 발생했다. 길이가 다른 5개의 단어를 받아오기 때문에 오류가 생긴다는 점 ! 그 문제를 방지하기 위해 if문을 사용한다. 3. 코드 lines= [] length = [] # 입력받는..