본문 바로가기

inistory

Visits

Today

Yesterday

Recent Posts

Popular Posts

Recent Comments

Algorithm

Algorithm/백준 [백준] #2529 부등호 (Python) 부등호 문제 입력 : 부등호 문자의 개수를 나타내는 정수 k( 2 ≤ k ≤ 9)와 k개의 부등호 기호 출력 : 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수 부등호의 갯수와 부등호가 주어졌을 때, 그 부등호에 맞게 양 옆으로 들어갈 수 있는 숫자(0~9)가 존재한다.(단, 모든 숫자는 달라야 한다.) 주어진 모든 부등호를 만족하는 숫자들을 찾고, 부등호를 제거하면 정수하나가 나오는데, 그들 중 최대값과 최솟값을 반환해야한다. 입력 2 출력 897 021 용어 정리 - 백트래킹 모든 가능한 경우의 수 중에서 특정한 조건을 만족하는 경우만 살펴보는 것 답이 될 만한지 판단하고 그렇지 않으면 탐색을 중단 주로 문제 풀이에서는 DFS 등으로 모든 경우의 수를 탐색하는 과정에서, 조건문으..

Algorithm/백준 [백준] #14501 퇴사 (Python) 퇴사 문제 퇴사를 진행행하려 하는는데 N+1일 째 되는날 퇴사를 하기 위해서 N일 동안 많은 상담을 하려고 한다. 상담을 완료하는데 걸리는 시간 T와 상담을 했을 때 받을 수 있는 금액 P를 보고, 퇴사 전까지 최대 수익을 구하는 문제이다. 예제 1일 2일 3일 4일 5일 6일 7일 Ti 3 5 1 1 2 4 2 Pi 10 20 10 20 15 40 200 입력 7 3 10 5 20 1 10 1 20 2 15 4 40 2 200 출력 45 문제 풀이 전략 day 0 1 2 3 4 5 6 Ti 3 5 1 1 2 3 2 Pi 10 20 10 20 15 40 200 day는 0~n-1, 퇴사일 n dp 방식으로 푼다 dp[day] = max(dp[day+1],dp[day+T[day]]+P[day]) day에서..

Algorithm/프로그래머스 [프로그래머스] 메뉴리뉴얼 - Python [문제링크] (https://programmers.co.kr/learn/courses/30/lessons/72411) 1. 문제 설명 입력 orders : 각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 course : "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열 출력 "스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return 사전순으로 오름차순 정렬 규칙 (1) 가장 많이 주문한 단품 메뉴들을 코스요리 메뉴로 구성 ex1 ) AC가 네번, CD는 세번 일 때 → AC를 두개까지 요리2개코스로 채택 ex2) BCFG가 두번, ACDE가 두 번 주문됨 → 둘 다 요리4개코스로 채택 (2) 코스요리는 최소 2가지 이상의 단품 메..

Algorithm/알고리즘 [Algorithm] 클루스칼 알고리즘 (Kruskal Algorithm) 1. 신장트리란? 그래프에서 1) 모든 노드를 포함하면서 2) 사이클이 존재하지 않는 부분 그래프를 의미 이는 트리의 조건이기도 함 2 . 최소신장트리 최소의 비용으로 구성되는 신장 트리를 찾아야 할 때 N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결 될 수 있게 도로를 설치하는 경우 3. 크루스칼 알고리즘 가장 대표적인 최소 신장 트리 알고리즘 그리디 알고리즘으로 분류 동작 과정 간선 데이터를 비용에 따라 오름차순으로 정렬 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인 사이클이 발생하지 않는 경우 → 최소 신장 트리에 포함 사이클이 발생하는 경우 → 최소 신장 트리에 포함 X 모든 간선에 대하여 2번의 과정을 반복 결론 최소 신장 트리에 포함되어 있..

Algorithm/프로그래머스 [프로그래머스] 포켓몬 - Python 1. 문제 설명 입력 nums : 포켓몬 종류를 담은 배열 출력 주어진 배열의 길이의 절반만큼 수를 선택할 수 있고, 최대한 다양한 종류의 수를 선택해야할 때 선택할 수 있는 최대값을 return nums result [3,1,2,3] 2 [3,3,3,2,2,4] 3 [3,3,3,2,2,2] 2 2. 코드 def solution(nums): answer = 0 max_num = len(nums)/2 temp = [] #지금까지 나온 포켓몬 저장 for i in range(len(nums)): if nums[i] not in temp: temp.append(nums[i]) if len(temp) == max_num: break return len(temp) 3. 어려웠거나 배운 점 not in 활용 not..

Algorithm/알고리즘 [Algorithm] 그리디 알고리즘 1. 정의 현재 상황에서 지금 당장 좋은 것만 고르는 방법 일반적인 상황에서는 최적의 해를 보장할 수 없을 때가 많지만, 코딩테스트에서는 대부분 그리디로 풀었을 때 최적의 해가 됨 2. 대표적인 그리디 문제 거스름돈 문제 당신은 음식점의 계산을 도와주는 점원입니ㅏㄷ. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정합니다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수입니다. 500원, 100원, 50원 10원짜리 동전에서 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유?만약, 800원을 거슬러주어야하는데, 500원, 400원, 100원..

Algorithm/백준 [백준] #1764 듣보잡 (Python) 듣보잡 듣도 못한 사람과 보도 못한 사람의 수와 명단이 각각 주어질 때, 듣도 보도 못한 사람의 수와 명단을 출력하는 문제 예제 입력 3 4 ohhenrie charlie baesangwook obama baesangwook ohhenrie clinton 출력 2 baesangwook ohhenrie 예시 듣도 못한 사람은 3명 ohhenrie, charlie, baesangwook 보도 못한 사람은 4명 obama, baesangwook, ohhenrie, clinton 이러한 경우, 듣도 보도 못한 사람은 baesangwook, ohhenrie 으로 2명이 나온다. 문제 풀이 전략 listen_list, see_list 에 input값을 넣고 name = set(listen_list) & set(se..

[백준] #15970 화살표 그리기 (Python)

Algorithm/백준 [백준] #15970 화살표 그리기 (Python) KOI 문제 이해 직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른쪽 방향으로 놓여 있다. 이러한 위치들 중 N개의 위치에 하나씩 점들이 주어진다(). 주어진 점들의 위치는 모두 다르다. 두 점 사이의 거리는 두 점의 위치를 나타내는 수들의 차이이다. 에서는 4개의 점이 주어지고 점 a와 b의 거리는 3이다. 각 점은 N개의 색깔 중 하나를 가진다. 편의상, 색깔은 1부터 N까지의 수로 표시한다. 각 점 p에 대해서, p에서 시작하는 직선 화살표를 이용해서 다른 점 q에 연결하려고 한다. 여기서, 점 q는 p와 같은 색깔의 점들 중 p와 거리가 가장 가까운 점이어야 한다. 만약 가장 가까운 점이 두 개 이상이면 아무거나 하나를 선택한다. 모든 점에 대해서..

이전 1 ··· 3 4 5 6 7 8 다음

티스토리툴바