본문 바로가기

알고리즘11

[알고리즘] 위상 정렬(Topological Sort) - 개발하는 지토 위상 정렬(Topological Sort) 위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. 즉, 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것 이다. 위상 정렬을 가장 잘 설명할 수 있는 예시는 대학의 선수과목 구조 또는 게임에서의 스킬트리 중 선행스킬이 존재하는 경우이다. 앞선 대표 예 두가지 중 각자 더 이해가 쉬운 예시를 떠올려 보면 쉽게 이해할 수 있을 것이다. 위상 정렬이 성립하기 위해서는 반드시 그래프에 순환이 존재하지 않아야 한다. 즉, 비순환 방향 그래프(Directed Acyclic Graph, DAG) 여야 한다. 그리고 하나의 방향 그래프에 대해서 위상 정렬을 수행한 결과 값이.. 2021. 3. 18.
[알고리즘] 백준 2003번: 수들의 합 2 (자바/Java) - 슬라이딩 윈도우, 구간합 스터디 중에 풀었던 알고리즘 문제 백준 2003번: 수들의 합 2 문제를 가져와봤다. 사실 이 문제는 투 포인터 기법을 활용해서 문제를 푸는 것 같았다. 하지만 오늘 스터디에서 투 포인터를 들어가기 전에 슬라이딩 윈도 기법을 먼저 진행했기 때문에 이번 문제는 슬라이딩 윈도 기법으로 풀어보았다. 문제는 다음과 같다. 수들의 합 2 성공분류 시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율 0.5 초 128 MB 17563 8645 5801 50.752% 문제 N개의 수로 된 수열 A [1], A [2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에.. 2020. 10. 29.
[알고리즘] 백준 2839번: 설탕 배달 풀이 (자바/Java) DP,동적계획법, Dynamic Programming 기본 www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그�� www.acmicpc.net 설탕 배달 1 초 128 MB 130830 39344 31733 31.834% 문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로.. 2020. 9. 26.
[알고리즘] 프로그래머스 무지의 먹방 라이브(Level 4/2019 카카오 블라인드 채용 문제) [자바/JAVA] 풀이- 개발하는 지토 무지의 먹방 라이브 * 효율성 테스트에 부분 점수가 있는 문제입니다. 평소 식욕이 왕성한 무지는 자신의 재능을 뽐내고 싶어 졌고 고민 끝에 카카오 TV 라이브로 방송을 하기로 마음먹었다. 그냥 먹방을 하면 다른 방송과 차별성이 없기 때문에 무지는 아래와 같이 독특한 방식을 생각해냈다. 회전판에 먹어야 할 N 개의 음식이 있다. 각 음식에는 1부터 N 까지 번호가 붙어있으며, 각 음식을 섭취하는데 일정 시간이 소요된다. 무지는 다음과 같은 방법으로 음식을 섭취한다. 무지는 1번 음식부터 먹기 시작하며, 회전판은 번호가 증가하는 순서대로 음식을 무지 앞으로 가져다 놓는다. 마지막 번호의 음식을 섭취한 후에는 회전판에 의해 다시 1번 음식이 무지 앞으로 온다. 무지는 음식 하나를 1초 동안 섭취한 후 남은 음.. 2020. 9. 7.
[알고리즘] 프로그래머스 모의고사(Level 1) [자바/JAVA] 풀이- 개발하는 지토 문제 설명 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ... 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작.. 2020. 9. 3.
[알고리즘] 프로그래머스 큰 수 만들기(Level 2) [자바/JAVA] 풀이- 개발하는 지토 문제 설명 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요. 제한 조건 number는 1자리 이상, 1,000,000자리 이하인 숫자입니다. k는 1 이상 number의 자릿수 미만인 자연수입니다. 입출력 예 number k return 1924 2 94 1231.. 2020. 9. 2.

티스토리툴바