알고리즘 문제풀이

마치 잔돈 문제와 매우 유사한 구조의 문제였습니다. 3과 5를 최소한으로 사용하여 N을 만들어야했고 만들 수 없을 때는 -1을 리턴해야했습니다. 분기를 최대한 나누는 방식으로 문제를 해결했습니다. 일단 가장 큰 수인 5로 나누었고(-> 이 몫을 fiveShare라고 했

이 문제는 정말 간단한 문제였습니다. 그냥 오름차순으로 정렬을 하고 각 시간들을 중복되는 숫자만큰 차례로 더해서 해결하였습니다.

이 문제도 거스름돈 거슬러주기와 매우 유사한 문제였습니다. 오히려 조금 더 쉬운 느낌이었습니다. 애초에 입력 자체가 오름차순으로 주어져서 더욱 쉽게 느낀 것 같습니다. 입력 받을 때 만들어야할 값보다 작은 동전 값을 확인후 그 동전 값으로 주어진 값을 나누고 그 결과를

이 문제는 정말 유명한 거스름돈 동전 갯수 문제입니다. 물론 알고리즘을 많이 풀어보지는 않았지만 거스름돈 유형은 정말 많이 들어봤던 것 같습니다. 문제 자체는 어렵지 않았습니다. 기본 주어진 금액 1000에서 입력으로 받은 값을 뺀 뒤 그 값을 동전들과 내림차순으로 비

이 문제는 처음 읽었을 때는 너무 어려웠습니다. 하지만 천천히 문제를 풀다보니 해결책이 보였습니다. 일단 n개의 루프가 주어지니까 w = n\*(로프가 견딜수있는 가장 적은무게) 로 놓고 n을 하나씩 빼나가면서 그 중 w의 최댓값을 구했습니다. 사용되는 모든 줄은 w/

처음에 낸 아이디어는 시작 시간, 종료시간을 pair를 사용해서 묶어서 벡터에 저장후 시작 시간으로 오름차순으로 정렬 한뒤 문제에 맞게 요소들을 고르고 갯수를 증가시키는 방식이었습니다. 하지만 시간초과가 났고, 또한 간과한 문제점도 있었습니다. 일단 for를 두번 사용

c++에서는 문자열로 받은 수식을 수식으로써 계산해주는 방법을 쉽게 찾을 수 없었습니다. 그래서 조금 더 어렵게 해결한 것 같습니다. 일단 메인 아이디어는 string으로 받은 수식을 '-'기준으로 나누고 각 나누어 놓은 요소들을 각각 계산해주는 것입니다. 그리고 그

정말 어려웠습니다. 문제에 써있는 최댓값이라는 단어 때문에 더욱 어렵게 생각했던 것 같습니다. 사실 어차피 전체 인원에서 비교해야하기에 각 순위를 비교하는 순서만 잘 고려하면 잘 풀리는 문제였습니다. 일단 두 성적 중 첫번째로 주어지는 것을 first, 두 번째는 se

정말 오랜 시간을 투자하였고, 정말 어렵게 풀었습니다. 이렇게 어렵게 해결해야할 문제였나 싶을 정도로 어렵게 풀었습니다. 삽질을 많이 하다보니 코드가 점점 복잡해져서 그렇게 된 것 같기도 합니다. 처음 아이디어는 vector배열을 이용해서 각 알파벳 문자열을 자릿수에

이 문제는 2가지 방법으로 해결할 수 있다. 첫번째로 순열을 이용해서 해결할 수 있다. 9명 중 7명을 뽑고 sum이 100이면 출력하는 방식이다.두 번째 방법은 발상을 바꿔서 생각할 수 있다. sum이 100인 7명을 뽑는 다는 것은 7명의 sum이 100이 되게 나

이 문제는 처음에는 next_permutation을 중첩해서 사용하여 풀었었지만 시간초과가 발생하였다. 이 문제는 주어지는 N, M의 값이 작기에 재귀함수로 해결할 수 있었다. 1~N을 1부터 하나씩 선택하고 checked로 선택됬는지를 구분해주며 오름차순으로 차례로

이 문제는 15649번과 유사해보이지만 조금 다른 문제였다. 1~N까지 중복없이 M개를 고르고, 고른 수열을 오름차순으로 해줘야한다. 입력, 출력 예시를 보면 더욱 쉽게 차이를 이해할 수 있다. 이 문제는 prev라는 인자를 추가함으로써 중복을 제거하여 쉽게 해결할 수

해당 문제는 1~N까지 자연수중 M개를 고른 수열을 얻어야 합니다. 하지만 조건이 있습니다. 같은 수를 여러번 골라도 되고 출력은 사전 순으로 증가하는 순서로 출력해야 합니다. 이 문제는 기존의 checked를 사용하여 나눴던 조건을 해제해주면 간단하게 해결할 수 있었

시험 기간으로 잠시 알고리즘을 쉬었다. 3학년 정말 너무 바빠서 병행하기 너무 힘들어 학업에 좀 더 집중을 하였다. 그에 맞는 결과가 나올지는 모르겠지만..ㅎㅎ 간만에 알고리즘을 풀었는데 쉽지 않았다.처음에는 단순히 그냥 for문을 이용해서 연산을 해주려하였다. 하지만

문제는 한 시작점으로부터 모든 정점까지의 최단경로를 구하는 문제였다. 그냥 다익스트라 알고리즘을 사용하여 쉽게 해결할 수 있었다. 모든 정점을 최댓값으로 초기화한 뒤 시작점부터 시작하여 거리를 갱신해나가는 알고리즘이다.시작 정점 결정 -> 현재 정점시작 정점 제외 모든

백준 1806번

해당 문제는 처음에 읽었을 때 어찌 풀어야할지 감이 오지 않았다. 그라다가 플로이드와샬 알고리즘을 이용해서 풀 수 있을 것 같았다. 하지만 바로 오답을 맞아버렸다. 생각해보니 시간을 돌릴 수 있어서 음수의 간선이 있다는 것을 간과하였다. 음수의 간선이 있기에 벨만포드를

양수의 산성 용액이 있고 음수의 알칼리 용액이 있을 때, 나열된 용액들 중 두 개를 골라서 0에 가장 가까운 값을 만드는 문제이다. 해당 문제는 이중포인터를 사용하여 해결하면 된다. 나열된 배열에 가장 왼쪽과 오른쪽을 가르킨다. 그리고 두 개의 합이 0보다 작으면 0이

백준 1644번 한 숫자가 주어졌을 때 그 소수를 하나 이상의 연속된 소수의 합으로 나타낼 수 있는지, 나타낼 수 있으면 몇가지 경우의 수가 있는지 출력하는 문제이다.

숫자로 된 수열을 주고 해당 수열을 조합하여 만들 수 있는 가장 큰 수를 구하는 문제였다.처음에는 모든 dfs를 이용하여 문제 풀이를 시도하였다. 모든 값들을 조합해보고 모든 수열을 다 썼으면 그 숫자를 string에서 long long으로 변환 후에 vector에 집

해당 문제는 H-Index를 구하는 문제이다. 논문과 관련된 수치로 그 학술자의 영향력을 판단하는 수치라고한다. 사실 문제가 잘 이해가 안되서 좀 자세히 몇 번을 읽어봤다.문제 자체를 어렵지않았다. 우선 내림차순으로 논문 인용횟수를 정렬하였다. 그리고 첫번째 값을 Ma

우주 탐사선이 주어진 모든 행성을 방문할 경우 걸리는 가장 최단 시간을 구하는 문제입니다. 행성의 갯수와 시작 행성, 그리고 각 행성까지 걸리는 시간이 배열 형식으로 주어집니다.처음에는 문제를 오해하여 플로이드 와샬로 풀려했습니다. 모든 행성을 방문해야하는데 각 행성의

이 문제는 방향성이 없는 그래프가 먼저 주어지고, 해당 그래프에서 1 -> N까지의 최단 경로를 구하는 문제이다. 이 때 조건이 주어지는데 문제에서 주어진 2개의 정점을 반드시 경로에 포함시켜야한다.해당 문제는 쉽게 해결하는 방식은 쉽게 생각해내었지만 중간 계산에서의

이 문제는 N개의 마을에 있는 학생들이 X번 마을로 모여 파티를 하는데 이때 왕복시간이 가장 오래 걸리는 학생을 찾는 문제이다. 도로가 단방향으로 주어지기에 오는 동선과 가는 동선이 다를 수 있다는 것을 염려해야하는 문제다.처음 문제를 읽고 해결 방안을 생각해봤을 때,

해당 문제는 각 기능의 현재 진행 상황을 주어주고, 각 기능의 개발 속도를 주어줍니다. 그리고 배포는 100%일때 반영되고 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포된다. 즉 뒤에 있는 기능이 먼저 완성되어도 그 앞에 있는 모든 기능이 완성되어야 배포할

해당 문제는 학생들이 체육복을 가지고 있었는데 도난당했을 경우 서로 빌려주었을 때 체육복을 가지고 있을 수 있는 학생의 최댓값을 구하는 문제이다. 이때 체육복은 자신의 전, 후 사람과만 교환할 수 있다.단순하게 생각하면 쉽게 풀 수 있는 문제였다. 우선 모두 1개씩 체

해당 문제는 아래의 3가지 조건을 만족하는 프린터에서 요청한 문서가 몇 번째로 인쇄되는지 구하는 문제이다.인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼낸다.나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지