그리디 알고리즈 (탐욕법), 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미 이러한 트리가 있다고 할 때 Root에서 시작하는 경로중 아스키코드의 총합이 더 작은 경우의 경로를 고르라고 할 때 그리드의 경우 현재 상황에서 지금 가장 작은 아스키코드를 가지고 있는 B를 선택하게 되고 그 이후에는 D, H 순으로 경로를 고르게 됩니다. 이처럼 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 그리디 알고리즘 또는 탐욕 법이라고 말합니다. 그리디 알고리즘으로 분류되는 코테의 경우 그리디 알고리즘을 써도 최적의 해가 나오는 경우들만 출제합니다. 예시 문제 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지..
위장 # 위장 # 링크 : https://programmers.co.kr/learn/courses/30/lessons/42578 # 문제 설명 # 스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다. # 예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 # 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다. # 종류 이름 # 얼굴 동그란 안경, 검정 선글라스 # 상의 파란색 티셔츠 # 하의 청바지 # 겉옷 긴 코트 # 스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요. # 제한사항 # clothes의 ..
전화번호 목록 # 전화번호 목록 # 링크 : https://programmers.co.kr/learn/courses/30/lessons/42577 # 문제 설명 # 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. # 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. # 구조대 : 119 # 박준영 : 97 674 223 # 지영석 : 11 9552 4421 # 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 # 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요. # 제한 사항..
완주하지 못한 선수 # 완주하지 못한 선수 # 링크 : https://programmers.co.kr/learn/courses/30/lessons/42576 # 문제 설명 # 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. # 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, # 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. # 제한사항 # 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. # completion의 길이는 participant의 길이보다 1 작습니다. # 참가자의 이름은 1개 ..
코딩테스트 연습 - 문자열 내 p와 y의 개수 # 문제 설명 # 대문자와 소문자가 섞여있는 문자열 s가 주어집니다. s에 'p'의 개수와 'y'의 개수를 # 비교해 같으면 True, 다르면 False를 return 하는 solution를 완성하세요. 'p', 'y' # 모두 하나도 없는 경우는 항상 True를 리턴합니다. 단, 개수를 비교할 때 대문자와 소문자는 # 구별하지 않습니다. # 예를 들어 s가 "pPoooyY"면 true를 return하고 "Pyy"라면 false를 return합니다. # 제한사항 # 문자열 s의 길이 : 50 이하의 자연수 # 문자열 s는 알파벳으로만 이루어져 있습니다. # 입출력 예 s answer "pPoooyY" true "Pyy" false # 입출력 예 설명 # 입출..
코딩테스트 연습 - 짝수와 홀수 # 문제 설명 # 정수 num이 짝수일 경우 "Even"을 반환하고 홀수인 경우 "Odd"를 반환하는 함수, # solution을 완성해주세요. # 제한 조건 # num은 int 범위의 정수입니다. # 0은 짝수입니다. # 입출력 예 num return 3 "Odd" 4 "Even" 소스 더보기 더보기 def solution(num): return "Odd" if num%2 else "Even"
코딩테스트 연습 - 서울에서 김서방 찾기 # 문제 설명 # String형 배열 seoul의 element중 "Kim"의 위치 x를 찾아, "김서방은 x에 있다"는 # String을 반환하는 함수, solution을 완성하세요. seoul에 "Kim"은 오직 한 번만 # 나타나며 잘못된 값이 입력되는 경우는 없습니다. # 제한 사항 # seoul은 길이 1 이상, 1000 이하인 배열입니다. # seoul의 원소는 길이 1 이상, 20 이하인 문자열입니다. # "Kim"은 반드시 seoul 안에 포함되어 있습니다. # 입출력 예 seoul return ["Jane", "Kim"] "김서방은 1에 있다" 소스 더보기 # 1 def solution1(seoul): return '김서방은 '+str(seoul...
코드업 기초 100제 문제 099 # 성실한 개미 # **서론** # 영일이는 생명과학에 관심이 생겨 왕개미를 연구하고 있었다. # 왕개미를 유심히 살펴보던 중 특별히 성실해 보이는 개미가 있었는데, # 그 개미는 개미굴에서 나와 먹이까지 가장 빠른 길로 이동하는 것이었다. # 개미는 오른쪽으로 움직이다가 벽을 만나면 아래쪽으로 움직여 가장 빠른 길로 움직였다. # (오른쪽에 길이 나타나면 다시 오른쪽으로 움직인다.) # 이에 호기심이 생긴 영일이는 그 개미를 미로 상자에 넣고 살펴보기 시작하였다. # 미로 상자에 넣은 개미는 먹이를 찾았거나, 더 이상 움직일 수 없을 때까지 # 오른쪽 또는 아래쪽으로만 움직였다. # 미로 상자의 구조가 0(갈 수 있는 곳), 1(벽 또는 장애물)로 주어지고, # 먹이가..
코드업 기초 100제 문제 098 # 설탕과자 뽑기 # **서론** # 부모님과 함께 유원지에 놀러간 영일이는 # 설탕과자(설탕을 녹여 물고기 등의 모양을 만든 것) 뽑기를 보게 되었다. # 길이가 다른 몇 개의 막대를 바둑판과 같은 격자판에 놓는데, # 막대에 있는 설탕과자 이름 아래에 있는 번호를 뽑으면 설탕과자를 가져가는 게임이었다. # (잉어, 붕어, 용 등 여러 가지가 적혀있다.) # 대체 텍스트 # 격자판의 세로(h), 가로(w), 막대의 개수(n), 각 막대의 길이(l), # 막대를 놓는 방향(d:가로는 0, 세로는 1)과 # 막대를 놓는 막대의 가장 왼쪽 또는 위쪽의 위치(x, y)가 주어질 때, # 격자판을 채운 막대의 모양을 출력하는 프로그램을 만들어보자. # 입력 # 첫 줄에 격자판의..
코드업 기초 100제 문제 097 # 바둑판에 십자 뒤집기 # 부모님을 기다리던 영일이는 검정/흰 색 바둑알을 바둑판에 꽉 채워 깔아 놓고 놀다가... # "십(+)자 뒤집기를 해볼까?"하고 생각했다. # 바둑판(19 * 19)에 흰 돌(1) 또는 검정 돌(0)이 모두 꽉 채워져 놓여있을 때, n개의 좌표를 입력받아 십(+)자 뒤집기한 결과를 출력하는 프로그램을 작성해보자. # 입력 # 바둑알이 깔려 있는 상황이 19 * 19 크기의 정수값으로 입력된다. # 십자 뒤집기 횟수(n)가 입력된다. # 십자 뒤집기 좌표가 횟수(n) 만큼 입력된다. 단, n은 10이하의 자연수이다. # 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 # 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 ..
