코딩테스트 공부

https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 문제 설명 강의의 시작 시간과 끝나는 시간을 주어졌을 때 모든 강의를 할 수 있게 몇개의 강의실을 빌려야하는지를 계산하는 프로그램을 구현해야 합니다. 문제에 대한 아이디어 이 문제는 회의실 배정문제와 유사합니다. 그래서 처음에는 인풋값을 끝나는 시간을 기준으로 오름차순 정렬을 하고 우선순위 큐에 집어 넣으면서 만약 현재 우선순위 큐에 peek 값보다 시작하는 시간이 작다면 우선순위 큐에 넣어주는 형식으로 진행을 했습니다. 예를 들어 1 3을 집..

https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 문제 설명 도시의 노드 연결 여부가 알려주면 주어지는 여행 계획을 수행 할 수 있는지 찾는 알고리즘을 구현하는 문제입니다. 문제를 풀기 위한 아이디어 예제 입력을 보면 인접 행렬로 입력값을 주어지는 것을 알 수 있습니다. 그러므로 인접 행렬을 이용해 문제를 푸는 방식으로 생각해봤습니다. N은 최대 200 이고 M은 1000이하 인 것을 알 수 있습니다. 시간 제한이 2초 이므로 모든 노드를 돌아봐..

https://school.programmers.co.kr/learn/courses/30/lessons/49190 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 입력으로는 방향이 주어진다. 이 방향으로 움직였을 때, 방이 생기는지 확인하면 됩니다. 예시로 살펴보면 주어진 방향대로 움직이면 삼각형 1개, 큰 사각형1개, 평행사변형 1개가 생깁니다. 문제에 대한 아이디어 이 문제는 프로그래머스 코딩 테스트 문제 풀이 전략에서 나온 문제입니다. 간선을 지나갔는지 유무를 확인하는 문제를 어떻게 풀어야 할까 고민하고 있었는데 책에 이 문제가 있어 책의 ..

https://school.programmers.co.kr/learn/courses/30/lessons/42584# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 문제 설명이 약간 애매합니다. 1초에 가격에서 앞으로 5초 동안 떨어지지 않으므로 4입니다 2초 시점에 2의 가격은 앞으로 2보다 떨어진 가격이 없으므로 3입니다. 3초 시점에 3의 가격은 바로 1초 후에 떨어지므로 1입니다. 4초 시점은 1초 후까지 가격이 떨어지지 않습니다. 문제에 대한 아이디어 제일 처음 생각은 뒤에서 부터 값을 추가해 그 때 제일 낮은 숫자의 인덱스를 가지고 있..

https://school.programmers.co.kr/learn/courses/30/lessons/142085# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 각 라운드 마다 적의 수를 알려줄 때 무적권을 적절하게 잘 사용해서 최대한 많은 라운드를 처리해야 합니다. 예를 들어 4,4,5를 무적권을 사용해 처리하고 2,3을 병사로 처리하면 병사는 2명 남습니다. 다음 라운드에 3명의 적이 오므로 라운드를 해결할 수 없으므로 최대 5라운드 까지 처리 가능합니다. 문제에 대한 아이디어 제일 처음 생각한 방법은 enemy를 정렬해서 k 번째 큰 ..

https://school.programmers.co.kr/learn/courses/30/lessons/161988 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 이 문제는 부분 수열의 최대 합을 구하는 문제와 엄청 유사합니다. 다른 점은 펄스 수열을 곱한 부분 수열의 최대 합을 구하는 것입니다. 문제에 대한 아이디어 부분 수열의 합을 구하는 방법은 DFS를 통해 모든 경우를 조사해서 최대 합을 찾는 방법이 존재합니다. 하지만 이 문제에서는 최대 500000개 이므로 DFS로 탐색하면 시간 초과가 나올 것입니다. 그러므로 O(n) 안에 풀어야 ..

문제 설명 https://school.programmers.co.kr/learn/courses/30/lessons/42746 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr int 배열이 주어지면 각 숫자를 적절하게 조합해 제일 큰 숫자를 만들면 됩니다. 문제에 대한 아이디어 주어진 int 배열을 적절한 조건에 맞게 정렬을 하면 될 것 같습니다. 문제는 2번 예시처럼 3, 30, 34를 어떻게 정렬할 것 인가 입니다. 둘 다 맨 앞자리는 똑같지만 뒤의 자리와 합한 숫자의 크기를 각각 비교해봐야 합니다!! 이렇게 비교하면 조건이 굉장히 많이 필요할 것 같습니..

https://school.programmers.co.kr/learn/courses/30/lessons/64064 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 fr*d*과 일치하는 것은 frodo, crodo abc1**과 일치하는 것은 abc123 그러므로 조합은 frodo abc123, crodo abc123 2개입니다!! 문제에 대한 아이디어 배열의 크기는 1이상 8이하 입니다. banned_id도 이보다 작기때문에 완전 탐색으로 가능할 것 같습니다. banned_id와 일치하는 user_id를 찾습니다. 각각 user_id를 모든 조합..