프로그래밍

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

[난이도] level2
[유형] 구현

[풀이]
2차원 배열의 특정 부분을 회전하는 순수 구현 문제입니다.
저는 이런 문제에서 주로 배열보다는 복사가 쉬운 2차원 vector를 이용해
복사본 tmp를 만들어서 업데이트 해주는 방식으로 구현합니다.

#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
using vvi=vector<vector<int>>;
int N,M;
int rotate(int y1,int x1,int y2,int x2,vector<vector<int>>& map){
    int ret = 9e8;
    vvi tmp = map;

    for(int i=x1+1;i<=x2;i++) ret=min(ret,tmp[y1][i]=map[y1][i-1]);
    for(int i=y1+1;i<=y2;i++) ret=min(ret,tmp[i][x2]=map[i-1][x2]); 
    for(int i=x2-1;i>=x1;i--) ret=min(ret,tmp[y2][i]=map[y2][i+1]); 
    for(int i=y2-1;i>=y1;i--) ret=min(ret,tmp[i][x1]=map[i+1][x1]);
    map=tmp;
    return ret;
}
vector<int> solution(int rows, int columns, vector<vector<int>> queries) {
    vector<int> answer;
    N=rows;
    M=columns;
    vvi map(N+1,vector<int>(M+1));
    int k=0;
    for(int y=1;y<=N;y++)
        for(int x=1;x<=M;x++)
            map[y][x] = ++k;
    for(auto v : queries) answer.push_back(rotate(v[0],v[1],v[2],v[3],map));
    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/행렬 테두리 회전하기.cpp

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

[난이도] level2
[유형] 브루트포스

[풀이]
방 한개의 칸이 5x5이기 때문에 (0,0)~(4,4) 부터 모든 점을 확인해도 시간내에 충분히 해결이 가능합니다.
만약 현재 점 (y,x)가 사람이고 아래의 P점이라면

K
K K K
K K P M M
M M M
M

M으로된 표시된 곳에 사람이 있으면서 파티션으로 막혀있지 않은지만 확인해주면 됩니다.
K로 된 곳은 이미 이전에 점을 확인하면서 체크가 되었기 때문에 확인할 필요가 없습니다.

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


bool inRange(int y,int x){
    return (y<5 && x<5 && y>=0 && x>=0);
}

bool check(int y,int x,vector<string>& map){

    if(map[y][x]!='P') return true;

    if(inRange(y+1,x) && map[y+1][x]=='P') return false;

    if(inRange(y,x+1) && map[y][x+1]=='P') return false;

    if(inRange(y+2,x) && map[y+2][x]=='P' && map[y+1][x]!='X') return false;

    if(inRange(y,x+2) && map[y][x+2]=='P' && map[y][x+1]!='X') return false;


    if(inRange(y+1,x+1) && map[y+1][x+1]=='P'){
        if(map[y+1][x]!='X') return false;
        if(map[y][x+1]!='X') return false;
    }
    if(inRange(y+1,x-1) && map[y+1][x-1]=='P'){
        if(map[y][x-1]!='X') return false;
        if(map[y+1][x]!='X') return false;        
    }
    return true;
}

bool checkMap(vector<string>& map){
    for(int y=0;y<5;y++){
        for(int x=0;x<5;x++){
                if(!check(y,x,map)) {
                    return false;
                }
        }
    }
    return true;
}


vector<int> solution(vector<vector<string>> places) {
    vector<int> answer;
    for(int i=0;i<5;i++){
        bool ret = checkMap(places[i]);
        if(!ret) answer.push_back(0);
        else answer.push_back(1);
    }


    return answer;
}

https://github.com/has2/Problem-Solving/blob/master/programmers/level2/거리두기 확인하기.cpp

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

[난이도] Silver3
[유형] 백트래킹

[풀이]
이전 포스팅의 "N과 M (2)" 문제와 비슷하게 접근하면 되지만 다른 점이 같은 수를 여러번 선택할 수 있다는 점입니다.

재귀함수 내 n을 선택했을때의 호출 부분을 아래와 같이 변경해주면 됩니다.
used[n]++
sol(n,k+1)
used[n]--
n을 또 선택할 수 있으므로 n을 그대로 인자로 넘기고, used를 true false가 아닌 n이 몇개 쓰였는지를 체크하기 위해
호출시 used[n]++을 해주고 리턴시 used[n]--를 해줍니다.
수열을 출력시에는 used[n]의 값만큼 n을 출력해주면 됩니다.

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
var N=0
var M=0
var used = Array<Int>(9){0}
fun sol(n:Int,k:Int){
    if(k==M){
        for(i in 1..N){
            repeat(used[i]){
                print("$i ")
            }
        }
        println()
        return;
    }
    if(n>N) return;
    used[n]++
    sol(n,k+1)
    used[n]--
    sol(n+1,k)
}
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var ip = readLine().split(' ').map{it.toInt()}
    N=ip[0]
    M=ip[1]
    sol(1,0)
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver3/15652.cpp

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

[난이도] Silver3
[유형] 백트래킹

[풀이]
N이 8이하이기 때문에 재귀함수를 이용한 백트래킹으로 순서대로 수열을 출력할 수 있습니다.

재귀함수 sol(n,k)는 현재 n을 선택할 차례이며 지금까지 k개의 수를 선택했다는 의미입니다.

함수 내부에서 n을 선택한 경우와
used[n]=true
sol(n+1,k+1) : n을 선택했으므로 k를 1 증가시키고 used flag를 체크해줍니다.
used[n]=false

선택한 경우
sol(n+1,k) : 선택하지 않았으므로 k를 증가시키지 않습니다.

두가지로 나눠서 재귀호출을 해주어 k가 M인 경우 M개를 선택한 것이므로 used가 체크된 원소들을 출력하면
모든 수열을 순서대로 구할 수 있습니다.

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
var N=0
var M=0
var used = Array<Boolean>(9){false}
fun sol(n:Int,k:Int){
    if(k==M){
        for(i in 1..N){
            if(used[i]) print("$i ")
        }
        println()
        return;
    }
    if(n>N) return;
    used[n]=true
    sol(n+1,k+1)
    used[n]=false
    sol(n+1,k)
}
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var ip = readLine().split(' ').map{it.toInt()}
    N=ip[0]
    M=ip[1]
    sol(1,0)
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver3/15650.cpp

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

[난이도] Silver2
[유형] 힙

[풀이]
Heap

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val pq = PriorityQueue<Int>{a,b->b.compareTo(a)}
    var N = readLine().toInt()
    repeat(N){
        var v = readLine().toInt()
        when{
            v>0 -> pq.add(v)
            pq.isEmpty() -> println(0)
            else -> println(pq.poll())
        }
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver2/11279.cpp

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

[난이도] Silver2
[유형] 좌표압축

[풀이]
나올 수 있는 수자의 범위는 -10^9 ~ 10^9이지만 실제 숫자의 개수는 10^6 최대이므로
0~(10^6)-1 로 압축이 가능합니다.
정렬을 한 뒤, map을 이용하였습니다.
작은 수부터 순회하면서 숫자가 이미 map에 저장되어 있다면 이전 수와 동일한 수이므로
mp[a[i]] = k 로 저장해주고, map에 저장되어 있지 않다면 처음 등장하는 수이므로 mp[a[i]] = ++k와 같이
저장해줍니다.
그 뒤 정렬하지 않은 original 배열인 b를 순회하면서
mp[b[i]]를 출력하면 압축된 좌표로 출력이 됩니다.

#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
const int mxN = 1e6+1;
int n,a[mxN],b[mxN],k;
map<int,int> mp;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        b[i]=a[i];
    }
    sort(a,a+n);
    for(int i=0;i<n;i++) mp[a[i]]= mp.find(a[i])==mp.end() ? ++k : k;
    for(int i=0;i<n;i++) printf("%d ",mp[b[i]]-1);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver2/18870.cpp

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

[난이도] Silver5
[유형] DP

[풀이]
set a[3] 과 같이 선언하여
a[1]에는 1개의 제곱수로 만들 수 있는 숫자들,
a[2]에는 2개의 제곱수를 만들 수 있는 숫자들을 저장합니다.
set을 사용한 이유는 1^2+2^2, 2^2+1^2 등 중복되는 경우가 저장될 수 있기 때문입니다.
a[2]는 a[1]의 원소들로 2중 for문으로 구할 수 있으며
중간에 n과 동일한 수가 나오면 제곱수의 개수를 return 해줍니다.

a[1],a[2]를 구해놨으면 3개와 4개의 제곱수로 만들어진 n도 한번에 구할 수 있습니다.

3개로 만들 수 있는 제곱수는 모든 a[1]을 순회하면서 현재 나온 수가 v일때,
a[2]에 n-v가 있다면 제곱수 3개로 n을 만들 수 있다는 의미이므로 3을 return 해줍니다.

4일때도 마찬가지로
a[2]를 순회하면서 현재 나온 수가 v일때 a[2]에 n-v가 있다면 제곱수 4개로 n을 만들 수 있다는 의미이므로
4를 return 해주면 됩니다.

#include <cstdio>
#include <cmath>
#include <set>
using namespace std;
int n;
set<int> a[3];
int sol(){
    for(int i=1;i<=sqrt(n);i++){
        if(i*i==n) return 1;
        a[1].insert(i*i);
    }
    for(auto v1 : a[1]){
        for(auto v2 : a[1]){
            if(v1+v2==n) return 2;
            a[2].insert(v1+v2);
        }
    }    
    for(int i=1;i<3;i++){
        for(auto v : a[i]){
            if(a[2].find(n-v) != a[2].end()) return i+2;
        }
    }
    return 0;
}
int main(){
    scanf("%d",&n);
    printf("%d",sol());
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver5/17626.cpp

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

[난이도] Silver4
[유형] Map

[풀이]
Map

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*
fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    var (N,M) = readLine().split(' ').map{it.toInt()}
    val mp = HashMap<String,String>()
    repeat(N){
        var ip = readLine().split(' ')
        mp[ip[0]]=ip[1]
    }
    repeat(M){
        println(mp[readLine()])
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver4/17219.cpp