[Programmers, C++]#Level2_소수 찾기, 백트래킹, 순열 백트래킹, set, 소수, set 컨테이너

2024. 8. 8. 19:13· 문제 풀이/Programmers 문제 풀이
목차
  1. #1. 문제
  2. #2. 풀이
  3. 1. 백트래킹
  4. 2. set 컨테이너
  5. 3. 소수
  6. #3. 코드

#1. 문제

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 


 

#2. 풀이

 

1. 백트래킹

 

[알고리즘]#6_백트래킹

[알고리즘]#6_백 트래킹 백 트래킹 알고리즘에 대해 알아보겠습니다.  Overview 개념예제 #0. 개념1. 백 트래킹백 트래킹 알고리즘은 문제 해결을 위해 여러 후보 해결책들을 점진적으로 탐색하

webddevys.tistory.com

백트래킹은 모든 후보 경로를 점진적으로 탐색해 최적 해를 찾는 알고리즘 기법입니다. 백트래킹은 현재 경로가 문제의 최적 해를 찾을 수 없다고 판단되면, 이전 단계로 돌아가 다른 후보 경로에 대하여 탐색을 진행합니다. 일반적으로, 백트래킹은 재귀 DFS를 통해 구현합니다.

 

2. set 컨테이너

 

[Basic C++] #29_Set, STL 컨테이너

[Basic C++] #29_Set, STL 컨테이너 C++ 개발에서 STL 컨테이너에 대해 알아보겠습니다. C++가 제공하는 STL 컨테이너 중 Set과 MultiSet을 살펴보겠습니다. #0. 개념 1. 개념 Set은 STL에서 제공하는 연관 컨테이

webddevys.tistory.com

set 컨테이너는 C++의 STL에서 제공하는 연관 컨테이너로, 키를 중복 없이 균형 이진 트리에 저장하는 컨테이너입니다. set 컨테이너는 키의 중복을 허용하지 않고, 내부적으로 항상 정렬된 상태를 유지합니다. set 컨테이너의 접근/삽입/삭제 작업의 시간 복잡도는 O(log n)입니다.

 

3. 소수

bool IsPrime(int num)
{
    if(num <= 1) return false;
    if(num == 2) return true;
    if(num%2 == 0) return false;

    for(int i=3; i*i<=num; i+=2)
    {
        if(num%i == 0) return false;
    }

    return true;
}
위 함수는 인자로 전달받은 수의 소수 여부를 판단하는 함수입니다. 외워 두면 좋을 듯?

 


 

#3. 코드

// 정답 코드/*
    @링크: https://school.programmers.co.kr/learn/courses/30/lessons/42839
    @문제: 한 자리 숫자들을 조합하여 만들 수 있는 소수의 개수 구하기
    @설명
        1. 순열 백트래킹(순서 나열)
        2. 빈 문자열 체크
        3. set 컨테이너 활용
*/

#include <string>
#include <vector>
#include <set>
using namespace std;

set<int> primes;
vector<bool> visited;

bool IsPrime(int num)
{
    if(num <= 1) return false;
    if(num == 2) return true;
    if(num%2 == 0) return false;

    for(int i=3; i*i<=num; i+=2)
    {
        if(num%i == 0) return false;
    }

    return true;
}

void dfs(string cur, const string& numbers)
{
    if (!cur.empty())  // 빈 문자열 체크
    {
        try 
        {
            int num = stoi(cur);
            if (primes.find(num) == end(primes) && IsPrime(num))
            {
                primes.insert(num);
            }
        }
        catch (const std::exception& e)
        {
            // 변환 실패 또는 오버플로우 처리
            return;
        }
    }

    if(cur.length() == numbers.length()) return;

    for(int i=0; i<numbers.length(); ++i)
    {
        if(!visited[i])
        {
            visited[i] = true;
            dfs(cur + numbers[i], numbers);
            visited[i] = false;
        }
    }
}

int solution(string numbers) {
    int answer = 0;

    //@방문 여부 초기화
    visited.resize((int)numbers.size(), false);

    //@백트래킹
    string str = "";
    dfs(str, numbers);

    return primes.size();
}

 


 

 

 

저작자표시 (새창열림)

'문제 풀이 > Programmers 문제 풀이' 카테고리의 다른 글

[Programmers, C++]#Level2_큰 수 만들기, stack 컨테이너, stack, 스택  (0) 2024.08.28
[Programmers, C++]#Level2_다리를 지나가는 트럭, 선형 자료구조, queue 컨테이너, deque 컨테이너  (0) 2024.08.22
[Programmers]#Level2_쿼드압축 후 개수 세기, 분할-정복, DFS  (0) 2024.08.02
[Programmers, C++]#Level2_2개 이하로 다른 비트, 비트 연산자  (0) 2024.08.02
[Programmers, C++]#Level2_파일 명 정렬, #include <cctype> 헤더, sort(), Predicate 함수  (0) 2024.07.25
  1. #1. 문제
  2. #2. 풀이
  3. 1. 백트래킹
  4. 2. set 컨테이너
  5. 3. 소수
  6. #3. 코드
'문제 풀이/Programmers 문제 풀이' 카테고리의 다른 글
  • [Programmers, C++]#Level2_큰 수 만들기, stack 컨테이너, stack, 스택
  • [Programmers, C++]#Level2_다리를 지나가는 트럭, 선형 자료구조, queue 컨테이너, deque 컨테이너
  • [Programmers]#Level2_쿼드압축 후 개수 세기, 분할-정복, DFS
  • [Programmers, C++]#Level2_2개 이하로 다른 비트, 비트 연산자
Hardii2
Hardii2
개발 블로그Hardii2 님의 블로그입니다.
Hardii2
개발 블로그
Hardii2
전체
오늘
어제
  • 분류 전체보기
    • 알고리즘
    • 웹 개발
      • Node.js
      • React
    • 게임개발
      • DirectX12
      • 관련 지식
      • Unreal C++
      • Unreal 블루프린트
    • 언어
      • Effective C++
      • Basic C++
      • 디자인 패턴
      • 자료구조
      • 기술 질문
    • 문제 풀이
      • BOJ 문제 풀이
      • Programmers 문제 풀이
      • geeksForgeeks 문제 풀이
    • 수학
      • 확률과 통계
      • 게임수학
    • 개인프로젝트
    • 그룹프로젝트
      • PM
      • Dev
    • Github

블로그 메뉴

  • 홈
  • 글쓰기

공지사항

인기 글

태그

  • 그래프
  • 우선순위 큐
  • Effective C++
  • 개발
  • 정렬
  • dfs
  • Unreal Blueprint
  • BOJ
  • 알고리즘
  • programmers
  • set
  • 디자인 패턴
  • DP
  • stl
  • BFS
  • C++
  • 최단 경로
  • 기술 질문
  • unreal
  • 트리

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
Hardii2
[Programmers, C++]#Level2_소수 찾기, 백트래킹, 순열 백트래킹, set, 소수, set 컨테이너
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.