Cherry & Cherish

그리디 알고리즘은 Greedy, 탐욕 알고리즘으로 불리기도 한다. 일반적으로 코딩테스트에서 문제를 해결 할 때에는 (몇몇의 특이 케이스를 제외하고)암기가 필요없지만, 문제의 폭이 넒다. 1. 개념 💡 현재상황에서 가장 좋은 것만 고르는 방법 (선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달) 이름에서 알 수 있듯이 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 여기서 탐욕적이라는 말은 ‘현재 상황에서 지금 당장 좋은 것만 고르는 방법’을 의미한다. 그리디 알고리즘을 이용하면 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 다시 말해, 최적화 문제를 해결하는 알고리즘으로, 탐욕 알고리즘은 최적..

생활 전반에서 우리는 ‘알고리즘’이라는 단어를 만나게 된다. 유튜브, 넷플릭스와 같은 미디어를 소비하는 과정 뿐만 아니라, 계산 절차나 처리 과정에서도 어떠한 알고리즘으로 내 눈에 보이는 결과값이 나왔는지 궁금해하는 일이 아주 흔하다. 모두가 알고있듯 알고리즘은 개발의 과정에서는 필수적으로 요구되는 능력이고, 기업의 입사 과정에서도 가장 첫 번째 전형으로 만난다. 그렇다면, 과연 알고리즘이란 무엇일까? 알고리즘 정의 알고리즘에 대한 정의는 아래와 같이 3가지로 정리할 수 있다. 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법 컴퓨터 용어로 쓰이며, 컴퓨터가 어떤 일을 수행하기 위한 단계적 방법 어떤 문제를 해결 하기 위한 절차 마치 거창한 것처럼 알고리즘을 생각하는 경향이 있지만 알고리즘이란 결국 ..

문제 : 나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다. 재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다. 재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다. 재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자! 접근 : 0이 입력되었을 때, pop을, 아닌 경우에는 push를 하고 최종적으로 sum 함수를 사용하여 전체 개수를 확인한다. 풀이 : import sys input = sys.stdin.readline T = int(input()) arr = [] for tc in range(1, T+1): data =..

문제 : 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다. 여러분은 입력으로 주어진 괄호 문..

문제 : 스페이스로 띄어쓰기 된 단어들의 리스트가 주어질때, 단어들을 반대 순서로 뒤집어라. 각 라인은 w개의 영단어로 이루어져 있으며, 총 L개의 알파벳을 가진다. 각 행은 알파벳과 스페이스로만 이루어져 있다. 단어 사이에는 하나의 스페이스만 들어간다. 접근 : 스택을 연습하기 위해서 push와 pop을 활용해서 접근한다. 풀이 : import sys input = sys.stdin.readline T = int(input()) for tc in range(1, T+1): arr = list(input().split()) arr_b = ' '.join(arr[::-1]) print(f'Case #{tc}: {arr_b}')

문제 : 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯 가지이다. push X: 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 스택에 들어있는 정수의 개수를 출력한다. empty: 스택이 비어있으면 1, 아니면 0을 출력한다. top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. 접근 : 문제 그대로 각 설명별 조건으로 구분하여 풀이 풀이 : import sys input = sys.stdin.readline n = int(input()) stack=[] fo..

문제 : 아래 그림처럼 높이만 다르고 (같은 높이의 막대기가 있을 수 있음) 모양이 같은 막대기를 일렬로 세운 후, 왼쪽부터 차례로 번호를 붙인다. 각 막대기의 높이는 그림에서 보인 것처럼 순서대로 6, 9, 7, 6, 4, 6 이다. 일렬로 세워진 막대기를 오른쪽에서 보면 보이는 막대기가 있고 보이지 않는 막대기가 있다. 즉, 지금 보이는 막대기보다 뒤에 있고 높이가 높은 것이 보이게 된다. 예를 들어, 그림과 같은 경우엔 3개(6번, 3번, 2번)의 막대기가 보인다. N개의 막대기에 대한 높이 정보가 주어질 때, 오른쪽에서 보아서 몇 개가 보이는지를 알아내는 프로그램을 작성하려고 한다. 접근 : list를 통해 데이터를 입력받고, Max값이 갱신되는 횟수를 카운트 한다. 풀이 : import sys ..