반응형 Algorithm143 [완전탐색, 난이도 중] 프로그래머즈, 소수 찾기 종이 조각을 조합할 수 있는 모든 경우의 수를 탐색해야 하는 브루트포스 문제이다. prime_check 함수는 소수 여부를 판단하는 함수이다. 각 자릿수는 0~9로 이루어져 있으니 문자열 numbers를 문자 단위로 쪼개서 arr 벡터에 넣고 계산을 수행했다. 순열을 이용하여 arr 벡터의 요소들을 조합하여 자료형만 문자열인 정수를 만들어낸뒤, stoi 함수를 이용하여 자료형을 string에서 int로 변환해주었다. permutation이 순열 함수이고 매개변수는 (총 요소의 수, 고를 요소의 수, 재귀함수 깊이) 이다. 순열 알고리즘에 대해 다룬 포스팅 링크이다. kimcoder.tistory.com/115 재귀를 이용한 간단한 순열 알고리즘 이 소스코드는 중복 요소도 허용한다. 중복 요소를 지우고 싶.. 2020. 9. 22. 재귀를 이용한 간단한 순열 알고리즘 이 소스코드는 중복 요소도 허용한다. 중복 요소를 지우고 싶다면 erase, unique 함수를 이용하면 된다. 중복 요소 제거 방법에 대한 포스팅 링크도 첨부했다. kimcoder.tistory.com/100?category=887790 벡터 정렬 후, 중복 요소 제거하기 1. 필요 헤더 vector, algorithm 2. 필요 함수 sort : 범위 퀵 정렬 unique : 연속된 중복값을 맨 뒤로 보내고, 중복값이 시작되는 주소를 리턴한다. erase : 범위 모두 제거 3. 소스 코드 ※ unique 함수는 연속.. kimcoder.tistory.com 순열은 조합과 달리 요소의 순서가 중요할 경우 쓰인다. 순서까지 고려하여 1,2,3,4중 3개를 고르는 경우들이다. 경우의 수는 4P3=24이다.. 2020. 9. 22. 삽입, 삭제 모두 O(logn)!! STL priority_queue 소개 priority_queue는 큐에 데이터가 삽입, 삭제 되어도 데이터들의 우선순위를 유지해주는 라이브러리이다. priority_queue는 힙 구조로 구현되므로 삽입과 삭제의 시간 복잡도는 O(logn) 밖에 되지 않는다. 프로그래머라면 O(n)과 O(logn)의 차이가 얼마나 큰지 알고 있을 것이다. 후자는 거의 상수 취급 하기도 할 정도로 시간복잡도를 매우 단축할 수 있다. 힙 구조에 대한 자세한 설명은 아래 링크를 보면 좋다. ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) 힙 (자료 구조) - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 1부터 100까지의 정수를 저.. 2020. 9. 16. 스택/큐 고득점 kit 풀이 완료, 후기 스택은 데이터를 후입선출(LIFO) 구조를 유지하는 자료구조, 큐는 데이터를 선입선출(FIFO) 구조를 유지하는 자료구조이다. 이를 물론 배열/벡터와 인덱스 변수만으로 구현 할 수도 있다. 그리고 C++에서는 라이브러리를 제공한다. 데이터는 push함수로 넣고 pop함수로 뺄 수 있다. 스택과 큐 라이브러리는 빈 상태(empty) 여부를 판단하는 empty함수도 제공하고 스택의 front 함수, 큐의 top 함수로 가장 앞에 있는 데이터도 확인 할 수 있다. 이 라이브러리를 사용하여 코드도 줄이고 가독성도 올리는 것을 추천한다. 고득점 kit에 있는 스택/큐 문제들도 해결하기 까지 어느정도 생각이 필요했지만 전반적으로 어렵지 않게 풀 수 있었다. 문제모음 [난이도 하] 주식 가격 kimcoder.tist.. 2020. 9. 16. [스택/큐, 난이도 하] 프로그래머즈, 주식가격 이 문제는 맞추고도 당황했다. prices의 길이는 최대 100000인데 prices의 길이에 대한 이중 반복문을 사용했는데 효율성까지도 만점을 받았다. 그래서 난이도를 '하' 로 정했다. 뒤의 요소들을 탐색하면서 시간을 계속 더해주되, 주식가격이 현재가격보다 아래가 되는 경우 바로 break를 해줘서 그런 것 같은데, 테스트 케이스들이 최악의 경우 까지는 고려를 안해서 그런 것 같다. prices의 길이가 100000이고, 주식 가격이 계속 오르기만 하는 경우에서 최악의 시간 복잡도가 나올 것이다. 현재의 주식 가격과 그 다음의 주식 가격의 관계만 신경 쓰면 되므로 이 문제에서 요구하는 것은 스택이라고 볼 수 있다. 벡터와 인덱스 변수만으로도 스택을 흉내낼 수 있기도 하고 벡터를 이용하는 것이 소스 코.. 2020. 9. 16. [스택/큐, 난이도 중하] 프로그래머즈, 기능개발 먼저 배포되어야 하는 작업의 순서가 정해져 있는 것을 보아 큐를 이용하여 푸는 문제임을 알 수 있었다. 이번엔 큐 라이브러리를 이용하지 않고 현재 작업중인 작업 번호 변수를 만들어 큐의 역할을 흉내냈다. 큐를 이용한다면 입력 vector의 요소들을 큐에 모두 넣는 작업이 필요한데 굳이 그럴 필요까진 없었기 때문이다. 앞에 있는 task의 진도율이 100이 아닌 경우, 100이 나올 때 까지 계속해서 현재 진도율에 speed값을 더해준다. 반복할때마다 날짜는 1씩 더해준다. 그리고 앞에 있는 task의 진도율이 100을 달성 했을 경우, 한번에 배포할 수 있는 작업수와 작업 번호를 모두 1씩 증가시켜주면 된다. 그 뒤에 있는 task들에도 날짜와 speed를 곱한 값을 더해보고 진도율이 100을 달성 했을.. 2020. 9. 15. [스택/큐, 난이도 중하] 프로그래머즈, 다리를 지나는 트럭 트럭은 1초에 최대 1번 다리에 들어올 수 있고, 최대 1번 나갈 수 있다. 즉 초를 세는 변수를 만들고, 반복문 안에 트럭이 다리에 들어오는 조건문과 나가는 조건문을 하나씩 세워주면 된다. 제일 앞에 있는 트럭의 입장 시각이 현재 시각에 다리의 길이를 뺀 값이 되면, 누적 무게에서 이 트럭의 무게를 빼고 queue에서 pop시켜주고 누적 무게에 가장 앞에 대기중인 트럭의 무게를 더해봐서, 제한 무게를 넘어가지 않는다면 queue에 push 해주면 된다. queue 안에 들어있는 pair 정보는 트럭의 무게와 입장 시각이다. 테스트 케이스 14개 모두 통과 #include #include using namespace std; int solution(int bridge_length, int weight, .. 2020. 9. 14. [그리디, 난이도 중하] 프로그래머즈, 체육복 체육복 여벌이 있는 학생들이 옆에 있는 학생에게 체육복을 빌려주었다고 했을 때 체육복을 가지고 있는 최대 학생 수를 구하면 되는 문제이다. 나의 풀이는 이렇다. boolean 배열 2개를 생성하고 다음 조건에 맞게 true/false를 부여해야 한다. phy[ ] : 체육복을 1벌 이상 가지고 있는지 여부를 판단 phy_reserve[ ] : 체육복을 2벌 가지고 있는지 여부를 판단 (여벌) 초기 bool phy[ ]는 true로 초기화 해두었다. reserve벡터를 참조하여, 체육복을 2벌 가지고 있는 학생은 phy_reserve 배열값을 true로 만든다. 그리고 lost벡터를 참조하여 2가지 경우에 대해 처리해준다. 여벌을 가지던 학생이 도난 당하면 1벌 남으므로 phy_reserve 배열 값을 f.. 2020. 9. 12. [완전탐색, 난이도 중하] 프로그래머즈, 카펫 brown+yellow 개의 격자는 brown+yellow의 두 약수 n,m 의 곱으로 이루어질 수 있다. 이렇게 해서 가능한 두 약수의 조합들을 완전탐색하는 문제이다. 매개변수로 들어온 정수의 약수들을 모두vector에 담아서 그 vector을 리턴하는 함수를 추가로 만들었다. 두 약수를 n, m이라고 하자. 아래와 같이 n x m 카펫이 주어 졌을 때, 갈색 격자의 개수는 m*2+n*2-4 이다. 주어진 갈색 격자의 개수와 같게 나왔을 경우 m,n 값을 answer에 담아 리턴하면 된다. 테스트 케이스 13개 모두 통과 #include using namespace std; vector get_prime_numbers(int n){ vector prime_numbers; for(int i=1;i 2020. 9. 11. 이전 1 ··· 6 7 8 9 10 11 12 ··· 16 다음
