boj
-
[STACK] BOJ 9012 번 문제풀이백준 문제풀이/etc 2019. 5. 12. 00:33
문제분석 굉장히 읽기 싫을 정도로 긴 문제지만 결국 소괄호가 한쌍으로 존재하는 가? 를 묻는 문제네요. ㅎㅎ 알고리즘 문제를 풀 때, 접근법이 굉장히 중요한 게 제가 처음에 이 문제를 접근하는 방법은 이렇습니다. '(' , ')' 두 개의 개수를 카운트해서 같으면 VPS 이다 ~ 라고 접근했습니다. 이 방법 역시 그렇게 어렵진 않지만 굉장히 단순 무식한 방법 같았습니다. 그래서 다른 분들의 코드를 보니 세상에 천재들이 많더군요. 개발자 지망생 김 모 씨의 접근법은 이렇습니다. 여는 괄호 '(' 가 나오면 무조건 스택에 PUSH 하고 닫는 괄호 ')' 가 나왔을 때, 배열 안에 여는 괄호 '(' 가 존재하면 스택에서 POP 하고 배열이 비어있다면 FALSE 하는 겁니다. 같은 문제를 이렇게 구현할 수 있다..
-
[DP] BOJ 1912 번 문제풀이백준 문제풀이/Dynamic Programming 2019. 5. 11. 15:45
문제분석 처음에 해석 잘하셔야 돼요!!... 저는 이해를 잘 못해서 연속된 두 개의 수로 풀고 기차게 틀렸었습니다... 그러니까 이 문제는 연속된 여러 개의 숫자를 더했을 때 나올 수 있는 가장 큰 수를 찾는 문제죠. 만약에 이 문제가 DP 문제인 것을 파악하지 못했다면 3중 for문으로 해결할 수도 있어요. 시작점, 끝점, 중단점 이런 식으로 나눠서요. ...더보기 cin >> n; for (int st = 1; st s[i]; } d[1] = s[1]; for (int i = 2; i
-
[DP] BOJ 11726 번 문제백준 문제풀이/Dynamic Programming 2019. 5. 11. 01:48
문제분석 내용이 어렵지 않아서 추가적인 설명은 굳이 필요 없을 것 같아서 패스할게요~ 저만 그럴 수도 있지만... 처음에 이 문제를 보고 생각한 게 배열의 행을 2로 잡고 해야 되나? 도형을 뭐로 표현하지? 라고 생각했었는데 그럴 필요가 없더군요... DP 문제 점화식만 파악하면 되는 문제입니다. 우선 눈으로만 봐도 알 수 있는 경우의 수를 정의해봅시다! D[n] = 가로길이가 n 인 직사각형을 채우는 경우의 수 A = 가로길이가 2 인 직사각형 B = 가로길이가 1 인 직사각형 이라고 했을 때, D[0] = 0 D[1] = 1 D[2] = 2 3가지 경우는 확실해집니다. 이제 D[3] 에 대해서 봅시다. 상황을 두 가지로 나누어 볼 수 있습니다. D[3] 의 처음 블록을 A 로 시작하는 경우 이 경우 ..
-
[DP] BOJ 1149 번 문제 풀이백준 문제풀이/Dynamic Programming 2019. 5. 6. 16:00
문제 분석 문제는 RGB 거리에 R,G,B 의 색으로 집을 칠하는 최소비용을 구하는 것이다. 이때, 이웃하는 집의 색은 달라야 한다. 예를 들어 G 의 인덱스가 i 라고 할 때 i + 1 과 i - 1 이 이웃하는 집이다. 우선 최소비용과 색을 포함할 수 있는 배열을 선언하자. d[i][0] = i 번째 집까지 칠할 때 최소비용 단, i 번째 집은 빨간색 d[i][1] = i 번째 집까지 칠할 때 최소비용 단, i 번째 집은 초록색 d[i][2] = i 번째 집까지 칠할 때 최소비용 단, i 번째 집은 파란색 이제 배열이 선언됐으니 점화식을 끌어내 보자. 우선 경우의 수가 하나밖에 없는 초깃값들을 초기화 하자. d[0][0] = s[0][0] , d[0][1] = s[0][1] , d[0][2] = s[..
-
[DP] BOJ 2579번 문제풀이백준 문제풀이/Dynamic Programming 2019. 5. 4. 23:35
문제 분석 각 계단을 오를 때 계단에 적혀있는 숫자의 합이 가장 큰 경우를 구하는 문제다. 조건은 다음과 같습니다. ...더보기 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 자, 지금부터 s[i] = 계단의 적힌 숫자 d[i][j] = 현재까지 j 개의 계단을 연속해서 밟고, i 번째 계단에 올라섰을 때의 점수 합의 최댓값이라고 합시다. (단, i 번째 계단은 반드시 밟는다.) 이상태에서 주어진 계단에 대해서 한번 값을 찾아봅시다. 첫 번째 계단에서는 이러한 값이 도출됩니다. d[..