목록알고리즘 (508)
어흥
문제 링크: www.acmicpc.net/problem/1484 1484번: 다이어트 첫째 줄부터 한 줄에 하나씩 가능한 성원이의 현재 몸무게를 오름차순으로 출력한다. 가능한 몸무게가 없을 때는 -1을 출력한다. 현재 몸무게는 자연수로 떨어지지 않을 수도 있는데, 이런 경우 www.acmicpc.net 1. 주의할 점 - a*a - b*b = (a+b)*(a-b)로 접근한다 2. 구현 - G = (a+b)*(a-b)라고 생각하여 G의 약수중에서 작은 값을 V벡터에 넣는다. 즉, a-b의 값을 V에 너흔ㄴ다 - V에 있는 값을 통해 a+b를 구한다. - {(a+b) + (a-b)}/2 = a 식을 통해 a를 구한다. 이때, 좌변은 2로 나누기 전, 짝수여야 한다 - 모든 a 값을 ans벡터에 넣고 정렬한 ..
문제 링크: programmers.co.kr/learn/courses/30/lessons/64061 코딩테스트 연습 - 크레인 인형뽑기 게임 [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]] [1,5,3,5,1,2,1,4] 4 programmers.co.kr 1. 주의할 점 - 크레인으로 뽑는 경우, 뽑은 자리는 0으로 바꾼다 - 바구니의 가장 위에 위치한 인형과 뽑은 인형만 비교한다 2. 구현 - 뽑으려는 위치를 idx로 표시한다(기존의 원소 - 1) - 위에서부터 뽑으므로 0부터 Num-1까지 탐색하여 인형이 있다면 뽑은 후, 해당 위를 0으로 바꾼다 - 뽑은 인형의 숫자를 바구니의 가장 위와 비교한다. 이때, 바구니가 비어있다면 바로 뽑은..
문제 링크: programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 1. 주의할 점 - 숫자가 크다 → 단순한 풀이로 접근하려고 하면 TLE가 발생한다 - 벡터/배열의 index 범위를 벗어나는지 확인한다 2. 구현 - 이분탐색을 통해 접근한다. 중간값만큼의 사람들이 넘어갈 수 있는가? - 돌의 가장 큰 크기가 200,000,000이므로 이보다 1 더 크게 R을 설정한다. L은 0으로 설정한다 - 0번째 돌까지 뛰는것도 1만큼 뛴것이기 때문에 idx를 -1로 설정하고 점프 크기(J)를 1~K까지로 설정한다 - 현재 위치에서 뛰어서 징검다리의 반..
문제 링크: programmers.co.kr/learn/courses/30/lessons/64064 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr 1. 주의할 점 - 불량사용자와 매칭된 사용자는 탐색할 수 없어야 한다 - 예제 2번과 같이 순서가 같지만 사용자는 같으므로 순열이 아닌 조합이다 2. 구현 - 불량사용자와 매칭된 사용자들이 오름차순으로 정렬하여 Set에 저장하여 조합의 수를 구하도록 한다 - DFS(idx)를 통하여 idx번째 불량사용자와 매칭되는 i번째 사용자를 구한다 - 사용자와 매칭되려면,..
문제 링크: www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 1. 주의할 점 - 한 학생이 자신의 순서를 정확히 아는 경우: 앞에서 몇번째인지 + 뒤에서 몇번째인지 2. 구현 - 모든 순서에 대한 정보를 V[] 벡터에 담는다. 이때, 앞에 나온 수 V[A]에 뒤에 나온 수 B를 추가한다 - 모든 학생들에 대해서 단방향 BFS를 수행하며 해당 학생이 몇명의 다른 학생에게 도달이 가능한지(자기보다 큰 사람)를 canReach[]++를 통해 저장하며, 도달당한 학생..
문제 링크: programmers.co.kr/learn/courses/30/lessons/64065 코딩테스트 연습 - 튜플 "{{2},{2,1},{2,1,3},{2,1,3,4}}" [2, 1, 3, 4] "{{1,2,3},{2,1},{1,2,4,3},{2}}" [2, 1, 3, 4] "{{4,2,3},{3},{2,3,4,1},{2,3}}" [3, 2, 4, 1] programmers.co.kr 1. 주의할 점 - 각 원소를 모두 숫자로 끊는다. 이때, 2자리수 이상을 어떻게 처리해야 하는지 생각한다 2. 구현 - 문자열 S에서 문자 1개씩 읽는다. 이때, 숫자형태인 문자라면 str에 더한다. 아닌 경우, str을 int로 바꾼 이후, 0이 아니라면(""->0으로 치환된다. 또한, 자연수라고 했으므로 0..
문제 링크: programmers.co.kr/learn/courses/30/lessons/64063 코딩테스트 연습 - 호텔 방 배정 programmers.co.kr 1. 주의할 점 - 범위가 1~10^12를 어떻게 처리할 것인가 → 배열 시도시 컴파일 에러 - Room_Number 벡터로 1이 20만개 들어온다고 할때, 하나하나 다음칸을 확인한다 → O(N^2): TLE 2. 구현 - 해당 방이 배정되었다면, 다음 방을 가리키도록 한다 → '유니온 파인드' 처럼 생각한다 → O(NlgN) Ex. 순서대로 2,2,3이 들어오고 추가로 2가 들어온다면, 2,2,3은 모두 다음으로 비어있는 칸인 5를 가리키도록 하여 2가 5에 할당되도록 한다 - Map을 이용하여 10^12도 처리할 수 있도록 한다. Map..