뚝딱뚝딱

소프티어의 "성적 평균" 문제를 풀다가 "평균을 소수점 셋째 자리에서 반올림하여 표시" 하도록 요구되어 있었다.

printf에서는 "%.2f"엿던가..? 

c++에서 iomanip 헤더에 있는 setprecision을 사용하면 소수점 반올림이 가능하다.

cout으로 출력을 낼 때는 다음 두가지 경우로 나누어 표현할 수 있다 

✔ fixed를 안붙이는 경우

double a = 3.1415
cout<<setprecision(3)<<a<<endl;

//출력 : 3.14

fixed의 역할은 고정 소수점 표기를 해주는 것인데, 위처럼 fixed를 쓰지 않으면, setprecision(3)에 의해서 3번째 자리수에서 반 올림하고, 3.14로 출력된다.

만약 a가 3.000이었다면, 소수점이하의 값은 날라가서 3으로 출력된다.

✔ fixed를 붙이는 경우

double a = 3.1415
cout<<fixed<<setprecision(3)<<a<<endl;
//출력 : 3.142

 fixed를 붙이면 3번 째 자리까지 반올림 된 값이 출력이 된다.

따라서 문제에서는 3번째 자리에서 반올림하여 둘째 자리까지 표시되도록 (3.00) 하였으므로, fixed를 붙이고 setprecision(2)로 하여 출력하였다.

소프티어의 "성적 평균" 문제를 풀다가 사용했던 2차원 배열 동적 할당에서 어이없는 오류를 냈다.

기본 of 기본인데.. 이 참에 한번 짚고 넘어간다!

✅ 배열 동적 할당

✔ 1차원 배열을 동적 할당 시

//int 배열을 받는다고 가정하겠습니다.
int N=100;
int *arr = new int[N];
//크기가 100인 int타입의 배열을 동적 할당해주었습니다. arr이라는 이름으로요.

✔ 2차원 배열을 동적 할당 시

//동일하게 int 타입의 배열을 생성하겠습니다.
int N = 100;
int **arr = new int*[N];
//1차원과 다른 점은 바로 이 부분입니다. arr을 2차원으로 생성한다면, 먼저 1차원 포인터 배열을 가리키도록 해야겠죠?

for(int i=0; i<N; i++){
	arr[i] = new int[N];//그리고 각각의 1차원 포인터에 크기가 N인 배열을 가리키도록 해주어야 2차원 형태가 됩니다.
}

어떤 실수를 했었냐면, **arr = new int[N][N]; 이렇게 해버린 것이다.. 뒤에 [N][N]은 정적 배열을 생성할 때 하는 것인데.. 이런 실수를 더이상 하지말자!!!!!

main함수의 맨 위에 다음 세 줄을 적어주면, cin, cout과 같은 입출력 스트림 사용 시 시간을 좀 더 단축할 수 있다.

하지만, n의 크기가 커지면 입출력으로 인한 시간 단축은 별로 의미가 없을 수 있다는 점을 알아두자.

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

ios_base::sync_with_stdio(false)는 C++ 스트림과 C 스타일 스트림 간의 동기화를 비활성화 해준다.

이렇게하면 C++ 스트림과 C 스타일 스트림이 각각 독립적으로 작동하며 데이터가 교차되지 않는다.

cin.tie(NULL)와 cout.tie(NULL)는 C++ 스트림의 버퍼와 C 스타일 스트림 간의 결합도를 제거한다.

tie(NULL)은 출력 스트림의 버퍼와 입력 스트림의 버퍼를 연결하지 않도록 설정한다.

따라서 불필요한 교차로 인해 발생하는 시간을 줄일 수 있으므로, 적은 양의 데이터를 이용하는 프로그램에서는 유용할 수 있다.

하지만, 교차가 필요한 경우에는 예기치 못한 상황이 발생할 수 있으니, 사전에 꼭 확인하고 사용하여야 한다.

***정렬을 이용한 c++ 코드가 필요하다면 아래의 블로그를 참고하세요***

2023.10.18 - [CO-TE/challenge] - [프로그래머스] JAVA / c++ LV2 전화번호 목록 / 해시알고리즘, SORT 풀이 (1)

이번에는 해시 알고리즘을 이용한 java 풀이법을 살펴보겠다.

💡 ''해시 알고리즘''??

해시(hash)는 임의의 데이터를 고정된 길이의 숫자나 문자열로 변환하는 과정이다.

HashMap
- 해시를 사용하는 자료 구조의 일종이다.
- HashMap은 키-값 쌍을 저장하고, 이러한 키-값 쌍에 대한 빠른 검색 및 검색을 지원합니다
- 문자열을 가지고, 해당 문자열이 HashMap에 있는지 바로바로 찾아주기 때문에 O(1)의 복잡도를 갖는다.

HashMap을 활용해서 HashMap에 전화번호 목록들을 키-값 쌍으로 저장하는 과정이 필요하다.

HashMap에 있는 값들은 이제 HashMap에서 지원하는 찾기 함수를 통해서 바로바로 찾아 낼 수 있다.

 java / HashMap 사용 

1. 먼저 HashMap을 Map<>을 통해서 생성하자.

• HashMap의 경우 java.util.HashMap에 정의되어 있으므로 import해준다.
• Map의 경우 java.util.Map에 정의되어 있으므로 import해준다.

import java.util.HashMap;
import java.util.Map;

• HashMap은 Map 인터페이스를 구현한 클래스로, Map<>의 객체에 HashMap의 생성자로 생성되도록 할 수 있다.
• 전화번호의 경우 String문자열로 되어 있기 때문에, <String, Integer>를 키-값 쌍으로 갖는 Map을 생성한다.
• 사실상 Integer(값)는 쓸 일이 없고, Map을 활용하기 위한 것이므로, 인덱스를 넣어주겠다.

Map<String, Integer> map = new HashMap<>();

2. HashMap에 phone_book에 있는 값들을 키로, 그리고 인덱스를 값으로 넣어준다.

for(int i=0; i<phone_book.length; i++){
            map.put(phone_book[i], i);
        }

• 여기서 주의할 점..phone_book의 배열 크기는 .length로 얻어 올 수 있다. (c++의 size()와 헷갈리지 말자)
• map에 요소를 넣을 때는 put을 사용하고, 지정해준 키-값 쌍을 인자로 넣어주면 된다.

3. 2중 for문을 통해서 phone_book에 있는 전화번호 각각의 접두어가 HashMap에 있는지를 확인한다.

for(int i=0; i<phone_book.length; i++){
            for(int j=0; j<phone_book[i].length(); j++){
                if(map.containsKey(phone_book[i].substring(0,j))){
                    return false;
                }

• 현재 가리키는 전화번호의 0부터 j번 까지의 문자열이 HashMap의 키를 통해 검색한 결과에 있으면, j번까지의 접두어로 존재하는 전화번호가 있다는 의미이기 때문에, false를 반환하도록 한다.
• 이때 사용하는 map의 함수가 containsKey()로, 검색하고자 하는 값을 인자로 넣어주면 된다.
• 자바에서 String의 substring()함수는 자르고자 하는 문자열의 시작 인덱스와 끝인덱스를 인자로 넣어주고, 만약 인자를 하나만 적는다면 해당 시작부터 끝까지 잘라준다.
• string의 쓰임같은 경우 c++에서와 헷갈리지 않도록 주의한다!!!
• 참고로 문자열의 길이를 반환할 때는 .length()이다! 

이렇게 해시를 이용하면 바로바로 문자열을 map의 함수를 통해 검색할 수 있으므로 효율성에서 높아진다.

전체코드는 아래와 같다.

//해시로 풀이
import java.util.HashMap;
import java.util.Map;

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        Map<String, Integer> map = new HashMap<>();
        
        for(int i=0; i<phone_book.length; i++){
            map.put(phone_book[i], i);
        }
        
        for(int i=0; i<phone_book.length; i++){
            for(int j=0; j<phone_book[i].length(); j++){
                if(map.containsKey(phone_book[i].substring(0,j))){
                    return false;
                }
                    //substring은 start index부터 end index까지
                    //java에서는 string size가 아니고 배열 크기는 length, 배열 안에서 문자열                        길이는 length() 
            }
        }
        
        
        return answer;
    }
}

***해시알고리즘을 사용한 java 코드가 궁금하다면 아래 블로그를 참고하세요***

2023.10.18 - [CO-TE/challenge] - [프로그래머스] java / c++ LV2 전화번호 목록 / 해시알고리즘, SORT 풀이 (2)

이 문제는 처음에 c++로는 2중 for문을 돌면서, 배열에서 첫번째 전화번호를 기준으로 시작하여, 다른 전화번호들 중 기준이 되는 전화번호보다 길이가 작으면 continue로 건너 뛰고, 그렇지 않으면, substr을 사용해 기준 전화번호 길이만큼 잘라서 비교한 후, 문자열이 동일하면 false를 반환하는 방식으로 접근했다.

이렇게 하면 테스트 케이스는 다 맞지만, 효율성에서 떨어지게 된다. 당연히 무식하게 2중 for문으로 일일이 확인하기 때문에 복잡도가 O(n^2)일 수 밖에 없다.

문제의 카테고리에서 주어진 방식대로 해시 알고리즘을 사용해서 풀면 효율성 문제를 해결할 수 있지만, 사실 해시 알고리즘을 어떻게 사용하는지 몰랐기 때문에, 다른 사람의 코드를 보고 참고하여 먼저 정렬을 이용해 더 쉽게 풀이하였다.

  c++ / sort 함수와 1중 for문으로 풀기 

string 타입의 배열 phone_book을 <algorithm> 헤더에 있는 기본 정렬 함수인 sort()를 통해 정렬한다.

숫자로 표현된 문자열의 경우 사전식으로, 각 문자열의 첫번째 값부터 비교한다. 

첫번째 값들이 다 동일하면 두번째 값을 비교한다.

즉 숫자 그 자체가 큰지가 아니라, 앞에 문자열부터 각 숫자가 작은 것 부터 정렬하는 방식이다

예) "12" "14" "112" 가 있으면, 112, 12, 14 순으로 정렬 된다.

첫번째 1은 모두 같고, 두번째 값이 1,2,4순이기 때문이다.

따라서 이렇게 정렬을 먼저 해 놓으면, 자연스럽게 접두사가 될 확률이 높은 문자열이 앞에 위치하게 되고, 해당 접두사를 가지는 문자열은 무조건 그 문자열의 다음에 정렬될 것이기 때문에, 이 방법은 1중 for문으로도 인접한 문자열에 대해 한번씩만 비교하면 된다. 

해당 코드는 아래와 같다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    
    sort(phone_book.begin(), phone_book.end());
    
    for(int i=0; i<phone_book.size()-1; i++){
        string s = phone_book[i+1].substr(0, phone_book[i].size());
        if(phone_book[i]==s) {
            answer = false;
            break;
        }
    }
  
    return answer;
}

• sort함수에 배열의 첫번째 요소와, 배열의 마지막 요소를 인자로 넣어주면, 자동으로 정렬된다.
• 1중 for문을 통하여 string 문자열 s에는 현재 접근하는 phone_book의 전화번호 바로 다음에 위치한 전화번호를, 접두사 길이 만큼 잘라 (substr을 사용) 저장한다. 이때 c++에서는 substr(시작 인덱스, 자르고 싶은 만큼의 문자열 크기) 이므로 이에 유의한다. 
• 그래서 현재 접두사 후보의 값과 s가 일치한다면 false를 반환하도록 answer에 설정해준다.

사실상 해시 알고리즘으로 푸는 의도의 문제이긴 하지만, 실제 코테에서는 이 방법을 꼭 사용하라는 명시가 없기 때문에, 위와 같이 효율적인 코드가 생각이 난다면 당연히 사용해도 좋다.

그러나 해시 알고리즘을 이번 기회에 알고 넘어 가기 위해 java를 이용해서 한번 더 풀어보았다.

2탄에서 이어서...

DFS/BFS 알고리즘의 대표적인 문제 "타겟 넘버"의 풀이방법이다.

그 전에 DFS/BFS의 개념을 정리하자면,

그래프와 트리와 같은 자료 구조에서 사용되는 탐색 알고리즘이다.

문제에 따라서 각각의 접근방식을 달리 사용할 수 있다.

💡 DFS (깊이 우선 탐색)

• 깊이 우선 탐색은 한 분기를 끝까지 탐색한 후 다음 분기로 넘어가는 방식의 탐색 알고리즘이다.
• 시작 노드에서 출발하여 가능한 한 깊이 들어가면서 탐색한다.
• 주로 재귀 함수를 사용하여 구현하거나 스택(Stack)을 이용한다.
• 특정 경로를 탐색하다가 더 이상 진행할 수 없는 상황에 도달하면 이전 단계로 돌아와 다른 경로를 탐색한다.
• DFS는 그래프에서 사이클을 찾거나 깊이에 관한 문제를 해결하는 데 유용하다.

예시) 미로를 탐색할 때 한 방향으로 직진하다가 막히면 되돌아가서 다른 방향으로 계속 진행하는 방식이다.

💡 BFS (너비 우선 탐색)

• 너비 우선 탐색은 시작 노드에서부터 가까운 노드부터 차례대로 탐색하는 방식의 탐색 알고리즘이다.
• 큐(Queue) 자료 구조를 사용하여 구현한다.
• 주로 최단 경로를 찾는 문제에 사용되며, 모든 가까운 노드를 우선 탐색하여 최단 경로를 찾아낸다.
• BFS는 그래프에서 사이클을 찾지 않고, 가까운 노드를 먼저 탐색하는 데 적합하다.

예시) 같은 미로에서 모든 가로행을 먼저 탐색하고, 그 다음에 세로열을 탐색하는 방식이다.

결론적으로

DFS는 깊이 관련 문제를 해결할 때 유용하며, BFS는 최단 경로와 가까운 노드를 탐색할 때 효과적이다.

그럼 다시 본론으로 돌아와서...

해당 타겟 넘버 문제를 살펴보자. 

문제에서는 주어지는 숫자 배열 numbers를 각각 더하거나 빼면서 target 값을 생성하는 방법을 반환하는 solution을 찾도록 되어있다.

그렇다면 numbers에 있는 숫자 개수 만큼 + 또는 -의 연산자가 필요하다.

모든 숫자 앞에는 + 또는 -의 연산을 해야하므로, 각각의 숫자는 + 또는 - 중에 선택되어야 하며, 트리 형태로 표현해보면 다음과 같이 표현할 수 있다.

즉, 모든 경우의 수에 대해서 끝까지 탐색해 봐야 target 값이 도출되는지를 확인할 수 있다.

따라서 위 문제는 DFS로 해결할 수 있다.

DFS는 재귀 함수를 이용한다. 그럼 재귀함수를 어떻게 구성할 수 있을까?

한번의 연산에서는 +연산을 했을 때와 -연산을 했을 때의 두가지 경우를 고려할 수 있기 때문에, 두 연산을 각각 수행할 수 있도록 재귀함수를 사용해야 한다.

그런데, 마지막 노드에 대해서는 더이상 탐색할 것이 없기 때문에=해당 분기에 대해서는 다 탐색을 했기 때문에, 해당 연산이 target이 나오는지를 확인하고, 해당하면 이 분기는 타켓 넘버를 계산할 수 있는 경우의 수중 하나가 되기 때문에 1을 반환하도록 할 것이다.

따라서 solution이 시작될 때는 vector가 비어있는지부터 확인하여(비어있다면 다 탐색했다는 의미이므로), 비어있으면 return하는 동작을 수행하도록 한다.

그렇지 않다면 vector의 마지막 요소를 따로 저장해둔뒤, 해당 요소를 삭제한다.

그리고 solution함수를 호출해서 마지막 요속 삭제된 vector를 넘겨주고, target에 마지막 요소를 더한 값을 target자리로 같이 넘겨준다. 반환된 값을 answer에 저장되도록 한다.

이를 빼기 연산에 대해서도 동일하게 수행한다.

target에 vector의 마지막 요소를 더하거나 뺌으로써 탐색을 마쳤을 때 최종 target값이 0이 되면 해당 분기는 하나의 경우의 수가 되는 방식으로 생각했다. (=수학을 잘하자..)

그러면 최종적으로 answer에는 모든 경로를 탐색하여 얻은 "타겟 넘버를 만드는 경우의 수"를 저장하게 될 것이다.

코드는 아래와 같다.

int solution(vector<int> numbers, int target) {
    if(numbers.empty()){
        if(target==0) return 1;
        else return 0;
    }
    
    int answer = 0;
    int top = numbers.back();
    numbers.pop_back();
    
    answer+=solution(numbers, target+top);
    answer+=solution(numbers, target-top);
    
    return answer;
}