문제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://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인 것에서 백트래킹으로 풀 수 있을 정도의 입력 데이터가 주어진다는 것을 확인할 수 있었다. 말은 현재 위치한 칸에서 갈 수 있는 곳을 택하고 탐색해 최장 거리를 매 재귀마다 최장 거리를 계산해준다.핵심은 '이전 상태를 어떻게 저장할 것인가'에서 나뉘게 된다. 깊은 고민없이 접근했다가 많은 시간 초과를..

문제https://www.acmicpc.net/problem/93282차원 좌표 상의 맵에서 문서를 훔치려고 한다.문은 모두 잠겨 있고, 문을 열려면 열쇠가 필요하다.열쇠의 일부를 미리 가지고 있고 일부 열쇠는 빌딩의 바닥에 놓여져 있다.상하좌우로만 이동할 수 있을 때, 훔칠 수 있는 문서의 최대 개수를 구하려고 한다.테스트 케이스의 개수 ≤ 1002 ≤ h, w ≤ 100 '.'는 빈 공간을 나타낸다.'*'는 벽을 나타내며, 벽은 통과할 수 없다.'$'는 훔쳐야하는 문서이다.알파벳 대문자는 문을 나타낸다.알파벳 소문자는 열쇠를 나타내며, 그 문자의 대문자인 모든 문을 열 수 있다.이미 가지고 있는 열쇠가 공백없이 주어진다. 만약, 열쇠를 하나도 가지고 있지 않는 경우에는 "0"이 주어진다.처음에는 ..

문제이 식에 괄호를 적절하게 쳐서 식의 값을 최소로 만드려고 한다.식은 0~9, +, -로만 이루어져 있다. 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 풀이그리디 알고리즘을 연습하고자 푼 문제다. 하지만 아이디어가 잘 떠오르지 않았다. 힌트를 얻어 풀 수 있었다. 아직 JS에 익숙하지 않아 파싱하는 데 어려움을 겪었다. 그리디 알고리즘은 아이디만 떠오르면 푸는 건 금방인데 아이디어가 잘 안떠오르면 시간이 많이 걸리는 듯하다..💡 숫자로 판별될 수 있는 값과 그렇지 않은 값이 배열에 혼재되어 있으면 `map(Number)`를 사용할 수 없음에 주의하자. 최소값을 만드려면 뺄셈이 시작되면..

문제https://www.acmicpc.net/problem/7453정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다. A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구해야 한다. 1 ≤ 배열의 크기 ≤ 4,000 풀이배열의 최대 크기가 4,000으로 단순 4중 반복문으로는 16,000,000^2번 반복해야 하므로 불가능하다.이분 탐색 혹은 투 포인터를 활용하거나, 맵으로 저장하는 방법이 있다. 처음은 이분 탐색으로 풀이를 시도했는데, 계속 시간 초과가 났다. 그래서 풀이 방법을 찾아보다가 맵을 활용해서 풀었더니 통과할 수 있었다.찾아보니 JS로는 이분 탐색, 투 포인터로는 시간 내로 풀 수 없다고 한다. 또 자바의 경우엔 맵으로 풀 수 없고, 이분 ..

문제https://www.acmicpc.net/problem/1863스카이라인은 건물의 그림자를 말한다.스카이라인을 보고 도시에 세워진 건물이 몇 채인지 알고싶다.정확히 몇개인지 아는 것은 대부분 불가능하고, 최소한 몇 채인지 알아내고 싶다. 아래 스카이라인을 보자................................XX.........XXX........XXX.XX.......XXXXXXX.....XXXXXXXXXX....XXXXXXXXXXXX다음 스카이라인에는 최소 6개의 건물이 있다................................22.........333........111.22.......XX333XX.....X111X22XXX....XX333XXXXXXX..................

문제https://www.acmicpc.net/problem/16236N x N 크기의 격자에 물고기 M마리와 아기 상어 1마리가 있다. 한 칸에는 물고기가 최대 한 마리만 존재한다.물고기, 아기 상어는 모두 크기를 가지며 처음 아기 상어는 2의 크기로 시작하며 1초에 상하좌우로 인접한 칸으로 이동한다.아기 상어는 자신보다 큰 물고기는 지나갈 수 없고, 나머지 칸은 지나갈 수 있다. 아기 상어는 자신보다 작은 물고기만 먹을 수 있다.아기 상어는 다음과 같은 기준으로 이동한다.더 이상 먹을 수 있는 물고기가 없다면 이동을 종료한다.먹을 수 있는 물고기가 1마리라면, 그 물고기를 먹으러 간다.먹을 수 있는 물고기가 1마리보다 많다면, 거리가 가장 가까운 물고기로 간다.거리는 물고기 칸까지 지나야하는 칸의 최..