본문 바로가기

프로그래머스8

Lv2_[전화번호 목록, C++] 풀이 및 알고리즘 정리 - 프로그래머스 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 내용, 조건, 예시는 프로그래머스 사이트 참조 '한 번호가 다른 번호의 접두어인 경우'를 찾아야하기 때문에 아래와 같은 생각을 했습니다. "길이가 짧은 것을 앞에 배치하고 크기에 따라 정렬하면 편하겠다" 위의 내용을 감안하여 알고리즘을 짜봤습니다. 알고리즘 sort 오름차순 정렬을 통해서 크기가 작은 값을 앞에 배치 ("234" < "1234") string 비교는 길이 짧은것이 작다고 판단, 길이가 같으면 크기 순으로 정렬) 정렬된 순서대로 인접한 두 문자열을 비교 비교할 때는 작은 문자열 기준으로 크.. 2023. 5. 28.
소수(Prime Number) 구하기 - 에라토스테네스의 체 해당 수가 소수라는 것을 판별하는 방법은 이전 포스팅에 했었다. [C++] 소수(Prime Number) 효율적으로 구하기 소수(Prime Number) https://ko.wikipedia.org/wiki/%EC%86%8C%EC%88%98_(%EC%88%98%EB%A1%A0) 소수 (수론) - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 각각의 자리에 놓인 숫자와 소수점을 통해 workingdog.tistory.com 그러면 1부터 n 사이에 있는 소수의 개수는 어떻게 구할까? 바로 생각 나는 방식은 소수를 판단하는 알고리즘을 반복시켜주면 되지만 숫자가 커질 수록 점점 많은 수의 연산이 필요하게 된다. 그래서 소수 관련 문제를 풀 때 자주 사용되는 방법으로 "에라토스테네스의 체"를.. 2022. 12. 26.
[C++] 유클리드 호제법 (최대공약수, 최소공배수) 유클리드 호제법 또는 유클리드 알고리즘 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘 예시) 1112와 695를 반복해서 MOD 연산 유클리드 호제법(Euclidean-algorithm) 유클리드 호제법에 대해 알아보자. velog.io 최대공약수 GCD (Greatest Common Divisor) 139일 때 나머지가 0이 되므로 최대공약수는 139가 된다. 최소공배수 LCM (Least Common Multiple) 두개의 수를 곱한 뒤 최대공약수로 나눠주면됨 (1112 * 695) / 139 = 5560 코드 HTML 삽입 미리보기할 수 없는 소스 2022. 12. 9.
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_[옹알이(2), C++] 알고리즘 정리 - 프로그래머스 (map, 재귀함수 사용) 문제 내용, 조건, 예시는 프로그래머스 사이트 참조 입력으로 문자열 배열(babbling)과 조카의 발음을 비교하기 쉽게 구분을 했습니다. 조카의 발음을 알파벳으로 구분해서 map에 저장해두는 방식을 사용 이유는 네 가지 발음만 사용할 수 있기 때문에 다른 발음이 들어오면 발음을 할 수 없기 때문이죠. ex) "yezma"가 입력일 때, z가 들어오면 발음할 수 없는 알파벳이므로 해당 문자열은 발음하지 못하는 것으로 결론내릴 수 있음. - map _m; - map (※map 대신 unordered_map을 사용해도됨. 조건과 상황에 따라 변경 가능) 와 같은 형태로 저장된다. 이렇게 구성을 하는 이유는 검색 속도를 높이기 위함이다. 지금 예시에는 발음이 4개 뿐이 없어서 단순 반복문(for)으로 검색해도.. 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.
728x90
반응형

티스토리툴바