1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을 www.acmicpc.net 위의 문제를 보고 분할 정복 문제라는 것을 알았지만, 분할 정복를 정확하게 모르고 있었기에 풀어내는데 조금 오래 걸렸다. import sys input = sys.stdin.readline def printResult(value, location): print(value + location) exit(0) def divide(n, r, c, value): n //= 2 if r < n and c < n: if n == 1: printResult(valu..
11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 처음에는 아래와 같이 정말 간편하게 풀 수 있을 것이라고 생각하고 풀었다. 아래와 같이 sum과 슬라이싱을 이용했더니 바로 실패했다. 그래서 누적합에 대해서 공부를 했다. n, m = map(int, input().split()) data = list(map(int, input().split())) for _ in range(m): i, j = map(int, input().split()) print(sum(data[i-1:j])) 아래는 ..
1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net DP문제를 잘 몰라서 처음에는 8까지 모든 경우의 수를 적었다. 적고 보니 어떻게 풀어야할 지 보여서 쉽게 풀 수 있다. 3이나 2로 나눠지면 best를 업데이트를 했다. 최소값만 넣을 수 있게 min을 활용해서 풀고, 마지막에 append하기 전에 min값을 넣었다. 이렇게 풀고 성공(832ms)은 했는데 생각을 해보니 굳이 인덱스를 넣을 필요가 없다는 것을 알게 되었다. import sys input = sys.stdin.readline num = int(input()) memo = [(0,0), (1,0)] for i in range(2, num+1): best = 99..
16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 이 문제를 풀면서 어떻게 BFS를 통해서 최소 탐색을 할 지 고민을 했습니다. 그래서 1~6을 추가해가면서 100이 되는 것을 확인해야한다고 생각했는데, 어떻게 풀어 나갈지가 가장 문제였다. 기존과 비슷하게 BFS를 진행하고, 각 경우의 수를 나누어 풀어나갔다. import sys from collections import deque input = sys.stdin.readline def bfs(start): q = ..
7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 앞에서 풀었던 토마토 문제와 같은 방법으로 BFS를 사용해서 풀면 쉽게 풀 수 있었다. 대신 2차원이 아닌 3차원 배열이라서 H의 값을 더 추가해서 풀었다. 코드는 앞에서 풀었던 BFS와 똑같지만 matrix의 차원만 하나 더 추가된 방법으로 풀었다. 그래서 쉽게 풀 수 있었다. import sys from collections import deque input = sys.stdin.readline directions = [(1, 0, 0..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2021 카카오 채용연계형 인턴십 문제로 나왔던 문제인 거 같다. 난이도로 봐서는 제일 쉬운 문제... 문제를 간단하게 말하면 one4seveneight라는 문자열이 들어오면 1478의 숫자로 반환하는 문제이다. 파이썬으로 풀었으면 정말 간단하게 replaceAll을 활용해서 풀었을 것이다. 여기서 생각이 나서 정규식을 활용해서 문제를 풀었다. const solution = (s) => { const words = ["zero", "one", "two", "three", "four", "five", "six"..
7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 최소라는 단어를 보고 바로 BFS를 사용한다는 것을 알았다. 그렇게 처음에는 BFS를 활용해서 풀었는데 생각해보니 한 곳에서 시작한 첫 포인트가 토마토 전체를 익은 상태로 만들어 더 많은 일 수가 나왔다. 시작점이 동시에 출발해야하는 것을 깨닫고, 이번 알고리즘2 수업에서 들은 Multi Source BFS를 떠올려서 queue에 시작점을 넣어 탐색하게 만들었다. 그렇게 푸니 최소 일수가 나온것이다. import sys from collectio..
7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 처음 이문제를 풀었는데 계속 답이 나오지 않았다. matrix를 출력해보니 한 방향으로 가지 않는 것이였다. 그래서 살펴보니 directions의 배열에 잘못 입력을 해서 문제였다. 배열을 잘 고쳐서 8방향 전부 갈 수 있게 만들어 풀 수 있었다. import sys from collections import deque input = sys.stdin.readline directions = [(-2, -1), (-1, -2), (2, 1), (1, 2), (-2,..
