컴굥일지

문제 상황 firebase로 리액트 프로젝트를 배포하려고 했다. firbase init 명령어를 쳤더니 아래와 같은 문구와 함께 제대로 작동하지 않았다. Error: HTTP Error: 401, Request had invalid authentication credentials. Expected OAuth 2 access token, login cookie or other valid authentication credential. See https://developers.google.com/identity/sign-in/web/devconsole-project. 문제 해결 방법 문제는 한 2,3년 전쯤에 firebase를 사용하면서 로그인을 했었던 적이 있어서였다. 그때 로그인한 정보가 남아있어서 fi..

문제 https://www.acmicpc.net/problem/2193 문제 내용 n자리 이친수의 개수를 구하면 된다. 이친수란 아래와 같다. 1. 이친수는 0과 1로만 이루어져 있다. 2. 이친수는 0으로 시작하지 않는다. (== 1로만 시작한다.) 3. 이친수에서는 1이 두 번 연속으로 나오지 않는다. 문제 풀이 dp로 해결할 수 있는 문제이다. dp[i][0]은 마지막이 0으로 끝나는 i자리 이친수, dp[i][1]은 마지막이 1로 끝나는 i자리 이친수로 설정해 두고 문제를 풀었다. 0으로 끝나는 이친수는 이전까지의 이친수가 1로 끝나든 0으로 끝나든 상관이 없다. 하지만, 1로 끝나는 이친수는 이전까지의 이친수가 반드시 0으로 끝나야 한다. +) 배열을 int로 선언하면 오버플로우가 발생하기 때문..

문제 https://www.acmicpc.net/problem/1149 문제 내용 n개의 집을 빨/초/파 3가지 색으로 칠하려고 한다. 각각의 집을 3가지 색으로 칠할 때의 비용이 주어졌을 때, 모든 집을 칠하는 최소 비용을 구하면 된다. 단, 인접한 집은 서로 색이 달라야 한다. 문제 풀이 dp로 문제를 풀 수 있다. dp[i][0]은 i번째 집을 칠하기까지 필요한 비용 (단, i번째 집은 빨간색) dp[i][1]은 i번째 집을 칠하기까지 필요한 비용 (단, i번째 집은 초록색) dp[i][2]은 i번째 집을 칠하기까지 필요한 비용 (단, i번째 집은 파란색) 이런 식으로 설정하고 문제를 풀면 쉽게 해결할 수 있다. 코드 #include using namespace std; int main() { in..

문제 https://www.acmicpc.net/problem/2667 문제 내용 0은 집이 없는 곳, 1은 집이 있는 곳이다. 집들이 서로 이어져있으면 같은 단지에 속해있다. 단지의 개수를 출력하고, 각 단지에 포함된 집의 개수를 오름차순으로 정렬하여 출력하면 된다. 문제 풀이 bfs/dfs를 통해 문제를 풀 수 있다. (dfs로 풀었다.) 일단 dfs를 돌며, 서로 이어진 집끼리 단지 번호를 같게 하여 used배열에 추가한다. 모든 집에 대해 dfs 탐색이 끝나면, used배열에 있는 값을 카운트하여 출력하면 된다. 코드 #include #include #include using namespace std; int dr[4] = {1, -1, 0, 0}; int dc[4] = {0, 0, 1, -1};..

문제 https://www.acmicpc.net/problem/1992 문제 내용 배열을 입력받아 규칙대로 압축을 진행하면 된다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다 문제 풀이 재귀를 사용하여 문제를 해결할 수 있다. 먼저 범위에 해당되는 부분이 다 같은 수로 채워져 있는지를 체크하고, 그렇지 않으면 4등분으로 분할하여 각각에 대해 같은 과정을 거친다. 만약 다 같은 수로 채워져 있으면 결과에..

문제 https://www.acmicpc.net/problem/15903 문제 내용 입력받은 원소 n개짜리 배열에 대해, 아래 과정을 m번 수행하면 된다. 1. x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y) 2. 계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 쓴다. m번의 과정이 모두 끝나고, 전체 원소의 합이 최소가 되도록 해야 한다. 문제 풀이 x와 y를 골라 두 값을 더해 카드를 덮어써야 한다. 즉, x와 y의 값은 기존과 같거나 커지게 된다. (값이 줄어드는 경우는 없다) 전체 합이 최소가 되게 하기 위해선, 매 과정마다 가장 작은 두 수를 x, y로 골라야 한다. 코드 #include #include using namespace std; in..

문제 https://www.acmicpc.net/problem/1780 문제 내용 아래 문제와 매우 유사한 문제이다. [BOJ/백준 2630][C++] 색종이 만들기 문제 https://www.acmicpc.net/problem/2630 문제 내용 주어진 입력에서 색종이 개수를 구하는 문제이다. 색종이는 정사각형+같은 색이어야 하며, n*n 크기의 종이가 전부 같은 색이 아니면 가로 세로를 반 gyong0117.tistory.com 1780 종이의 개수 문제 역시 색종이의 개수를 구하는 문제이다. 차이는 2630번은 매번 n/2가 되지만 이 문제는 n/3을 해야 한다는 점, 종이의 종류가 다르다는 점이다. 문제 풀이 역시나 재귀를 통해 문제를 풀면 된다. 먼저 종이가 다 같은 수로 채워져 있는지를 체크하..

문제 https://www.acmicpc.net/problem/14889 문제 내용 N명을 2개의 팀으로 나눈 후, 각 팀의 능력치를 구한다. 각 팀의 능력치 차가 최소가 되는 값을 구하면 된다. 이때 팀의 능력치는 팀에 속한 모든 쌍의 능력치의 합이다. (아래는 예시) 1,2번이 같은 팀이고 3,4번이 같은 팀일 때 (1,2)가 속한 팀의 능력치 = arr[1][2]+arr[2][1] (3,4)가 속한 팀의 능력치 = arr[3][4]+arr[4][3] 문제 풀이 이 문제에서 가장 중요한 부분은, 팀을 두 개로 나누는 것이다. 이 부분을 위해 백트래킹으로 문제를 풀었다. 사람은 1~n번으로 주어지고, 순서가 의미가 없기 때문에 N과 M (2)를 참고하면 좋을 것 같다. [BOJ/백준 15650][C++..

문제 https://www.acmicpc.net/problem/7562 문제 내용 각 테스트 케이스별로 체스판의 길이, 나이트의 현재 위치와 이동하려는 위치가 주어진다. 나이트가 최소로 이동하여 목적지까지 갔을 때, 몇 번의 이동이 필요한지 출력하면 된다. 문제 풀이 bfs를 통해 이 문제를 풀면 좋다. 체스판의 길이를 len이라 했을 때 len*len 배열을 선언하고, 초기 위치부터 bfs를 돌리면 된다. 초기 위치의 값을 1로 하고, 해당 위치로부터 갈 수 있는 곳을 +1 하여 배열에 저장하는 방식으로 문제를 풀었다. 그렇게 하면 목적지에 해당하는 arr배열의 값-1 이 구하고자 하는 값이 된다. (시작을 1로 세팅했기 때문에 -1 필요) 나이트가 이동할 수 있는 위치는 문제에 주어진 것처럼 8개이다..

문제 https://www.acmicpc.net/problem/7562 문제 내용 각 테스트케이스 별로, k개의 숫자를 입력받아 그중에서 6개를 골라 수열을 만들면 되는 문제이다. k개의 숫자는 오름차순으로 주어진다. 문제 풀이 N과 M문제와 많이 비슷한 유형으로, 백트래킹으로 풀면 되는 문제이다. 입력의 마지막이 0으로 주어진다는 점을 잘 처리하는게 중요한 부분이고, 이외에는 백트래킹 풀이와 똑같이 하면 된다. 코드 #include #include using namespace std; vector arr; vector result(6, 0); int k; void back(int cnt, int before) { if (cnt == 6) { for (int i = 0; i < 6; i++) { cout..