어흥

문제 링크: programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 1. 주의할 점 - TLE가 날까..? 하는 방식으로 풀어도 TLE가 발생하지 않는다 2. 구현 - 2^20 은 대략 10^6으로 1초인 10^9보다 작으니 브루트포스로 풀어도 가능하다 - 각 수를 총합에서 더하거나 빼면서 진행한다. 끝까지 다다른 경우, Target과 숫자가 일치하면 1을, 아니라면 0을 반환..

문제 링크: programmers.co.kr/learn/courses/30/lessons/43236 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 1. 주의할 점 - 브루트포스로 접근하지 않는다 - 구하려는 수의 범위가 크다 + O(N^2)의 경우로는 TLE가 발생할 것 같다 → 최소 O(NlgN)의 방법으로 접근한다 2. 구현 - 구하려는 답의 크기가 1~10억 사이의 수 → 이분탐색으로 접근 - 파라미터로 전달받은 Rocks의 수가 정렬되어 있지 않다 -> 이분탐색을 위해 정렬 - V 벡터에..

문제 링크: 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번째 사용자를 구한다 - 사용자와 매칭되려면,..

문제 링크: 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..