본문 바로가기

정리9

Lv1_[로또의 최고 순위와 최저 순위, C++] 알고리즘 정리 - 프로그래머스 문제 내용, 조건, 예시는 프로그래머스 사이트 참조 이번 문제의 풀어야 할 점은 "일치하는 숫자가 몇개"인지 입니다. 일치하는 숫자는 당연하게 최저 순위가 될 것입니다. 그러면 최고 순위는 (일치하는 숫자 + 낙서로 가려진 숫자의 개수)가 됩니다. 문제 해결방법은 찾았으니 얼마나 효율적으로 찾아낼 수 있느냐만 남아있다. 두 개의 벡터를 비교하는 방법 고민해보면 1) 이중 반복문으로 비교 2) 벡터 정렬 후 index를 가지고 비교 (Lv1. 숫자 짝꿍에서 사용했던 방식; https://workingdog.tistory.com/38) 3) set을 활용해서 중복인 요소 찾아내기 (삽입 연산 insert) 위의 3가지 시간복잡도를 살펴보면 1) O(n*n) (이중 반복문) 2) O(nlogn + n) (so.. 2022. 11. 16.
Lv1_[푸드 파이트, C++] 알고리즘 정리 및 풀이 - 프로그래머스 문제 내용, 조건, 예시는 프로그래머스 사이트 참조 ※ 고려사항 · 물(0)을 제외하고는 동일한 양이 되야하기 때문에 음식의 개수는 짝수가 되야함. · 물을 기준으로 왼쪽, 오른쪽에는 주어진 음식의 양의 절반씩 배치해주면 된다. (2로 나누고 양쪽에 동일하게 배분, 나머지는 버림) 양쪽의 배치는 서로 반전이 되어 있기 때문에 한쪽 배치를 구하면 다른 한쪽은 역배치를 해주면 된다. (ex. 112233 ↔ 332211) 역배치를 하는 법은 reverse() 사용, 반복문을 역으로 실행 등등 있지만 방금 설명한 방식은 추가로 리소스를 소모하기 때문에 불필요한 방법이다. 더 좋은 방법은 한쪽 배치를 할 때, 다른 반대쪽도 배치를 해주는 것이다. · string left_str = left_str + to_st.. 2022. 11. 16.
Lv1_[숫자 짝꿍, C++] 알고리즘 정리 - 프로그래머스 문제 내용, 조건, 예시는 프로그래머스 사이트 참조 간단하고 쉬운방법은 하나씩 전부 비교하면서 일치하는 값이 있으면 추출하는 방식을 사용하면 된다. 하지만 이중반복문으로 돌려야하고 요소삭제까지 하게 된다면 굉장히 비효율적으로 처리를 하게 된다. 그래서 생각한 방식은 X, Y를 내림차순으로 정렬 후에 같은 레벨에서 비교를 하는 것이다. 비교 방법은 아래와 같은 알고리즘을 해택했다. 같은 index_0에서 시작해서 문자를 비교 후에 · 같은 문자면 해당 문자 결과로 저장 후 X,Y index 둘 다 1씩 증가 · 숫자가 다르면 숫자가 큰쪽의 index를 1증가 시킴 · index가 총 사이즈를 넘어가면 작업 종료 예를들면 3) X_index 0 (3) < (5) Y_index 0, Y가 더 큼 → Y_ind.. 2022. 11. 15.
Lv1_[과일 장수, C++] 알고리즘 정리 - 프로그래머스 문제 내용, 조건, 예시는 프로그래머스 사이트 참조 사과박스의 가격은 박스에 들어가 있는 사과 중 최하품 사과 가격으로 정해진다. 그렇기 때문에 가격이 높은 것끼리 박스에 포장으로 하는 것이 가격을 가장 높게 받는 방법이다. · 사과가 저장되어 있는 "vector score"를 내림차순으로 정렬 · m개씩 사과를 포장했을 때, index가 큰 것이 가장 낮은 가격이 됨 [4, 1, 2, 2, 4, 4, 4, 4, 1, 2, 4, 2]를 내림차순으로 정렬을 하면 index [2, 5, 8, 11]의 가격을 m과 곱한 값을 모두 더하면 최대 이익을 만들 수 있다. ※ 조건 중 고려할 사항 - 사과 박스에 m개 미만의 사과가 들어가면 안 됨 - k 매개변수는 사용되지 않음 HTML 삽입 미리보기할 수 없는 소.. 2022. 11. 15.
Lv1_[성격유형 검사하기, C++] 알고리즘 정리 - 프로그래머스 문제 내용, 조건, 예시는 프로그래머스 사이트 참조 문제와 풀이는 길고 복잡하게 보이지만 간단하게 생각하면 쉽게 풀리는 문제 각 지표별 2개의 유형, 0~3까지의 점수를 구해서 알맞은 문자를 리턴 시켜주면 된다. 예를 들어 survey : RT를 정리해보면 위와 같은 형태로 정리가 가능하다. 여기서 choice의 값으로 원하는 index와 점수를 구할 수가 있는데 · score : (choice - 4)의 절대값 · index : (choice / 4)의 정수값 로 계산이 가능하다. ex) survey가 RT이고 choice값이 5인 경우 · score : abs(5 - 4) = 1 · index : (5 / 4) = 1 T[1]에 score는 1점을 얻을 수 있다. (T에 1점 저장) ex) surve.. 2022. 11. 10.
Lv1_[부족한 금액 계산하기, C++] 알고리즘 정리 - 프로그래머스 문제 내용, 조건, 예시는 프로그래머스 사이트 참조 간단한 풀이 방식은 반복문에 넣어서 모든 값을 더해주면 되지만, 위의 문제는 패턴이 있는 덧셈이기 때문에 수식화 하면 간단히 풀 수 있다. ★ 수식화 동일한 간격의 수를 더하는 공식을 계산해보자. · 3 + 6 + 9 + 12 (price : 3, count : 4) 맨 앞과 뒤를 더하고 총개수의 절반만큼 곱해주면 된다. · (3 + 12) + (3 + 9) = (3 + 12) * (4 / 2) = 30 count를 하나 더 늘리면 3 + 6 + 9 + 12 + 15 (price : 3, count : 5) · (3 + 15) + (3 + 12) + 9 = (3 + 15) * (5 / 2) = 45 공식화하면 · (price*1 + price*count.. 2022. 11. 8.
Lv1_[콜라 문제, C++] 알고리즘 정리 - 프로그래머스 문제 내용, 조건, 예시는 프로그래머스 사이트 참조 이 문제는 예제 풀이에 자세히 나와 있기 때문에 알고리즘을 작성해주면 된다. 1) 빈병 a개를 주면 콜라 b개를 주기 때문에 교환비는 a:b가 되고 콜라를 얻는 수는 빈병 곱하기 교환비다. (n/a)로 정수를 뽑아주고 곱하기 b를 해주면 된다. (n/a)*b 2) 교환비에 맞지 않게 남은 공병은 별도로 기억해둔다 (n%a) 3) 얻은 콜라는 마셔서 공병으로 만들어서 남은 공병이랑 같이 더해서 다시 1) 반복 (n = gain_cokeEA + have_left_EmptyCokeEA) 4) 얻은 콜라 수가 a보다 작아질 때 (a>n) 종료한다. HTML 삽입 미리보기할 수 없는 소스 동작 시간은 특별한 것이 없기 때문에 빠르게 넘어갔다. 무언가 특별한 규칙.. 2022. 11. 3.
Lv1_[햄버거 만들기, C++] 알고리즘 정리 - 프로그래머스 (빵 – 야채 – 고기 - 빵) 순서로 햄버거 만들기! 문제 내용, 조건, 예시는 프로그래머스 사이트 참조 제시한 조건을 보면 stack 구조를 사용하는 것이 가장 효율적이라 생각합니다. 아래의 그림과 같이 햄버거 틀(vector)를 만들어서 햄버거 재료를 차곡 차곡 쌓는 방식을 만들어줌 햄버거가 만들어지기 전에 다른 재료들도 들어올 수 있기 때문에 햄버거 틀을 여러개 생성할 수 있도록 햄버거 틀 묶음(vector)을 구성해줌 ex) ingredient = {1, 2, 3, 1} 들어온다면 햄버거 1개를 완성 시킬 수 있다. ex) ingredient = { 1, 2, 1, 3, 1, 1, 2, 3, 1, 2, 3, 1 } 들어온다면 앞쪽 { 1, 2, 1, 3 } 재료는 손실되고 2개의 햄버거를 만들 .. 2022. 10. 31.
DIY - 5평 원룸 정리! 공간박스를 이용해 수납 공간 활용 "DIY 공간박스를 이용한 집 정리" 공간박스를 통해 침대 매트릭스 받침대의 공간이 아주 넓은 수납공간으로 변경 이제부터 작은 5평 원룸의 공간을 정리해보겠습니다. 지금의 집으로 이사하기전 5평 남짓한 원룸에서 살고 있었습니다. 작은 원룸이지만 베란다와 부엌이 분리되어 있는 구조로 실제 생활하는 공간은 체감상 3.5평 정도ㅠㅠ 평소에 인테리어, 공간 정리와 같은 것에 관심이 없었지만 필요성을 느끼게 되어 찾아본 것이 "DIY 공간 박스를 이용한 집 정리" 정리하기 전, 집구조부터 파악하기 위해 간단하게 평면도를 그려보았습니다. (CAD가 없기 때문에 파워포인트를 활용하여 그림) 좁은 원룸에 어울리지 않은 장롱 받침대 없이 사용하고 있는 매트릭스 옷 양에 비해 터무니 없이 작은 이동식 행거 '어울리지 않은.. 2020. 10. 15.
728x90
반응형

티스토리툴바