'분류 전체보기' 카테고리의 글 목록 (34 Page)

728x90

삼성 SW 역량 테스트 기출 문제인 14503번 문제

14503번: 로봇 청소기

로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다. 로봇 청소기는 다음

www.acmicpc.net

문제를 그대로 코드로 구현하면 되는 직관적인 문제였다.

def clean(now_row, now_col, direction):
    if li[now_row][now_col] == 0:
        li[now_row][now_col] = 2 #2는 청소된 부분을 말한다
    if li[now_row][now_col - 1] != 0 and li[now_row - 1][now_col] != 0 and li[now_row][now_col + 1] != 0 and li[now_row + 1][now_col] != 0:
        if direction == 0 and li[now_row + 1][now_col] != 1:
            clean(now_row + 1, now_col, direction)
        elif direction == 1 and li[now_row][now_col - 1] != 1:
            clean(now_row, now_col - 1, direction)
        elif direction == 2 and li[now_row - 1][now_col] != 1:
            clean(now_row - 1, now_col, direction)
        elif direction == 3 and li[now_row][now_col + 1] != 1:
            clean(now_row, now_col + 1, direction)
        else:
            return
    elif direction == 0:
        if li[now_row][now_col - 1] == 0:
            clean(now_row, now_col - 1, 3)
        else:
            clean(now_row, now_col, 3)
    elif direction == 1:
        if li[now_row - 1][now_col] == 0:
            clean(now_row - 1, now_col, 0)
        else:
            clean(now_row, now_col, 0)
    elif direction == 2:
        if li[now_row][now_col + 1] == 0:
            clean(now_row, now_col + 1, 1)
        else:
            clean(now_row, now_col, 1)
    elif direction == 3:
        if li[now_row + 1][now_col] == 0:
            clean(now_row + 1, now_col, 2)
        else:
            clean(now_row, now_col, 2)
from sys import stdin
n, m = list(map(int, stdin.readline().split()))
r, c, d = list(map(int, stdin.readline().split()))
li = []
visited = [[False] * m for i in range(n)]
for i in range(n):
    li.append(list(map(int, stdin.readline().split())))
clean(r, c, d)
count = 0
for i in range(n):
    for j in range(m):
        if li[i][j] == 2:
            count += 1
print(count)

728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 1932번 정수 삼각형 (0)	2020.01.18
[백준] 14890번 경사로 (0)	2020.01.16
[백준] 1149번 RGB 거리 (0)	2020.01.12
[백준] 9461번 파도반수열 (0)	2020.01.12
[백준] 11729번 하노이 탑 이동 순서 (0)	2020.01.12

728x90

단계별로 풀어보기 동적계획법1의 5단계 문제

1149번: RGB거리

RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이고, 첫 집과 마지막 집은 이웃이 아니다. 각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠하는 비용의 최솟값을 구하는 프로그램을 작성하시오.

www.acmicpc.net

이렇게 제출했는데 런타임 에러가 났다

def promising(row, color):
    if row == 0:
        return True
    if col[row - 1] == color:
        return False
    else:
        return True
def locate(row):
    if row == n:
        total.append(cost[row - 1])
        return
    for i in range(3):
        if promising(row, i):
            col[row] = i
            cost[row] = cost[row - 1] + li[row][i]
            locate(row + 1)
n = int(input())
li = []
from sys import stdin
for i in range(n):
    li.append(list(map(int, stdin.readline().split())))
col = [0] * n
cost = [0] * n
total = []
locate(0)
print(min(total))

5일 뒤 2020.01.18 재도전

1932번을 풀고 나니까 이 문제도 어떻게 푸는지 딱 보였다.

이렇게 쉽게 풀 수 있었는데 괜히 시간 낭비를 한 것 같지만 덕분에 또 하나 더 배웠다. 앞으로는 절대로 잊지 말아야지

1932번과 같이 뒤에서부터 풀면 된다.

n = int(input())
li = []
from sys import stdin
for i in range(n):
    li.append(list(map(int, stdin.readline().split())))
for i in range(n - 2, -1, -1):
    for j in range(3):
        if j == 0:
            li[i][j] = min(li[i][j] + li[i + 1][1], li[i][j] + li[i + 1][2])
        elif j == 1:
            li[i][j] = min(li[i][j] + li[i + 1][0], li[i][j] + li[i + 1][2])
        else:
            li[i][j] = min(li[i][j] + li[i + 1][0], li[i][j] + li[i + 1][1])
print(min(li[0]))

728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 14890번 경사로 (0)	2020.01.16
[백준] 14503 로봇 청소기 (0)	2020.01.15
[백준] 9461번 파도반수열 (0)	2020.01.12
[백준] 11729번 하노이 탑 이동 순서 (0)	2020.01.12
[백준] 2447번 별 찍기 - 10 (0)	2020.01.12

728x90

단계별로 풀어보기 동적계획법1의 4단계 문제

9461번: 파도반 수열

문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. N이 주어졌을 때, P(N)을 구하

www.acmicpc.net

test_case = int(input())
for i in range(test_case):
    n = int(input())
    li = [1] * n
    for j in range(3, n):
        li[j] = li[j - 3] + li[j - 2]
    print(li[n - 1])

728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 14503 로봇 청소기 (0)	2020.01.15
[백준] 1149번 RGB 거리 (0)	2020.01.12
[백준] 11729번 하노이 탑 이동 순서 (0)	2020.01.12
[백준] 2447번 별 찍기 - 10 (0)	2020.01.12
[백준] 10870번 피보나치 수5 (0)	2020.01.12

728x90

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

11729번: 하노이 탑 이동 순서

세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5

www.acmicpc.net

def hanoi(n, fr, temp, to):
    if n == 1:
        li.append((fr, to))
        return
    hanoi(n - 1, fr, to, temp)
    li.append((fr, to))
    hanoi(n - 1, temp, fr, to)
n = int(input())
li = []
hanoi(n, 1, 2, 3)
print(len(li))
for i in range(len(li)):
    print(li[i][0], li[i][1])

728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 1149번 RGB 거리 (0)	2020.01.12
[백준] 9461번 파도반수열 (0)	2020.01.12
[백준] 2447번 별 찍기 - 10 (0)	2020.01.12
[백준] 10870번 피보나치 수5 (0)	2020.01.12
[백준] 10872번 팩토리얼 (0)	2020.01.12

728x90

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

2447번: 별 찍기 - 10

첫째 줄에 N이 주어진다. N은 항상 3의 제곱꼴인 수이다. (3, 9, 27, ...) (N=3k, 1 ≤ k < 8)

www.acmicpc.net

def star(k):
    for a in range(n // k):
        for b in range(n // k):
            for i in range(k // 3 + a * k, k // 3 + a * k + k // 3):
                for j in range(k // 3 + b * k, k // 3 + b * k + k // 3):
                    li[i][j] = ' '
    if k == 3:
        return
    star(k // 3)
n = int(input())
li = [['*'] * n for i in range(n)]

star(n)
for i in range(n):
    for j in range(n):
        print(li[i][j], end='')
    print()

728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 9461번 파도반수열 (0)	2020.01.12
[백준] 11729번 하노이 탑 이동 순서 (0)	2020.01.12
[백준] 10870번 피보나치 수5 (0)	2020.01.12
[백준] 10872번 팩토리얼 (0)	2020.01.12
[백준] 2206번 벽 부수고 이동하기 (미해결) (0)	2020.01.11

728x90

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

10870번: 피보나치 수 5

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를 구하는

www.acmicpc.net

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))

728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 11729번 하노이 탑 이동 순서 (0)	2020.01.12
[백준] 2447번 별 찍기 - 10 (0)	2020.01.12
[백준] 10872번 팩토리얼 (0)	2020.01.12
[백준] 2206번 벽 부수고 이동하기 (미해결) (0)	2020.01.11
[백준] 1697 숨바꼭질 (0)	2020.01.10

728x90

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

10872번: 팩토리얼

0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.

www.acmicpc.net

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

728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 2447번 별 찍기 - 10 (0)	2020.01.12
[백준] 10870번 피보나치 수5 (0)	2020.01.12
[백준] 2206번 벽 부수고 이동하기 (미해결) (0)	2020.01.11
[백준] 1697 숨바꼭질 (0)	2020.01.10
[백준] 7569번 토마토 (0)	2020.01.10

728x90

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

2206번: 벽 부수고 이동하기

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동

www.acmicpc.net

이렇게 짰는데

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)

틀렸다고 한다.

728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 10870번 피보나치 수5 (0)	2020.01.12
[백준] 10872번 팩토리얼 (0)	2020.01.12
[백준] 1697 숨바꼭질 (0)	2020.01.10
[백준] 7569번 토마토 (0)	2020.01.10
[백준] 7576번 토마토 (0)	2020.01.10

728x90

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

1697번: 숨바꼭질

문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지

www.acmicpc.net

최솟값을 구하는 것이므로 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;
}

728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 10872번 팩토리얼 (0)	2020.01.12
[백준] 2206번 벽 부수고 이동하기 (미해결) (0)	2020.01.11
[백준] 7569번 토마토 (0)	2020.01.10
[백준] 7576번 토마토 (0)	2020.01.10
[백준] 2178번 미로 탐색 (0)	2020.01.10

728x90

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

7569번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, 1 ≤ H ≤ 100 이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마

www.acmicpc.net

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)

728x90

'알고리즘 문제' 카테고리의 다른 글

[백준] 2206번 벽 부수고 이동하기 (미해결) (0)	2020.01.11
[백준] 1697 숨바꼭질 (0)	2020.01.10
[백준] 7576번 토마토 (0)	2020.01.10
[백준] 2178번 미로 탐색 (0)	2020.01.10
[백준] 1330번 두 수 비교하기 (0)	2020.01.10

Feel Coding