Feel Coding

단계별로 풀어보기 재귀의 2단계 문제

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 2) + fibonacci(n - 1)
n = int(input())
print(fibonacci(n))

단계별로 풀어보기 재귀의 1단계 문제

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)
n = int(input())
print(factorial(n))

단계별로 풀어보기 DFS와 BFS 9단계 문제

이렇게 짰는데

from sys import stdin
n, m = list(map(int, stdin.readline().split()))
li = []
for i in range(n):
    li.append(stdin.readline())
import collections
q = collections.deque()
q.append((0, 0, 1, False))
visited = [[False] * m for i in range(n)]
flag = False

while q:
    cur = q.popleft()
    if cur[0] == n - 1 and cur[1] == m - 1:
        print(cur[2])
        flag = True
        break
    if not visited[cur[0]][cur[1]]:
        visited[cur[0]][cur[1]] = True
    else:
        continue
    if cur[0] - 1 >= 0 and li[cur[0] - 1][cur[1]] == '0' and not visited[cur[0] - 1][cur[1]]:
        q.append((cur[0] - 1, cur[1], cur[2] + 1, cur[3]))
    if cur[0] + 1 < n and li[cur[0] + 1][cur[1]] == '0' and not visited[cur[0] + 1][cur[1]]:
        q.append((cur[0] + 1, cur[1], cur[2] + 1, cur[3]))
    if cur[1] - 1 >= 0 and li[cur[0]][cur[1] - 1] == '0' and not visited[cur[0]][cur[1] - 1]:
        q.append((cur[0], cur[1] - 1, cur[2] + 1, cur[3]))
    if cur[1] + 1 < m and li[cur[0]][cur[1] + 1] == '0' and not visited[cur[0]][cur[1] + 1]:
        q.append((cur[0], cur[1] + 1, cur[2] + 1, cur[3]))
    if not cur[3] and cur[0] - 1 >= 0 and li[cur[0] - 1][cur[1]] == '1':
        q.append((cur[0] - 1, cur[1], cur[2] + 1, True))
    if not cur[3] and cur[0] + 1 < n and li[cur[0] + 1][cur[1]] == '1':
        q.append((cur[0] + 1, cur[1], cur[2] + 1, True))
    if not cur[3] and cur[1] - 1 >= 0 and li[cur[0]][cur[1] - 1] == '1':
        q.append((cur[0], cur[1] - 1, cur[2] + 1, True))
    if not cur[3] and cur[1] + 1 < m and li[cur[0]][cur[1] + 1] == '1':
        q.append((cur[0], cur[1] + 1, cur[2] + 1, True))
if not flag:
    print(-1)

틀렸다고 한다.

단계별로 풀어보기 DFS와 BFS의 8단계 문제

최솟값을 구하는 것이므로 BFS로 풀었다. 30분 정도 걸렸다.

from sys import stdin
n, k = list(map(int, stdin.readline().split()))
import collections
q = collections.deque()
q.append((n, 0))
visited = [False] * (max(n, k) + 2)
while q:
    cur = q.popleft()
    if cur[0] == k:
        print(cur[1])
        break
    if not visited[cur[0]]:
        visited[cur[0]] = True
    else:
        continue
    if cur[0] + 1 < (max(n, k) + 2) and not visited[cur[0] + 1]:
        q.append((cur[0] + 1, cur[1] + 1))
    if cur[0] - 1 >= 0 and  not visited[cur[0] - 1]:
        q.append((cur[0] - 1, cur[1] + 1))
    if 2 * cur[0] < (max(n, k) + 2) and not visited[2 * cur[0]]:
        q.append((2 * cur[0], cur[1] + 1))

23일 뒤에 C++로 다시 풀어봤다.

#include <iostream>
#include <tuple>
#include <queue>
#include <vector>
using namespace std;


int main() {
	int n, k;
	cin >> n >> k;
	queue<pair<int, int>> q;
	q.push(make_pair(n, 0));
	vector<bool> visited(100001);
	while (!q.empty()) {
		pair<int, int> cur = q.front();
		q.pop();
		if (cur.first == k) {
			cout << cur.second;
			break;
		}
		visited[cur.first] = true;
		if(cur.first - 1 >= 0 && !visited[cur.first - 1])
			q.push(make_pair(cur.first - 1, cur.second + 1));
		if(cur.first + 1 <= 100000 && !visited[cur.first + 1])
			q.push(make_pair(cur.first + 1, cur.second + 1));
		if(cur.first * 2 <= 100000 && !visited[cur.first * 2])
			q.push(make_pair(cur.first * 2, cur.second + 1));
	}
	return 0;
}

단계별로 풀어보기 DFS와  BFS의 7단계 문제

5단계 문제인 7576번 문제의 3차원 버전이다. 따라서 위, 아래만 더 검사하면 된다. 앞, 뒤, 오른쪽, 왼쪽은 2차원일 때에도 검사했으니까.

from sys import stdin
m, n, h = list(map(int, stdin.readline().split()))
matrix = []
for i in range(h):
    matrix.append([])
count = 0
minus = 0
zero = 0
import collections
q = collections.deque()
one = []
for i in range(h):
    for j in range(n):
        temp = list(map(int, stdin.readline().split()))
        matrix[i].append(temp)
        count += temp.count(1)
        minus += temp.count(-1)
        zero += temp.count(0)
        for k in range(m):
            if temp[k] == 1:
                q.append((i, j, k, 0))
if zero == 0:
    print(0)
else:
    ripen = 0
    result = 0
    visited = [[[False] * m for j in range(n)] for i in range(h)]
    while q:
        cur = q.popleft()
        if not visited[cur[0]][cur[1]][cur[2]]:
            visited[cur[0]][cur[1]][cur[2]] = True
            matrix[cur[0]][cur[1]][cur[2]] = 1
            ripen += 1
            result = cur[3]
        else:
            continue
        if cur[0] + 1 < h and matrix[cur[0] + 1][cur[1]][cur[2]] == 0 and not visited[cur[0] + 1][cur[1]][cur[2]]:
            q.append((cur[0] + 1, cur[1], cur[2], cur[3] + 1))
        if cur[1] + 1 < n and matrix[cur[0]][cur[1] + 1][cur[2]] == 0 and not visited[cur[0]][cur[1] + 1][cur[2]]:
            q.append((cur[0], cur[1] + 1, cur[2], cur[3] + 1))
        if cur[0] - 1 >= 0 and matrix[cur[0] - 1][cur[1]][cur[2]] == 0 and not visited[cur[0] - 1][cur[1]][cur[2]]:
            q.append((cur[0] - 1, cur[1], cur[2], cur[3] + 1))
        if cur[1] - 1 >= 0 and matrix[cur[0]][cur[1] - 1][cur[2]] == 0 and not visited[cur[0]][cur[1] - 1][cur[2]]:
            q.append((cur[0], cur[1] - 1, cur[2], cur[3] + 1))
        if cur[2] + 1 < m and matrix[cur[0]][cur[1]][cur[2] + 1] == 0 and not visited[cur[0]][cur[1]][cur[2] + 1]:
            q.append((cur[0], cur[1], cur[2] + 1, cur[3] + 1))
        if cur[2] - 1 >= 0 and matrix[cur[0]][cur[1]][cur[2] - 1] == 0 and not visited[cur[0]][cur[1]][cur[2] - 1]:
            q.append((cur[0], cur[1], cur[2] - 1, cur[3] + 1))
    if ripen == m * n * h - minus:
        print(result)
    else:
        print(-1)

단계별로 풀어보기 DFS와 BFS의 6단계 문제

한 시간 정도 걸렸던 것 같다.

최솟값을 구하는 거니까 BFS를 이용했다.

from sys import stdin
m, n = list(map(int, stdin.readline().split()))
matrix = []
count = 0
minus = 0
zero = 0
import collections
q = collections.deque()
one = []
for i in range(n):
    temp = list(map(int, stdin.readline().split()))
    matrix.append(temp)
    count += temp.count(1)
    minus += temp.count(-1)
    zero += temp.count(0)
    for j in range(m):
        if temp[j] == 1:
            q.append((i, j, 0))
if zero == 0:
    print(0)
else:
    ripen = 0
    result = 0
    visited = [[False] * m for i in range(n)]
    while q:
        cur = q.popleft()
        if not visited[cur[0]][cur[1]]:
            visited[cur[0]][cur[1]] = True
            matrix[cur[0]][cur[1]] = 1
            ripen += 1
            result = cur[2]
        else:
            continue
        if cur[0] + 1 < n and matrix[cur[0] + 1][cur[1]] == 0 and not visited[cur[0] + 1][cur[1]]:
            q.append((cur[0] + 1, cur[1], cur[2] + 1))
        if cur[1] + 1 < m and matrix[cur[0]][cur[1] + 1] == 0 and not visited[cur[0]][cur[1] + 1]:
            q.append((cur[0], cur[1] + 1, cur[2] + 1))
        if cur[0] - 1 >= 0 and matrix[cur[0] - 1][cur[1]] == 0 and not visited[cur[0] - 1][cur[1]]:
            q.append((cur[0] - 1, cur[1], cur[2] + 1))
        if cur[1] - 1 >= 0 and matrix[cur[0]][cur[1] - 1] == 0 and not visited[cur[0]][cur[1] - 1]:
            q.append((cur[0], cur[1] - 1, cur[2] + 1))
    if ripen == m * n - minus:
        print(result)
    else:
        print(-1)

단계별로 풀어보기 DFS와 BFS의 5단계 문제

BFS로 풀면 된다.

큐에 (row, col, depth)를 집어넣는다. (row, col)은 방문한 위치, depth는 (1, 1)부터 몇 칸 거쳐서 왔는지 정보이다.

from sys import stdin
import collections
n, m = list(map(int, stdin.readline().split()))
matrix = []
for i in range(n):
    matrix.append(stdin.readline())
q = collections.deque()
q.append((0, 0, 1))
visited = [[False] * m for i in range(n)]
while q:
    cur = q.popleft()
    if not visited[cur[0]][cur[1]]:
        visited[cur[0]][cur[1]] = True
        if cur[0] == n - 1 and cur[1] == m - 1:
            print(cur[2])
            break
    else:
        continue
    if cur[0] + 1 < n and matrix[cur[0] + 1][cur[1]] == "1" and not visited[cur[0] + 1][cur[1]]:
        q.append((cur[0] + 1, cur[1], cur[2] + 1))
    if cur[1] + 1 < m and matrix[cur[0]][cur[1] + 1] == "1" and not visited[cur[0]][cur[1] + 1]:
        q.append((cur[0], cur[1] + 1, cur[2] + 1))
    if cur[0] - 1 >= 0 and matrix[cur[0] - 1][cur[1]] == "1" and not visited[cur[0] - 1][cur[1]]:
        q.append((cur[0] - 1, cur[1], cur[2] + 1))
    if cur[1] - 1 >= 0 and matrix[cur[0]][cur[1] - 1] == "1" and not visited[cur[0]][cur[1] - 1]:
        q.append((cur[0], cur[1] - 1, cur[2] + 1))

단계별로 풀어보기 if문의 1단계 문제

너무 쉬운 문제라서 올리기도 민망하지만

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        if (a > b)
            System.out.println(">");
        else if (a < b)
            System.out.println("<");
        else System.out.println("==");
    }
}

단계별로 풀어보기 그리디 알고리즘의 마지막(4단계) 문제

더하기끼리 최대한 많이 묶으면 된다.

import java.awt.datatransfer.StringSelection;
import java.util.ArrayList;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.next();
        StringTokenizer st = new StringTokenizer(s, "-");
        ArrayList list = new ArrayList<>();
        while (st.hasMoreTokens()) {
            String next = st.nextToken();
            if(next.contains("+")) {
                StringTokenizer tokenizer = new StringTokenizer(next, "+");
                int sum = 0;
                while (tokenizer.hasMoreTokens()) {
                    sum += Integer.parseInt(tokenizer.nextToken());
                }
                list.add(sum);
            }
            else {
                list.add(Integer.parseInt(next));
            }
        }
        int result = list.get(0);
        for (int i = 1; i < list.size(); i++) {
            result -= list.get(i);
        }
        System.out.println(result);
    }
}

단계별로 풀어보기 그리디 알고리즘 2단계 문제

파이썬의 좋은 점 중 하나가 (x, y)와 같은 순서쌍을 표현하고 싶을 때 클래스를 따로 만들지 않고 튜플을 이용하면 된다는 점인 것 같다.

자바는 튜플이 없어서 클래스를 하나 만들었다.

import java.util.ArrayList;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        ArrayList li = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            li.add(new Tuple(in.nextInt(), in.nextInt()));
        }
        li.sort(new Comparator() {
            @Override
            public int compare(Tuple o1, Tuple o2) {
                if (o1.y - o2.y < 0)
                    return -1;
                else if (o1.y - o2.y > 0)
                    return 1;
                else
                    return o1.x - o2.x;
            }
        });
        ArrayList order = new ArrayList<>();
        int count = 0;
        order.add(li.get(0));
        count++;
        for (int i = 1; i < n; i++) {
            if(order.get(count - 1).y <= li.get(i).x) {
                count++;
                order.add(li.get(i));
            }
        }
        System.out.println(count);
    }
}
class Tuple {
    int x;
    int y;

    public Tuple(int x, int y) {
        this.x = x;
        this.y = y;
    }
}