본문 바로가기

알고리즘 문제풀이

 (73)
[c++] 프로그래머스: 완전탐색 / 숫자 야구 문제 설명 숫자 야구 게임이란 2명이 서로가 생각한 숫자를 맞추는 게임입니다. 각자 서로 다른 1~9까지 3자리 임의의 숫자를 정한 뒤 서로에게 3자리의 숫자를 불러서 결과를 확인합니다. 그리고 그 결과를 토대로 상대가 정한 숫자를 예상한 뒤 맞힙니다. * 숫자는 맞지만, 위치가 틀렸을 때는 볼 * 숫자와 위치가 모두 맞을 때는 스트라이크 * 숫자와 위치가 모두 틀렸을 때는 아웃 예를 들어, 아래의 경우가 있으면 A : 123 B : 1스트라이크 1볼. A : 356 B : 1스트라이크 0볼. A : 327 B : 2스트라이크 0볼. A : 489 B : 0스트라이크 1볼. 이때 가능한 답은 324와 328 두 가지입니다. 질문한 세 자리의 수, 스트라이크의 수, 볼의 수를 담은 2차원 배열 baseba..
[c++] 프로그래머스: 완전탐색 / 소수 찾기 문제 설명 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요. 제한사항 numbers는 길이 1 이상 7 이하인 문자열입니다. numbers는 0~9까지 숫자만으로 이루어져 있습니다. 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다. 입출력 예 numbers return 17 3 011 2 입출력 예 설명 예제 #1 [1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다. 예제 #2 [0, 1, 1]으로는 소수 [11, 101]를 ..
[c++] 문자열, 숫자 변환 / stoi 함수 / to_string 함수 / string -> integer로 변환 http://www.cplusplus.com/reference/string/stoi/ stoi - C++ Reference function template std::stoi int stoi (const string& str, size_t* idx = 0, int base = 10); int stoi (const wstring& str, size_t* idx = 0, int base = 10); Convert string to integer Parses str interpreting its content as an integral number of the spe www.cplusplus.com // stoi example #include // std::cout #in..
[c++] 완전탐색(Brute-Force) / 순열 / next_permutation 함수 완전탐색(Brute-Force) 가능한 모든 경우의 수를 탐색하는 방법 순열 1) next_permutation() 사용 next_permutation - C++ Reference: http://www.cplusplus.com/reference/algorithm/next_permutation/ 1. sort()로 정렬(오름차순) 2. do-while문의 조건 안에 next_permutation() 3. next_permutation의 parameter은 (첫번째 원소 주소, 마지막 원소 주소) 4. parameter로 넘긴 원소의 위치가 바뀌는 것, 이를 응용하여 쓸 것 // next_permutation example #include // std::cout #include // std::next_per..
[c++] 프로그래머스: 깊이 우선 탐색(DFS) / 단어 변환 문제 설명 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> cog와 같이 4단계를 거쳐 변환할 수 있습니다. 두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solu..
[c++] 프로그래머스: 깊이 우선 탐색(DFS) / 네트워크 문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[..
[c++] 프로그래머스: 깊이 우선 탐색(DFS) / 타겟 넘버 문제 설명 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 주어지는 숫자의 개수는 2개 이상 20개 이하입니다. 각 숫자는 1 이상 50 이하인 자연수입니다. 타겟 넘버는 1 이상 1000 이하인 자연수입니다. ..
[c++] DFS(깊이 우선 탐색) / 개념 / 함수 구현 DFS(깊이 우선 탐색) - 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 - 스택 또는 재귀함수로 구현 DFS: Stack(스택) // DFS 구현 - 스택 // 답: 1, 2, 4, 6, 5, 7, 3 #include #include #include using namespace std; // 인접행렬로 표현한 그래프 vector adjacent = { { 0,1,1,0,0,0,0 }, { 1,0,0,1,1,0,0 }, { 1,0,0,0,0,0,1 }, { 0,1,0,0,0,1,0 }, { 0,1,0,0,0,1,0 }, { 0,0,0,1,1,0,1 }, { 0,0,1,0,0,1,0 }, }; // 노드 방문 여부 표시 벡터 ..

티스토리툴바