문제N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.1234234534564567여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000표에 채워져 있는 수는 1,000보다 작거나 같은 자연수풀이N의 최대 크기가 1024 x 1024 = 1,048,576이고, 이 행렬에서 구해야 하는 구간 합의..

문제https://school.programmers.co.kr/learn/courses/30/lessons/42860 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr조이스틱으로 알파벳 이름을 완성하려고 한다.조이스틱은 아래와 같이 네 방향으로 이동할 수 있다.▲ - 다음 알파벳▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)알파벳 이름이 주어지면, AAA에서 시작하여 알파벳 이름을 만들 수 있는 최소 조작 횟수를 구해야 한다. 풀이휴리..

문제https://www.acmicpc.net/problem/15686크기가 NxN인 도시에서 도시의 치킨 거리의 최솟값을 구하라. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리다.도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.치킨집을 최대 M개를 골라서 도시의 치킨 거리의 최솟값을 구해야 한다.2 ≤ N ≤ 50 (집의 수는 2N개를 넘지 않는다.)1 ≤ M ≤ 13 풀이치킨집을 M개 골라 도시의 치킨 거리의 최솟값을 구한다.우선 치킨집의 위치와 집의 위치를 저장해두고 M개의 치킨집을 골랐을 때, 모든 집에서의 치킨 거리를 구해 더한다. (도시의 치킨 거리) 처음엔 치킨 거리를 구하기 위해 막연히 최소 거리를 구하기 위해 BFS를 활용했지만 시간 초과가 발생했다. 그 이유는 최대 연산 횟수를 계..

문제세로 R칸, 가로 C칸의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나 적혀 있고, 좌측 상단 칸에 말이 놓여져 있다.말은 상하좌우 인접한 네 칸 중 한 칸으로 이동할 수 있으나, 새로 이동한 칸에 적힌 알파벳은 이전에 밟지 않은 알파벳이어야만 한다.좌측 상단에서 시작하여 말이 최대로 지날 수 있는 칸의 개수를 구하라.1 ≤ R, C ≤ 20풀이주어진 시간 제한이 2초, R, C의 범위가 1~20인 것에서 백트래킹으로 풀 수 있을 정도의 입력 데이터가 주어진다는 것을 확인할 수 있었다. 말은 현재 위치한 칸에서 갈 수 있는 곳을 택하고 탐색해 최장 거리를 매 재귀마다 최장 거리를 계산해준다.핵심은 '이전 상태를 어떻게 저장할 것인가'에서 나뉘게 된다. 깊은 고민없이 접근했다가 많은 시간 초과를..

문제한 자리 숫자가 적힌 종이 조각이 흩어져 있다. 흩어진 종이 조각을 붙여 몇 개의 소수를 만들 수 있는 지 알고 싶다.각 종이 조각을 붙인 문자열 `numbers`가 주어진다.1 ≤ `numbers` ≤ 7 풀이`numbers`의 길이 범위가 1~7인 것으로 보아, 완전 탐색을 사용해도 성능 상 무리가 없다는 것을 알 수 있다.순열의 경우, n개의 원소로 만들 수 있는 모든 경우의 수는 n!이며, 일반적으로 n ≤ 7~8일 때는 완전 탐색(브루트포스)이 안정적으로 동작한다.예를 들어, n = 7이라면 7! = 5040개의 조합이 생성되며, 이는 1초 내에 충분히 탐색 가능한 수준이다.다만 9 이상이 되면 경우의 수가 급격히 증가(9! = 362,880)하기 때문에 이 경우에는 백트래킹, 가지치기, ..

문제https://school.programmers.co.kr/learn/courses/30/lessons/17679 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.krm x n 크기의 게임판이 있다.같은 그림의 2x2 블록은 지워진다.블록이 지워진 후에는 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.첫 배치가 주어졌을 때, 지워지는 블록이 모두 몇 개인지 계산하려고 한다.2 ≤ `n`, `m` ≤ 30풀이더 이상 지워지는 블록이 없을 때까지 아래의 계산을 반복한다.게임판을 순회하면서 같은 그림의 2x2 블록을 찾아서 지워질 모든 블록의 좌표를 계산한다. (`check2x2(map)`)지워질 모든 블록을 ..

문제https://school.programmers.co.kr/learn/courses/30/lessons/17686 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr단순한 문자 코드 순이 아닌, 파일명에 포함된 숫자를 반영한 정렬 기능을 구현하려고 한다.파일명은 100 글자 이내, 영문 대소문자, 숫자, 공백, 마침표, 빼기 부호("-")만으로 이루어지고 영문자로 시작하며 숫자를 하나 이상 포함한다.파일명은 HEAD, NUMBER, TAIL로 이루어진다.HEAD: 숫자가 아닌 문자로 이루어져 있으며, 최소 한 글자 이상이다.NUMBER: 한 글자에서 최대 다섯 글자의 연속된 숫자로 이루어져 있으며, 앞에 0이 올..

문제https://school.programmers.co.kr/learn/courses/30/lessons/92341 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr주차장의 요금표와 차량의 입/출차 기록이 주어졌을 때, 차량별 주차 요금을 계산하려고 한다.요금표는 `[기본 시간(분), 기본 요금(원), 단위 시간(분), 단위 요금(원)]` 형태의 배열로 주어진다.입/출차 기록은 `[시각(시:분), 차량 번호, 내역(입/출)]` 형태의 배열로 주어진다.주차 요금 계산은 다음과 같은 기준으로 이루어진다.입차 후 출차 기록이 없으면 23:59에 출차된 것으로 간주한다.주차 시간이 기본 시간 이하면 기본 요금이 청구된다..