2022-05-13 알고리즘 문제 (300문제 달성 후기)

https://programmers.co.kr/learn/courses/30/lessons/49993

코딩테스트 연습 - 스킬트리

자바스크립트의 map 생성 map n = new Map(); , 값 넣기 n.set(ket,value), 

값 가져오기 n.get(key), 값이 없을 떄 undefined 

function solution(skill, skill_trees) {
    var answer = 0;
    var m = new Map();
    for(var i = 0;i<skill.length;i++){
        m.set(skill[i],i);
    }
    
    for(var i = 0;i<skill_trees.length;i++){
        var not_valid = false;
        var index = 0;
        for(var j = 0;j<skill_trees[i].length;j++){
            var find = m.get(skill_trees[i][j]);
            if(find != undefined){
                if(index != find){
                    not_valid = true;
                    break;
                }
                else{
                    index++;
                }
            }
           
        }
        if(not_valid == false){
            answer++;
        }
        
    }
    
    return answer;
}

---

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

범위 벗어날 떄 신경쓰기, #include <cstdio> 함수의 "%1d"를 사용하면 정수 하나씩 입력받을 수 있다.

#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#define MAX 26
using namespace std;
vector<int> v;
int map[MAX][MAX];
bool visited[MAX][MAX];
int n;
int dx[4] = {1,0,-1,0}; //오른쪽,밑,왼쪽,위
int dy[4] = {0,-1,0,1}; //오른쪽, 밑 ,왼쪽 ,위
int cnt = 0;
int depth = 0;
void dfs(int x,int y){
    if(visited[x][y]){
        return;
    }
    visited[x][y] = true;
 
    for(int i = 0;i<4;i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
         if(nx < 0 || ny < 0 || nx >= n || ny >= n){
                continue;
            }
 
        if(map[nx][ny] == 1 && visited[nx][ny] == false){ 
            dfs(nx,ny);
            depth++;
        }
    }
}
int main(void){
    cin >> n;
 
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            scanf("%1d",&map[i][j]);
        }
    }
 
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            if(map[i][j] == 1 && visited[i][j] == false){
                dfs(i,j);
                cnt++;
                v.push_back(depth);
                depth = 0;
 
            }
        }
    }
    cout << cnt << '\n';
    sort(v.begin(),v.end());
    for(int i = 0;i<v.size();i++){
        cout << v[i]+1 << '\n';
    }
}

---

https://www.acmicpc.net/problem/6603

6603번: 로또

#include <iostream>
#include <algorithm>
#define MAX 14
using namespace std;
int n;
bool visited[MAX];
int arr[MAX];
int A[MAX];
void init(){
    for(int i = 0;i<=n;i++){
        arr[i] = 0;
        A[i] = 0;
        visited[i] = false;
    }
}

void dfs(int start){
    if(start == 6){
        bool valid = false;
            for(int i = 0;i<6;i++){
                if(arr[i-1] > arr[i]){
                    valid = true;
                    break;
                }
            }
        if(valid == false){
            for(int i = 0;i<6;i++){
                cout << arr[i] << ' ';
            }
            cout << '\n';
        }
        
     
        return;
    }
    for(int i = 0;i<n;i++){
        if(visited[i] == false){
            visited[i] = true;
            arr[start] = A[i];
            dfs(start+1);
            visited[i] = false;
        }
    }
}
int main(void){
    while(1){
        cin >> n;
        if(n == 0){
            break;
        }
        init();
        for(int i = 0;i<n;i++){
            cin >> A[i];
        }
        sort(A,A+n);
        dfs(0);
        cout << '\n';
    }
}

---

300문제 달성

올해까지 기본적인 알고리즘(특히 그래프 탐색)을 모두 익히고,

자바스크립트로 알고리즘을 많이 풀 생각이다. 이번년도까지 400문제를 찍고싶다.