본문 바로가기

프로그래밍70

Lv1_[명예의 전당(1), C++] 풀이 및 알고리즘 정리 - 프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/138477 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 내용, 조건, 예시는 프로그래머스 사이트 참조 ※ 동료와 코드 리뷰 후 우선순위 큐를 활용해보라는 의견을 듣고 내용 추가 두 가지의 풀이 방식 정렬 함수 (sort) 우선순위 큐 (Priority Queue) 1. 처음 풀었던 sort를 이용한 풀이 방식 1) score 점수 비교 1-1) 최하위 저장된 점수 개수가 k개를 넘지 않을때 → 2-1)으로 이동 1-2) k를 넘거나 같을 때 →.. 2022. 12. 5.
Lv1_[크레인 인형뽑기 게임, C++] 알고리즘 정리 - 프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/64061 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 내용, 조건, 예시는 프로그래머스 사이트 참조 문제의 핵심은 "2차원 배열 되어 있는 보드판과 크레인이 움직일 때 어떤 차원의 인덱스를 증가시켜줄 수 있는지"를 보는 문제이다. 예를들어 3X3 Board에서 move 2번이 들어온다면 크레인을 위의 그림과 같이 배치가 된다. 1) move 2번이지만 board index는 0부터 시작하기 때문에 -1을 해줘서 1번째 위치에서 시작 2) 1차원.. 2022. 12. 4.
Lv1_[신규 아이디 추천, C++] 알고리즘 정리 - 프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/72410 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 내용, 조건, 예시는 프로그래머스 사이트 참조 아래의 조건을 차근차근 풀어나가면서 중복되는 동작을 최소화 해주면 된다. 주어진 단계별로 풀어나간다면 불필요한 탐색이 많아지게 된다 (ex. 1단계 후 2단계를 진행하면 1단계에서 모든 글자 탐색을 마치고 2단계에 또 다시 반복탐색을 하게된다) 1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다. 2단계 new_id에서 알파벳 소문자.. 2022. 12. 4.
Lv1_[문자열 나누기, C++] 알고리즘 정리 - 프로그래머스 문제 내용, 조건, 예시는 프로그래머스 사이트 참조 https://school.programmers.co.kr/learn/courses/30/lessons/140108 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제를 해석해서 풀어보면 아래와 같은 흐름이 나온다. 1) 첫 글자 x를 뽑음 1-1) 첫 글자는 무조건 일치하므로 'same_index+1'을 해주고 다음 인덱스로 넘김 2) 다음 글자와 비교 2-1) 문자가 같으면 same_index+1 2-2) 문자가 다르면 differ_index+1 3) same_index, differ_index의 값.. 2022. 12. 2.
Lv1_[기사단원의 무기, C++] 알고리즘 정리 - 프로그래머스 문제 내용, 조건, 예시는 프로그래머스 사이트 참조 https://school.programmers.co.kr/learn/courses/30/lessons/136798 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이번 문제의 핵심은 약수를 구하는 것이다. 왜냐하면 기사의 number의 약수가 본인의 공격력이 때문에 약수를 구하는 것이 필수! 약수를 구하는 방법이 기억이 잘 안나서 검색해보니 초등학교 5학년..에 배웠던거였음.. https://workingdog.tistory.com/51 약수 구하기 [수학] | "자연수를 어떤 수로 나누었을 때 나누어 .. 2022. 11. 30.
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.
728x90
반응형

티스토리툴바