그냥 코딩하는 사람의 블로그

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

풀이 과정

1. 입력된 뉴런 a와 b가 같은 집합 내에 속해있는지 검사한다.
   1. 같은 집합 내에 속해있지 않다면 Union
   2. 같은 집합 내에 속해있다면 해당 뉴런은 끊어내야 하는 뉴런이므로 연산 횟수를 하나 증가시킨다.
2. 모든 뉴런들에 대해 같은 집합에 속해있는지 검사한다.
   1. 다른 집합에 속해있다면, 두 집합을 Union 해주고 연산 횟수를 하나 증가시킨다.
3. 연산 횟수를 출력시켜준다.

소스 코드

import sys

sys.setrecursionlimit(10**6)

input = lambda: sys.stdin.readline().rstrip()
N, M = map(int, input().split())

parent = [i for i in range(N+1)]

def find(parent, a):
    if parent[a] != a:
        parent[a] = find(parent, parent[a])
        
    return parent[a]

def union(parent, a, b):
    p1 = find(parent, a)
    p2 = find(parent, b)
    if p1 != p2:
        parent[p1] = p2

answer = 0

for _ in range(M):
    a, b = map(int, input().split())
    if find(parent, a) != find(parent, b):
        union(parent, a, b)
    else:
        answer += 1

parent_node = find(parent, 1)
idx = 1
for i in range(2, N+1):
    if find(parent, i) != parent_node:
        union(parent, i, idx)
        parent_node = find(parent, i)
        idx = i
        answer += 1

print(answer)

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

풀이 과정

1. 원형으로 연결되어 있으므로 첫번째 스티커를 선택하는지 선택하지 않는지에 따라 달라진다.
   1. 첫번째 스티커를 선택하는 경우, 마지막 스티커는 선택하지 않아야 함
   2. 첫번째 스티커를 선택하지 않는 경우, 마지막 스티커를 선택할 수도 있음
2. 첫번째를 선택하거나 선택하지 않은 각각의 경우에 따라 dp테이블을 구성해 준다.
3. 점화식은 다음과 같다.
   1. DP[i][0] = max(DP[i-1][0], DP[i-1][1])
   2. DP[i][1] = DP[i-1][0] + i번째 스티커
4. 첫번째 스티커를 선택한 경우는 마지막 스티커를 선택할 수 없으므로 DP[n-2]에서의 최댓값을, 첫번째 스티커를 선택하지 않은 경우는 마지막 스티커를 선택 가능하므로 DP[n-1]에서의 최댓값을 구해주면 된다.

소스 코드

def solution(sticker):
    answer = 0
    dp = [[0] * 2 for _ in range(len(sticker))]
    
    if len(sticker) == 1:
        return sticker[0]
    
    # 첫번째 선택
    dp[0][0], dp[0][1] = 0, sticker[0]
    dp[1][0], dp[1][1] = sticker[0], 0
    for i in range(2, len(sticker)):
        dp[i][0] = max(dp[i-1][0], dp[i-1][1])
        dp[i][1] = dp[i-1][0] + sticker[i]
    answer = max(answer, max(dp[len(sticker)-2]))
    
    # 첫번째 선택하지 않은 경우
    dp[0][0], dp[0][1] = 0, 0
    dp[1][0], dp[1][1] = 0, sticker[1]
    for i in range(2, len(sticker)):
        dp[i][0] = max(dp[i-1][0], dp[i-1][1])
        dp[i][1] = dp[i-1][0] + sticker[i]
    answer = max(answer, max(dp[len(sticker)-1]))
    
    return answer

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

풀이 과정

1. 4방향 모두 이동가능 하다면 DP로 풀이할 수 없지만 문제에서 오른쪽과 아래로만 이동 가능하다고 하였으므로 DP로 풀이 가능
2. 좌회전 / 우회전 금지가 없는 경우의 DP 점화식은 다음과 같다.
   1. DP[i][j] = DP[i][j-1] + DP[i-1][j]
3. 좌회전 / 우회전 금지가 존재하므로 해당 부분은 따로 처리해주어야 한다.
   1. 연속적으로 푯말이 있는 경우가 있으므로 해당 경우는 따로 처리해주어야 한다. 
   2. [i][j-1]에 금지 푯말이 있는 경우는 금지 푯말이 없을때까지 왼쪽으로 올라가보아야 함
   3. [i-1][j]에 금지 푯말이 있는 경우는 금지 푯말이 없을때까지 위로 올라가보아야 함
4. 경우의 수가 커질수도 있으므로 매순간 값을 구해준 다음 20170805의 나머지를 구해준다.
5. dp[m-1][n-1]을 리턴시켜 준다.

소스 코드

class Solution {
    int MOD = 20170805;

    public void calculateRowCell(int i, int j, int[][] cityMap, int[][] dp) {
        if (cityMap[i-1][j] == 2) {
            int dest = i-2;
            while (dest >= 0 && cityMap[dest][j] == 2)
                dest -= 1;
            if (dest >= 0)
                dp[i][j] += dp[dest][j];

        } else {
            dp[i][j] += dp[i-1][j];
        }
    }

    public void calculateColCell(int i, int j, int[][] cityMap, int[][] dp) {
        if (cityMap[i][j-1] == 2) {
            int dest = j-2;
            while (dest >= 0 && cityMap[i][dest] == 2)
                dest -= 1;
            if (dest >= 0)
                dp[i][j] += dp[i][dest];
        } else {
            dp[i][j] += dp[i][j - 1];
        }
    }

    public int solution(int m, int n, int[][] cityMap) {
        int answer = 0;
        int dp[][] = new int[m][n];
        dp[0][0] = 1;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (cityMap[i][j] == 1)
                    continue;
                if (i-1 >= 0) {
                    calculateRowCell(i, j, cityMap, dp);
                }
                if (j-1 >= 0) {
                    calculateColCell(i, j, cityMap, dp);
                }
                dp[i][j] %= MOD;
            }
        }
        answer = dp[m-1][n-1];
        return answer;
    }
}

https://github.com/nbalance97/java-vendingmachine-precourse

개발 과정

1. 이번 과제도 마찬가지로 기능 사항 작성부터 진행
2. 기능 사항 작성 이후 기능별 함수 작성 및 커밋

후기

1. 이번에는 기능이 좀 많아지면서 클래스가 너무 많아지게 된 문제가 있었다. 따라서 좀 구조화시키기 위해 MVC패턴을 도입하여 프로젝트를 진행하였다.
2. 코드의 가독성을 높이기 위해 노력함.
   1. 에러 메세지나 숫자 리터럴(매직 넘버)을 상수로 선언하여 사용하려고 노력함

      

   2. 입력 클래스와 출력 클래스, 처리 클래스를 따로 두어서 진행함.
      • 기존 코드에서는 클래스 내에 출력하는 부분까지 모두 두었는데 출력하는 클래스를 따로 구성하여 단일 책임 원칙을 만족시키려고 노력함
   3. 검증 클래스를 따로 두어서 진행함
      • 입력 데이터 검증 시 검증 클래스(Validators) 내에서 처리하도록 구현

3주간의 프리코스가 드디어 끝났다.. 많은 우여곡절이 있었지만 스스로 학습하면서 다른 사람이 읽기 좋은 코드를 구현하려고 많이 노력한 것 같다. 비록 최종테스트에서는 개인적으로 부족하여 바로바로 구현내용이 떠오르지 않기도 하고 시간이 부족하기도 하여 전부 완성하지는 못했으나 코드를 작성할 때 계속해서 고민해보는 습관을 들이게 되는 등 스스로 많이 성장하게 된 계기가 된 것 같다. 

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

풀이 과정

1. Tree를 먼저 중위순회 해보고 마지막에 방문하는 정점이 어디인지 파악한다.
2. 전체 간선의 개수의 두배에서 마지막에 방문하는 정점을 방문하기 위해 지나온 간선의 개수를 빼주어서 출력

소스 코드

import sys

sys.setrecursionlimit(10**6)

input = lambda: sys.stdin.readline().rstrip()
left = dict()
right = dict()

N = int(input())
parent = [0] * (N+1)
node_count = 0
for _ in range(N):
    a, b, c = map(int, input().split())
    left[a] = b
    right[a] = c

    if b != -1:
        parent[b] = a
        node_count += 1
    if c != -1:
        parent[c] = a
        node_count += 1

# 마지막 노드 구하는 파트
last_node = 0
def traverse(node):
    global last_node
    if node == -1:
        return
    traverse(left[node])
    last_node = node
    traverse(right[node])

traverse(1)
edge_count = node_count * 2
movement = 0
# 마지막 노드까지 이동 경로의 거리 구함
while last_node != 1:
    movement += 1
    last_node = parent[last_node]
print(edge_count - movement)

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

풀이 과정

Python을 사용할 수 없어 Java로 풀이함!!

1. 주어진 data을 각각 인원1, 인원2, 연산, 거리 형식의 Op 클래스로 치환한다.
2. Op 클래스에서는 거리가 주어졌을 때, 연산 결과가 반환되는 operate 메소드를 만들어 둔다.
3. 최대 인원수가 8명이므로 가능한 모든 순열을 Recursion으로 만들어 준다.
   
   1. Set 자료구조로는 현재 순열에 어떤 인원이 포함되어 있는지 체크
   2. Map 자료구조로는 현재 인원의 위치를 저장
   3. 이후 Op 클래스의 operate 메소드를 호출할 때 Map 자료구조를 넘겨줌으로써 빠르게 거리계산이 가능하도록 한다.
4. 각각의 순열에 대해서 모든 Op클래스의 operate 메소드가 True가 나온다면 카운팅 해주고, 하나라도 False가 나온다면 카운팅 해주지 않는다.
5. 카운팅 개수를 리턴해주면 끝

소스 코드

import java.util.HashSet;
import java.util.HashMap;
import java.util.Arrays;

class Op{
    private char from;
    private char to;
    private char operation;
    private int dist;

    public Op(String data) {
        this.from = data.charAt(0);
        this.to = data.charAt(2);
        this.operation = data.charAt(3);
        this.dist = data.charAt(4) - '0';
    }
    
    public void print() {
         System.out.println(this.from + "//" + this.to);
    }

    public boolean execute(HashMap<Character, Integer> pos) {
        int distance = Math.abs(pos.get(from) - pos.get(to)) - 1;
        if (operation == '=') {
            return distance == dist;
        }
        if (operation == '>') {
            return distance > dist;
        }
        if (operation == '<') {
            return distance < dist;
        }
        return false;
    }
}

class Solution {
    private HashMap<Character, Integer> characterPos = new HashMap<>();
    private HashSet<Character> character = new HashSet<>();
    private static final Character[] CHARACTER = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
    private int caseCount = 0;
    private Op[] operations;

    public void solve(int index) {
        if (index == 9) {
            if (check(characterPos)) {
                caseCount++;
            }
            return;
        }

        for (int i = 0; i < CHARACTER.length; i++) {
            if (!character.contains(CHARACTER[i])) {
                character.add(CHARACTER[i]);
                characterPos.put(CHARACTER[i], index);
                solve(index + 1);
                character.remove(CHARACTER[i]);
            }
        }
    }

    public boolean check(HashMap<Character, Integer> pos) {
        for (Op operation : operations) {
            if (!operation.execute(pos)) {
                return false;
            }
        }
        return true;
    }

    public int solution(int n, String[] data) {
        operations = Arrays.stream(data)
                .map(op -> new Op(op))
                .toArray(size -> new Op[size]);
        solve(1);
        return caseCount;
    }
}

https://github.com/nbalance97/java-racingcar-precourse

이번 과제에서는 함수화하는 점, Car 클래스를 이용하는 점, 그리고 저번 과제에서 부족했던 함수명과 변수명을 최대한 잘 짓는 점을 중점으로 과제를 구현하였음.

1. 함수화 하기

- 함수를 최소화하기 위해 각 함수 내에서 부분 함수들을 만들어서 처리하도록 구현하였음.

- 최종 함수에서는 부분 함수의 결괏값으로 처리

2. Car 클래스 이용하기

- 이동시키는 기능은 Car 클래스 내부에서 처리할 수 있을 것이라 생각하여 Car 클래스에서 처리하도록 구현

3. 함수명과 변수명을 최대한 잘 짓기

- 각각의 함수가 어떤 기능을 사용하는지, 각 변수가 어떤걸 의미하는지 파악하기 쉽도록 함수, 변수이름 작성

아쉬웠던 점

1. 함수 15줄 이내로 구현하기

- 최대한 15줄 이내로 함수를 작성하려고 하였으나 승자를 구하는 부분은 15줄 이내로 구현하기가 어려웠던 문제가 있음. 이 점은 추후에 학습하여 보니 배열로 작성하려고 해서 그런거고, Collection을 사용하였더라면 비교적 짧게 작성할 수 있었을 것.

2. 매직 넘버를 사용함

- 상수를 따로 선언하여서 사용하여야 했는데, 매직 넘버를 그대로 사용하여서 가독성이 좋지 않은 문제점이 있었다.

3. 클래스 분할을 하지 않음..

- 출력 클래스, 입력 클래스, 처리 클래스를 따로 나누었으면 더 좋았을 것 같음.

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

풀이 과정

1. 경우의 수가 너무 많아질 수 있으므로 탐색으로 구하는 문제는 아닌것 같아 DP로 풀이
2. DP로 풀이하기 위해 점화식을 도출한다.
   1. DP[i][j][0] = sum(DP[v][j-1][1] , 0<= v < i)
   2. DP[i][j][1] = sum(DP[v][j-1][0] , 0<= v < i)
   3. 여기서, DP[i][j][k]에서 i가 의미하는것은 현재 위치, j가 의미하는것은 현재 문자열이 두루마리의 몇번째에 적힌 문자열인지, k가 의미하는 것은 0일땐 악마의 돌다리, 1일땐 천사의 돌다리이다.
3. 점화식을 이용하여 전체 경우의 수를 구한 전체 DP테이블에서 두루마리의 마지막 문자까지 간 경우의 수들만 더해주면 된다.

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()
target = input()
s1 = input()
s2 = input()

dp = [[[0] * 2 for _ in range(len(target))] for _ in range(len(s1))]

for i in range(len(s1)):
    if s1[i] == target[0]:
        dp[i][0][0] = 1
    if s2[i] == target[0]:
        dp[i][0][1] = 1

for i in range(len(s1)):
    for j in range(1, len(target)):
        if s1[i] == target[j]:
            for k in range(i):
                dp[i][j][0] += dp[k][j-1][1]

        if s2[i] == target[j]:
            for k in range(i):
                dp[i][j][1] += dp[k][j-1][0]

answer = 0
for i in range(len(s1)):
    answer += (dp[i][len(target)-1][0] + dp[i][len(target)-1][1])

print(answer)

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

풀이 과정

1. 전체적인 점화식은 다음과 같다. 
   • dp[i][j] = dp[i-1][j] + dp[i-2][j-1]
   • dp[i][j]는 j번 칠했을 때 i번 위치에서의 경우의 수이다.
   • 설명하자면, dp[i-1][j]->dp[i][j]는 i에서 칠하지 않는 경우의 수이고 dp[i-2][j-1]은 i에서 칠하는 경우의 수이다.
2. DP를 두번 진행한다. 한번은 맨 첫번째 색상환을 칠하는 경우, 다른 한번은 첫번째 색상환을 칠하지 않는 경우이다. 이 때 주의해야 할 점은 첫번째 색상환을 칠하는 여부에 따라 dp 테이블 초기화 방식이 다르다는 점이다. 이 점 때문에 시간 많이 잡아먹음..ㅋㅋ
3. 맨 첫번째 색상환을 칠하는 경우에는 마지막 색상환을 칠해선 안되므로 dp[N-1][K]
4. 맨 첫번째 색상환을 칠하지 않는 경우는 마지막 색상환을 칠할 수 있으므로 dp[N][K]
5. 두 합을 구해서 출력시켜준다.

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()

N = int(input())
K = int(input())

answer = 0
selected = True

div = 1000000003
for i in range(2):
    dp = [[0] * (K+1) for _ in range(N+1)]
    for i in range(1, N+1):
        if not selected:
            dp[i][1] = i-1
            dp[i][0] = 1
        else:
            dp[i][1] = 1
            dp[i][0] = 0

    for i in range(2, N+1):
        for j in range(2, K+1):
            dp[i][j] += dp[i-1][j]
            if i >= 2 and j >= 1:
                dp[i][j] += dp[i-2][j-1]

            dp[i][j] %= div

    if selected:
        answer += dp[N-1][K]
    else:
        answer += dp[N][K]
        
    answer %= div
    selected = not selected
    
print(answer)

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

그냥 풀기 너무 어려워서 백준 내 질문게시판을 참조함..

풀이 과정

1. 출구가 한곳이 아니므로 전체 테두리를 .으로 감싸서 외부에서 시작할 때는 [0, 0]에서 시작할 수 있도록 한다.
2. 총 3번의 BFS를 진행하여야 한다.
   1. 1번 죄수 기준으로 BFS를 진행하여 전체 지점에서 부숴야 하는 최소 벽 개수를 구한다.
   2. 2번 죄수 기준으로 BFS를 진행하여 전체 지점에서 부숴야 하는 최소 벽 개수를 구한다.
   3. 외부 조력자 기준([0, 0])으로 BFS를 진행하여 전체 지점에서 부숴야 하는 최소 벽 개수를 구한다.
3. 전체 좌표에 대해서, 1번 죄수가 부숴야하는 벽, 2번 죄수가 부숴야하는 벽, 외부 조력자가 부숴야 하는 벽의 수를 모두 합한 값이 최소일 때의 값을 출력한다.
   • 단, 이 때 현 좌표가 벽인 경우는 1~3번이 모두 부수므로 2를 빼준다.

소스 코드

import sys
from collections import deque as Deque

input = lambda: sys.stdin.readline().rstrip()
T = int(input())

def bfs(matrix, x, y):
    new_matrix = [[int(10e9)] * len(matrix[0]) for _ in range(len(matrix))]
    deque = Deque([[x, y]])
    dx, dy = [-1, 1, 0, 0], [0, 0, 1, -1]
    R, C = len(matrix), len(matrix[0])
    visited = [[False] * C for _ in range(R)]
    visited[x][y] = True
    new_matrix[x][y] = 0
    while deque:
        cx, cy = deque.popleft()
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]
            if 0 <= nx and nx < R and 0 <= ny and ny < C:
                if not visited[nx][ny] and matrix[nx][ny] == '.':
                    new_matrix[nx][ny] = new_matrix[cx][cy]
                    deque.appendleft([nx, ny])
                elif not visited[nx][ny] and matrix[nx][ny] == '#':
                    new_matrix[nx][ny] = new_matrix[cx][cy]+1
                    deque.append([nx, ny])
                visited[nx][ny] = True
    return new_matrix

for _ in range(T):
    h, w = map(int, input().split())
    matrix = [list('.'+input()+'.') for _ in range(h)]
    matrix = [['.'] * (w+2)] + matrix + [['.'] * (w+2)]
    player = []
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if matrix[i][j] == '$':
                player.append([i, j])
                matrix[i][j] = '.'
                
    playerA, playerB = player[0], player[1]
    matrix1 = bfs(matrix, 0, 0)
    matrix2 = bfs(matrix, playerA[0], playerA[1])
    matrix3 = bfs(matrix, playerB[0], playerB[1])

    answer = int(10e9)
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if matrix[i][j] == '*':
                continue
            sumation = matrix1[i][j] + matrix2[i][j] + matrix3[i][j]
            if matrix[i][j] == '#':
                answer = min(answer, sumation-2)
            else:
                answer = min(answer, sumation)

    print(answer)