[코드트리 챌린지] 6주차, 바쁘다 바빠 현대사회.

 

진단평가, DP를 뚫어버렸다.

챌린지 시작 약 한달차, 드디어 유?의미한 점수의 상승이 생겼다.

이번 주에 조금 열심히 살긴 했는데 그 노력을 보상 받는거 같아서 기분이 좋지만

더 높은 점수를 내지 못한게 아쉽기도 하다.

이대로만 가면... 라이더

---

INTERMEDIATE LOW - 알고리즘 입문

지난주차에 시작한 단계, 슬슬 끝이 보인다.

Simulation은 시간을 많이 잡았지만 의외로 Backtracking/DFS/BFS는 문제들이 대부분 손 쉽게 풀렸다.

재미도 있어서 이번 주에는 꽤 많은 학습을 했던 것 같다.

오늘 바빠서 미처 학습을 못 한 걸 감안한다면... 꽤나 열심히 했다고 생각한다.

아마 다음주에는 INTERMEDIATE MID에 진입할 것 같다!

빠르게 학습 끝내고 알고리즘 다 부수고 다녀야지

---

이번 주 기억에 남는 문제

XOR 결과 최대 만들기 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

BackTracking 이라 풀이 자체는 어려운 문제는 아니었는데, XOR을 어떻게 해야하나 순간 고민했던 문제였다.

평소 OR이랑 AND는 자주 쓰지만 XOR은 잘 안쓰다보니 잊고 살았다.

잊지 말자는 의미에서 포스팅으로 남긴다. XOR을 하는 방법은 A^B 이다!

 

주사위 던지기 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

#include <iostream>
#include <deque>
#include <map>
using namespace std;

int n, m, r, c;
int board[101][101] = {0, };
int dice[3][3] = 
{
    {0, 5, 0},
    {4, 6, 3},
    {0, 2, 0}
};

int arr[101][101] = {0, };

map<char, int> dir = 
{
    {'L', 0},
    {'R', 1},
    {'U', 2},
    {'D', 3}
};

int dy[4] = {0, 0, -1, 1};
int dx[4] = {-1, 1, 0, 0};

void rollDice(int d)
{
    int y1 = 1 + (-1*dy[d]), y2 = 1, y3 = 1 + (1*dy[d]);
    int x1 = 1 + (-1*dx[d]), x2 = 1, x3 = 1 + (1*dx[d]);

    int tmp = dice[y2][x2];
    dice[y2][x2] = dice[y3][x3];
    dice[y1][x1] = tmp;
    dice[y3][x3] = 7 - tmp;

}


void solve()
{
    int y = r;
    int x = c;
    board[y][x] = dice[1][1];

    char turn;

    for(int i=0; i<m; i++)
    {
        cin >> turn;

        int d = dir[turn];

        y = y+dy[d];
        x = x+dx[d];

        if((y < 1 || y > n) || (x < 1 || x > n))
        {
            y -= dy[d];
            x -= dx[d];
            continue;
        }

        rollDice(d);
        board[y][x] = dice[1][1];
    }

    int answer = 0;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            answer += board[i][j];
        }
    }

    cout << answer;

}

void init()
{
    cin >> n >> m >> r >> c;
    solve();
}
int main() {
    init();
    // 여기에 코드를 작성해주세요.
    return 0;
}

Simulation에서 주사위를 굴리는 문제였다.

아무래도 굴리는 방향에 따라서 계속해서 수의 위치가 바뀌다 보니 이거를 어떻게 해 줘야하나 엄청 고민했었다.

3X3 배열에 윗쪽 면을 제외한 수들을 저장해주고 굴러가는 방향에 따라 값을 바꿔주면 쉽게 해결되는 문제였다.

늘 그렇듯 발상하는게 가장 어렵다. 그리고 반례찾기...

 

사각형 채우기 3

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

엊그제부터 DP풀이에 들어갔는데 풀다가 첫 번째로 막힌 문제였다.

점화식을 아무리 생각나는데로 작성을 해 봐도 뭔가 수가 조금씩 엇나가서 결국 해설을 봤던 문제인데

이 경우에는 누적합을 따로 관리하고 그걸 사용하는 누적합 DP문제였다.

n이 일정 이상 될 때부터 생기는 유니크 케이스를 생각해줘야한다는걸 알게 된 문제였다.

---

이번 주 소회

벌써 이 블로그 챌린지도 끝이 얼마 안 남은게 느껴진다.

끝나고 꾸준히 쓸 수 있다면 좋을텐데 어떻게 될 지는 모르겠다.

좀 더 알고리즘을 열심히 풀고 싶은데 이번주는 워낙 공사다망하여 정신이 없다.

포트폴리오도 작성하랴 이거하랴 저거하랴 그래도 열심히 해야지

 

흑흑 공사 다 망해