오늘도 맑음

[Node.js] 1913. 달팽이

문제 설명홀수인 자연수 N이 주어지면, NxN 그리드에 달팽이(=나선형) 모양으로 값을 채우는 문제이다.단 N 문제 풀이1. 시작 지점을 구해야 한다. 👉 sr, sc (startR, startC)- N = 3일 경우, (1,1)- N = 5일 경우, (2,2)- N = 7일 경우, (3,3)sr = Math.floor(N / 2)sc = Math.floor(N / 2) 2. 나선형으로 돌려야한다.아래 그림을 보면 맨처음은 위로 1번 이동하고 오른쪽으로 1번 이동하는 것을 알 수 있다.그 다음에는 아래로 2번 이동 왼쪽으로 2번 이동했다.그 다음에는 위로 3번 이동 오른쪽으로 3번 이동했다. 같은 방향으로 가야하는 칸의 수를 step이라고 하고, step = 1로 초기화한다.- step = 1 로 ..

우선 자랑부터2등이긴 하지만 거의 1등과 다름없는 성과가 있었다. 문제 설명"quackquack" 과 같이 오리 녹음소리가 입력으로 주어질 때, 동시에 울고 있는 오리 수를 구하는 문제이다. 예를 들어, quackquack은 동시에 울고 있는 오리가 없기 때문에 1마리이다.quqacukqauackck : 2마리quackquackquackquackquackquackquackquackquackquack : 1마리qquuaacckk : 2마리  오리 녹음 소리가 올바르지 않은 경우는 -1을 리턴한다.1) 순서대로 아닌 경우 (예. kcauq)2) 녹음이 끝난 후 오리가 울다가 끝난 경우 (예. qquack) 문제 풀이동시에 울고 있는 오리 수를 어떻게 구할까? 기본적인 동작을 먼저 생각해보았다. 예를 들어,만..

문제 설명입력 예시- 2개의 숫자 5, 6이 주어짐- 연산자 순서대로 +, -, x, ÷ 이 개수를 나타내며, 곱셈을 한개 가지고 있음을 의미25 60 0 1 0 숫자 사이의 연산자를 원하는 대로 조합하여 구할 수 있는 결과값 중 가장 큰 값과 가장 작은 값을 리턴하는 문제이다. 문제 풀이N 이는 1초에 해당하는 1억번의 연산보다 적은 수이므로 모든 조합을 구한다, 즉 백트래킹 문제이다. 우선 사칙 연산의 결과를 리턴하는 함수를 별도로 분리했다.function getResult(a, b, opNum) { if (opNum === 0) return a + b; else if (opNum === 1) return a - b; else if (opNum === 2) return a * b; else {..

백준 링크https://www.acmicpc.net/problem/2294문제 접근우선 가치 K를 완성하기 위해 필요한 최소 동전 개수를 구하기 위해완전 탐색 방식으로 접근을 시도 했다.그림 설명가치는 K이고 동전은 [1,2,3,4....N] 가정했을 때,Top Down 방식으로 생각한다면, 가치 K가 되기 위해서는 K-1, K-2, K-3, .....K-N 에서 동전 한개를 추가했을 것이다.따라서 트리형식이고, 이 경우의 시간복잡도는 O(N^K)이 된다.그리고 시간 초과가 된다. 따라서 다른 방식을 생각해내야 했다. 그렇다면 DP는 어떨까? 가치 K가 되기 위해서는 dp[K-coin] + 1 과 dp[K] 의 최소값을 넣어주면 될것같았다. 이중 반복문을 사용하여,첫번째 반복문 -> 모든 코인에 대해 순..

문제 링크https://www.acmicpc.net/problem/12904문제 해설A와 B로만 이루어진 영어 단어가 존재한다.두 문자열(S, T) 가 주어질 때, S를 T로 바꿀 수 있는 지 판별한다.문자열을 바꾸기 위한 연산은 다음과 같다.1. 문자열의 뒤에 A를 추가한다.2. 문자열을 뒤집고 뒤에 B를 추가한다. 예시BABBA B가 ABBA 가 되기 위해선 B, BA, ABB, ABBA 과정을 거치며, 최종적으로 ABBA가 됐으므로, 1을 리턴한다.만약 변경하지 못할 경우, 0을 리턴한다. ❌ 문제 접근 1 연산의 종류는 2가지이다. 따라서 연산 (1) 과 연산 (2)를 적용했을 때 다음과 같이 트리 형태로 나타낼 수 있다.시간 복잡도는 O(2^N)이 될것이고, 제한조건에 N은 1000자리이하라고 ..

문제 설명0부터 목적지(d)까지 가되, 가장 빠르게 갈 수 있는 거리를 찾는다.만약 지름길이 없다면 거리는 d가 되지만, 중간에 지름길이 있다면 그 거리는 더 짧아진다. 예시2 10010 60 4050 90 20 d가 100이고, 지름길이 총 2개이다. - 0 -> 10 -> 60 -> 100 : 10 + 40 + 40 = 90- 0 -> 50 -> 90 -> 100 : 50 + 20 + 10 = 80 이므로, 정답은 80이다. 문제 해결이전 값이 이후 값에 영향을 주기 때문에, dp로 해결할 수 있었다. DP 배열 정의- dp[i] : i 위치까지 가는 데 필요한 최단 거리- 0으로 초기화 식각 위치 i에 대해,기본적으로는 distance[i-1] + 1 을 수행한다.하지만, 지름길을 사용하는 경우 ..

문제 설명표와 구간을 나타내는 테스트 케이스가 주어질 때, 그 구간까지의 합을 구하는 문제이다. 만약 (2,2) - (3,4)의 구간합을 구하는 문제에서는 파란색 칸만큼 더하여 3+4+5+4+5+6 = 27이다. 문제 풀이구간합으로 풀 수 있었다.우선 2차원 배열 dp를 선언한다. dp[i][j]는 (0,0) 부터 table[i][j] 까지의 합이다.그림에서 보다싶이, 파랑과 빨강이 겹치는 부분이 존재하기 때문에 공통 된 부분은 빼줘야 한다. 코드로 나타내면 다음과 같다. 우선 dp를 (n+1)x(n+1) 사이즈를 0으로 초기화해주고,1) 왼쪽 dp 값 + 오른쪽 dp 값을 더한다.2) 대각선 dp 값을 빼준다.3) 현재 값을 더해준다. 이 과정을 통해 dp에 (0,0) 부터 현재 좌표까지 누적한 값들..

1. 입력으로 주어진 nxm 보드판에서 체스판(8x8)로 자른다.2. 체스판(8x8) 에서 예상한 컬러와 현재 컬러가 다르다면 변경 횟수를 1증가시킨다. 체스판의 종류는 2가지1. (0,0) 이 블랙(B)으로 시작하면서 교차로 색이 나오는 체스판 2. (0,0) 이 화이트(W)로 시작하며서 교차로 색이 나오는 체스판 두 개의 경우는 다 비교해야 하지만, 사실은 둘 중 하나만 하더라도 64 - (둘 중 하나를 돌렸을 때 나오는 경우) 로 나머지도 구할 수 있었다.편의상 1, 2 체스판을 각각 블랙 체스판, 화이트 체스판이라고 말하겠다. 따라서 나는 화이트 체스판이라고 가정해서 풀었다.화이트 체스판에서 예상한 컬러 구하는 법1. 인덱스가 홀수 + 홀수 이거나 짝수 + 짝수 -> 화이트(W)2. 인덱스가 홀수..

이 문제는 N이 크지 않아서 dfs 로 풀어도 가능하다.다음과 같이 각 노드에 대해 뻗어 나가는 경우는 2개이다.1. 인사를 한다2. 인사를 안한다트리로 나타내면 다음과 같고, 시간복잡도는 2의 N승이다.하지만, 제한조건 N의 수가 커진다면, 시간복잡도를 만족하지 않을 수 있다.그럼 어떻게 최적화를 할 수 있을까? 경우의 수를 구하는 문제에서는 배낭(Knapsack) 알고리즘으로 해결할 수 있었다.같은 색 노드를 봤을 때 사실 인덱스(i)만 다르지 얻을 수 있는 행복과 현재 체력은 같다. 따라서 i 번째 사람과 인사를 안할 경우 i-1번째 사람한테서 가져오면 된다. 하지만 i번째 일때도 경우의 수가 4개 정도 존재한다. 그 중 어떤 경우의 수에서 값을 가져와야할까?이것까지 고려해주기 위해 dp는 1차원 ..

각 도시들 사이에 길이 있을 수도 있고, 없을 수도 있다. 도시들의 연결되어 있는 정보를 보고 여행갈 수 있는 지를 판별하여 "YES"나 "NO"를 출력하면 된다.도시들이 연결되어있다는 말은 하나의 그래프라는 것이고 유니온 파인드 알고리즘을 사용하여 알 수 있다. 유니온 파인드각 연결정보가 주어질 때, 그 그래프를 모두 연결해보면 2개의 그래프로 나뉜다는 것을 알 수 있다.  그렇다면 유니온 파인드는 어떻게 구현할까? 유니온 파인드는 부모(Parent) 배열을 사용하여 각 원소가 속한 집합을 나타낸다.초기에는 각 원소가 자기 자신을 부모로 가지도록 설정한다.(1) Find 연산 (경로 압축: Path Compression)Find 연산은 특정 원소가 속한 집합의 대표(root) 원소를 찾는 과정일반적인 ..