# ProblemSolving
백준 14502 연구소 1
이 문제는 완전탐색과 BFS를 이용해 해결 할 수 있는 대표적인 문제 유형 중 하나이다. 첫줄에는 n,m으로 각각 세로와 가로 길이가 입력이 들어오고 그 다음 n줄 동안 연구소의 구조를 입력 받는다. 예제 입력 중 하나는 아래와 같다 . 4 6 0 0 0 0 0 0 1 0 0 0 0 2 1 1 1 0 0 2 0 0 0 0 0 2 여기서 0은 빈공간, 1은 벽 그리고 2는 바이러스로 표현 할 수 있다. 문제에서는 우린 총 3개의 벽을 세울 수 있고 0으로 표시된 공간 중 3곳을 선택해 벽을 세우면 되는 것이다 . 그러면 여기서 첫번째로 0이 표시된곳 중 3개를 고르면 되기에 고등학교 수학에서 배운 조합을 활용하면 도움이 될 것이라 생각이 든다 . 모두 벽을 세운 이후에는 바이러스가 상하좌우
13976 타일 채우기 2
A. 문제 요약 $3 \times N$의 공간을 $1 \times 2$ or $2 \times 1$ 타일로 채우는 방법의 갯수를 구하는 문제 B. 제한 조건 제한 시간 : 8초 (for python 3) 제한 메모리 : 1056 MB (for python 3) C. 주의사항 타일로 공간을 채울 적에 빈 칸이 존재하면 안 됨 => $N$이 홀수일 경우 무조건 빈 칸이 존재하므로, 타일을 채울 방법이 없음. 타일로 공간을 채울 적에 타일이 겹치면 안 됨 $N$의 제한 조건이 1,000,000,000,000,000,000임에 주의 D. How to Approach 이 문제의 경우 $N$의 제한 조건이 매우 크므로, iteration을 통해서는 구할 수 없음. 또한 방법의 갯수를 1,000,000,007로 나눈 갯수를 구하면 되므로, 점화식을 구한 뒤 행렬을 세팅해 분할 정복을 통한 거듭제곱으로 푸는 것이 적절해보임.
[Floyd-Warshall Algorithm] 에 관한 정리
플로이드 워셜 알고리즘(floyd Warshall Algorithm)은 대표적인 APSF(All pairs Shortest Path)알고리즘 중 하나입니다. 활용(Applications) computer network aircarft network railroad network table of distances between all pairs of cities for a road atlas ** 간단한 알고리즘의 속성** 그래프에서 가장 짧은 경로를 찾는 그래프 알고리즘 그래프는 음의 가중치를 가져도 됨(Dijkstra's algorithm은 불가능) 다이나믹 프로그래밍의 특성을 가짐(미리 계산된 최소경로를 이용해서 활용함) O(N^3)의 시간 복잡도를 지님 (N은 노드의 개수) [예시] 
[PS][LeetCode][Swift] Shortest Unsorted Continuous Subarray
581. Shortest Unsorted Continuous Subarray Problem Input / Output Example 1: Example 2: Example 3: Code Review 처음 생각난건 역시 완전 탐색이지만, 제한 조건에 배열 크기를 보면 어림도 없는 방법이란걸 알 수 있다. 두 번째로 생각한 것은 문제에서도 말하고 있듯 이 배열은 단조롭게 증가를 해야하는데 그 부분의 길이를 찾아주는데 있어서는 Stack 을 통해서 찾아 볼 수 있지 않을까? 라는 생각 까지 했다. 그리고 마지막으로 생각 난 것이 내가 풀이 방식에 써놓은 것 이다. 내가 생각한 Stack 을 사용하는 것은 최소 2번 이상 순회를 해야하지만, 위의 코드 방식대로 쓰면 전체는 딱 한번 탐색하고
n, nvm으로 Node 설치, 버전 변경 (macOS)
homebrew가 설치되있다는 하에 nvm으로 node 설치, 변경 nvm 설치 >### nvm 설치 $ sudo curl -o- https://raw.githubusercontent.com/creationix/nvm/v0.33.1/install.sh | bash .bash_profile 수정 나노로 .bash_profile 열기 nano ~/.bash_profile > > > 다음 내용 추가 > > > 저장하고 나가기 ctrl + x y enter > > > .bash_profile 재시작 source ~/.bash_profile 확인 nvm ls Node 설치 > 16.13.0 버전 설치 nvm install 16.13.0 버전 사용 및 변경 nvm use 사용할버전 현재 실행중인 버전 확인 node -v n 으로 node 설치, 변경 n 설치 > n 설치 `bre
[PS] BOJ_2315
BOJ_2315 💡 생각하자 > Dynamic Programming(동적 계획법)의 개발절차 재귀 관계식(recursive property) 세우기 상향식 방법(bottom-up)으로 답 구하기 주어진 예시 상황에 대해서 생각해보자. |가로등 번호| 1 | 2 | 3 | 4 | 5 | 6 | |:------:|:-:|:--:|:--:|:--:|:--:|----| | 위치 | 3 | 11 | 12 | 13 | 15 | 17 | | 소비량 | 2 | 10 | 18 | 19 | 15 | 19 | 마징가는 5번 가로등에서 출발한다. 다음으로는 4번 또는 6번으로 갈 수 있다. 4번으로 간 경우를 생각해보자. 여기서도 역시 3번 또는 6번으로 갈 수 있다. 그렇다면 예를 들어 5->4->3->2->1->6 인 경우를 살펴
[PS] BOJ_11057
BOJ_11057 💡 생각하자 > Dynamic Programming(동적 계획법)의 개발절차 재귀 관계식(recursive property) 세우기 상향식 방법(bottom-up)으로 답 구하기 N=1일 때 0, 1, ⋯, 9까지 총 10개가 존재한다. N=2일 때 오르막 수를 AB라고 두면, A는 0부터 9까지 가능하다. (0으로 시작할 수 있다는 조건에 의해) 그러면 A=0이고 B는 0~9, A=1이고 B는 1~9, ⋯, A=9이고 B는 9까지 총 55개가 존재한다. > 재귀 관계식 DPi : 길이가 j이고 i로 시작하는 오르막 수의 개수 DPi = sum(DPi + DPi+1 + ⋯ + DP9) 💻 구현하자 **길이가 n인 오르막
.png)
[PS] BOJ_10844
BOJ_10844 💡 생각하자 > Dynamic Programming(동적 계획법)의 개발절차 재귀 관계식(recursive property) 세우기 상향식 방법(bottom-up)으로 답 구하기 먼저, N=2인 경우(AB)를 생각해보자. 10, 12, 21, ⋯ ,87, 89, 98이 가능하다. 다음으로, N=3인 경우(ABC)를 생각해보자. A는 1~9가 가능하다. 이제 뒤의 두자리 BC를 구해야하는데, 이는 이미 N=2인 경우에서 구했다. 하지만 여기서 한가지 신경써야 할 것은 A에 따라서 B에 올 수 있는 수가 정해져있다는 것이다. 예를들어, A=3이면 B는 2 또는 4만 가능하다. 그러면 N=2인 경우에서 2, 4로 시작하는 것들이 가능하다. A가 2~8일 때는 위와 동일하지만, 1과 9일 때는 따로 생각해주어
[PS] BOJ_9095
BOJ_9095 💡 생각하자 > Dynamic Programming(동적 계획법)의 개발절차 재귀 관계식(recursive property) 세우기 상향식 방법(bottom-up)으로 답 구하기 먼저, [1 = 1], [2 = 1+1, 2], [3 = 1+1+1, 1+2, 2+1, 3]인 것은 쉽게 구할 수 있다. 주어진 예시 4에 대해서 생각해보자. 4는 1+'3', 2+'2', 3+'1'로 나눌 수 있다. 1) 1+'3' 위에 있는 3에 대한 정보를 활용하면 1+(1+1+1), 1+(1+2), 1+(2+1), 1+(3)을 얻을 수 있다. 2) 2+'2' 위에 있는 2에 대한 정보를 활용하면 2+(1+1), 2+(2)를 얻을 수 있다. 3) 3+'1' 위에
.png)
[PS] BOJ_1463
BOJ_1463 💡 생각하자 > Dynamic Programming(동적 계획법)의 개발절차 재귀 관계식(recursive property) 세우기 상향식 방법(bottom-up)으로 답 구하기 주어진 예시 '10'에 대해서 생각해보자. 10은 3가지 연산 중에서 '2로 나누기'와 '1을 빼기'를 적용할 수 있다. 그렇다면 '5->1'과 '9->1'에 필요한 연산의 수를 비교하여, 작은 쪽을 선택하고 +1('10/2=5' or '10-1=9')을 하면 '10->1'에 필요한 연산의 수를 구할 수 있다. 이렇듯 '10->9->3->1'에서 '10->1'을 구하기 위해서는 '9->1'이 필요하고, '9->1'은 '3->1', '3->1'은 '1->1'이 필요하므로, bottom-up으로 구하면 된다. > 재귀 관계식 M(n)
[PS] BOJ_9251
BOJ_9251 💡 생각하자 >Dynamic Programming(동적 계획법)의 개발절차 재귀 관계식(recursive property) 세우기 상향식 방법(bottom-up)으로 답 구하기 주어진 두 문자열을 X = $$x{1}x{2}⋯x{n}$$, Y = $$y{1}y{2}⋯y{m}$$으로 둔다. LCS(i, j)는 X$${i}$$ = $$x{1}x{2}⋯x{i}$$와 Y$${j}$$ = $$y{1}y{2}⋯y{j}$$ 사이의 LCS 길이 값을 의미한다. (1 LCS(i,
[PS] BOJ_2579
BOJ_2579 💡 생각하자 >Dynamic Programming(동적 계획법)의 개발절차 재귀 관계식(recursive property) 세우기 상향식 방법(bottom-up)으로 답 구하기 문제의 조건에 의해 마지막 계단(n번째 계단)은 무조건 밟아야 하므로, 경우의 수는 2가지가 존재한다. 1) n-2번째 계단 -> n번째 계단 2) n-1번째 계단 -> n번째 계단 단, 이 경우에는 연속된 3개의 계단을 밟을 수 없다는 조건에 의해 무조건 'n-3 -> n-1 -> n' 의 순서를 가지게 된다. > 재귀 관계식 stairs[n] = n번째 계단의 점수 S[n] : n번째 계단까지 오를 때 얻을 수 있는 점수의 최댓값 S[n] = maximum(S[n-2] + stairs[n], S[n-3
[PS] BOJ_11049
BOJ_11049 💡 생각하자 >Dynamic Programming(동적 계획법)의 개발절차 재귀 관계식(recursive property) 세우기 상향식 방법(bottom-up)으로 답 구하기 > 재귀 관계식 Ai : $$M{i}$$부터 $$M{j}$$까지의 행렬을 곱하는데 필요한 곱셈의 최소 횟수 Ai = minimum(Ai + Ak+1 + d$${i-1}$$d$${k}$$d$$_{j}$$) (i <= k <= j-1) Ai = 0 💻 구현하자 Ai를 구하는 함수 
[Express] Uncaught (in promise) SyntaxError: Unexpected token < in JSON at position 0
Uncaught (in promise) SyntaxError: Unexpected token < in JSON at position 0 비동기 통신 간에 에러가 발생했다. express() 도큐먼트를 살펴보면 .png)
[PS] BOJ_11404
BOJ_11404 💡 생각하자 >Dynamic Programming(동적 계획법)의 개발절차 재귀 관계식(recursive property) 세우기 상향식 방법(bottom-up)으로 답 구하기 > 재귀 관계식 $$D{k}i = minimun(D{k-1}i, D{k-1}i + D{k-1}k)$$ 💻 구현하자 D 배열을 초기화 하는 함수 i = j인 경우, $$V{i}$$에서 $$V{j}$$로의 비용은 0이다. 나머지는 임의의 큰 값(INF)로 초기화 해준다. 플로이드-와샬 알고리즘 \- 1번째 for문: $$V_{k}$$를 거칠 경우에 대해.. \- 2, 3번째 for문: 모든 경로에 대해서.. 이전 단계에서 갱신된 비용(D[i][j
[PS] React에서 alert 가 잘 동작하지 않을 때
Problem React를 설치하고 코드를 테스트를 하던 중 발생했다. 텍스트를 입력하고 버튼을 누르면 입력한 내용이 alert되는 NameForm 이라는 컴포넌트를 만들고 기존 App에 import 해주었다. 브라우저를 여는 순간 의도하지 않은 alert가 동작하고 .png)
[PS] BOJ_1992
BOJ_1992 💡 생각하자 먼저, 주어진 영상이 모두 0 또는 1로 되어있는지 판단하는 함수를 만든다. 만약 주어진 영상이 0과 1이 섞여있으면, 같은 수로 이루어진 영상이 나올 때 까지 4등분 한다. 💻 구현하자 주어진 영상이 모두 같은 수로 이루어져 있는지 판단하는 함수 \- pivot: 영상에서 첫번째 원소 영상을 4등분하는 함수 \- 종료조건: 주어진 영상이 모두 같은 수로 이뤄져있거나(res = TRUE), 영상의 길이가 2보다 작은 경우(n < 2) 더이상 4등분 할 필요가 없다. 초기 호출문 💥 발전하자 에러 및 해결 divideMat() 내부의 반복문에서 아무생각없이 i=0, j=0부터 시작하여 무한루프가 발생했다. 주의하자! 📌
.png)
[PS] BOJ_1780
BOJ_1780 💡 생각하자 먼저, 주어진 행렬이 같은 수로 이루어졌는지 판별하는 함수를 만든다. 위의 함수를 재귀적으로 수행할 때, 전달되는 행렬이 분할된 9개 중 어떤 것인지 알려줘야한다. 그러므로 해당 행렬의 첫번째 원소의 좌표를 전달한다. 💻 구현하자 주어진 행렬이 같은 수로 이루어졌는지 판별하는 함수 \- srow, scol: 주어진 행렬의 첫번째 원소 좌표 행렬을 돌면서 첫번째 원소(temp)와 비교한다. -> 다른 값의 원소가 발견되면 FALSE -> 반복문을 끝까지 수행하면 모두 같은 수로 이루어졌음을 의미한다. 그러므로 TRUE \- count()는 temp로만 이루어진 행렬의 수를 세는 함수 행렬을 분할하는 함수 \- 종료조건: 1 by 1 행렬이 되거나 해당 행렬이 모두 같은 수
[PS] BOJ_14600
BOJ_14600 💡 생각하자 > $$2^n$$ ⨉ $$2^n$$ 크기의 정사각형에 1x1 한 칸을 제외하고 항상 L-Tromino로 모두 채울 수 있다. _지금부터 편의를 위해 정사각형 한 변의 길이를 n으로 둔다. (단, n은 2의 거듭제곱)_ 한 변의 길이가 n인 정사각형에서 'X'가 속한 사분면을 확인하고, 해당 사분면을 제외한 나머지 3개의 사분면에 4등분 선을 중심으로 1칸씩 채워서 L-Tromino 하나를 생성한다. 
[PS][LeetCode][Swift] Push Dominoes
서론 놀랍게도 못풀었다.. 삽질을 엄청 했는데, 처음에 문제를 잘못읽어서, RR.L 경우에 가중치가 필요하지않나?.. 라는 생각도 했고, 마지막에 투포인터까지 가는 과정에서는 양사이드로 미는 것 까지는 생각했는데, 길이로 문제를 해결하려고 했다. 최근에 DP 를 틀린 적이 없는데.. 틀리다니 꽤나 충격적이었다. 풀이를 보고 푼 것을 리뷰해보자. 문제 문제는 여기에 있다. ![](https://images.velog.io/images/hzw94/post/071e6e4d-7d9c-4003-ae37-e32ebd7c4292/%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202022-01-08%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86