백준 - 구간 합 구하기4
문제 출처:https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 지문을 읽어 보면 간단히 주어진 구간에 덧셈을 진행하면 될 것처럼 보인다. 하지만 N, M, i, j의 범위를 보면 최대 100,000까지 주어질 수 있으므로 시간 초과의 조짐(?)이 보인다. 일단 혹시 몰라서 단순히 주어진 구간동안 계속 합치는 연산으로 수행해본 결과.. 예상했던 데로 시간 초과 문제가 발생했다. 결국 i,j의 구간 합을 구한다는 것은 j까..
문제 출처: https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 필자는 Dynamic Programming 즉, 동적 프로그래밍에 대한 유형에 약하다고 생각이 들어서 문제풀이를 해보았다. 해당 문제와 비슷한 유형을 여러 코테에서 확인할 수 있었고, 입력의 범위 때문에 거의 무조건 DP를 사용하지 않으면 테케를 통과하기 힘들다는 것을 알기 때문에 DP유형 학습을 위해 문제풀이를 해보았다. 우선 이문제는 Bottom-Up방식으로 접근했다. 배열의 인덱스가 1,2,3에 각각 0,1,1(걸리는 연산 횟수)이란 값을 넣어주었다. 이 값들의 의미는, 입력으로 1,2,3 이..
문제 출처:https://programmers.co.kr/learn/courses/30/lessons/77486 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr 지문처럼 단방향 그래프로 설정하여 풀면 간단히 해결할 수 있는 문제다. 초기 설정은 enroll의 부모는 referral로 하여 ArrayList배열을 설정해주면 된다. 보기에는 문자열로 되어있으므로 필자는 enroll에 이름들을 순서대로 hashmap으로 해서 0부터 순차적으로 값을 주었다. 즉, John은 1, mary는 2... 이런식으로 ..
문제 출처: https://programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 문제의 핵심은 i번 선수의 순위를 확실히 알 수 있는 방법은, i번 선수의 경기 결과가 n-1개 있으면 확실히 그 순위를 알 수 있다. 물론 그렇지 않더라도 n-1개의 결과를 가지고 있는 선수와 연결된 또 다른 선수의 결과 또한 알 수 있다. 필자는 이 문제를 2가지 방식으로 해결했다. 첫 번째는 특정 선수가 이긴 횟수+진 횟수 = n-1개 이면 순위를 구할 수 있다. 예제 테케를 보면, n results return 5 [[4, 3], [4, 2], [3..