문제풀이
-
[Brute Force] BOJ 2309 번 : 일곱 난쟁이백준 문제풀이/BRUTE FORCE 2019. 6. 25. 19:22
문제 왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다. 아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다. 아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오. 입력 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. 문제 요약 9명의 키가 모두 다른 난쟁이들이 있다. 이 중에서 키의..
-
[Greedy] BOJ 1449번 : 수리공 항승백준 문제풀이/GREEDY 2019. 5. 29. 23:25
문제 항승이는 품질이 심각하게 나쁜 수도 파이프 회사의 수리공이다. 항승이는 세준 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다. 파이프에서 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다. 항승이는 길이가 L인 테이프를 무한개 가지고 있다. 항승이는 테이프를 이용해서 물을 막으려고 한다. 항승이는 항상 물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다고 생각한다. 물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수를 구하는 프로그램을 작성하시오. 테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능하다. 입력 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 ..
-
[DP] BOJ 11053 번 문제 풀이백준 문제풀이/Dynamic Programming 2019. 5. 13. 15:05
문제분석 DP 유형의 문제들은 점화식을 도출하는 것이 문제의 전부입니다!! D[i] = i 번째 인덱스를 마지막으로 하는 수열의 최대 길이 arr[i] = 주어진 수열 이라고 정의하고 시작하겠습니다. 그러면, D[1] = 1 은 자명합니다. D[2] 부터는 주어진 수열의 데이터를 비교해야 합니다. 1. 이전 값 중에 arr[2] 보다 작은 값들을 모두 후보 인덱스로 둡니다. 2. D[후보 인덱스] 중에 최댓값을 구합니다. 3. 그 최댓값에 자기 자신인 1을 더해줍니다. 설명이 조금 복잡하니 예시문제로 다시 봅시다. 10 20 10 30 20 50 이러한 수열이 있습니다. 이때, D[4] 를 구하고자 합니다. 그러면 우선 arr[4] = 30 의 값 보다 작은 값들을 이전 인덱스에서 색출합니다. 10 20..
-
[STACK] BOJ 1874 번 문제풀이백준 문제풀이/etc 2019. 5. 13. 13:33
문제 분석 문제에 친절하게 스택을 사용하라고 나와있죠? ㅎㅎ 내용은 이렇습니다. 원하는 수를 사용하기 위해서는 반드시 스택에 push, pop 하는 과정을 거쳐야 합니다. 스택에 값은 아래의 그림처럼 채워집니다. 예를 들어, 가장 처음에 5를 사용해야 한다면 1 ~ 5 의 숫자를 push 한 후에 pop 을해서 사용하는 겁니다. 이게 이해가 되셨다면, 만들고자 하는 배열을 저장해야 하는데 이 배열을 큐에 저장하면 간단합니다. 입력 파트를 보면 먼저 입력된 값부터 스택에서 추출하기 때문입니다. 따라서 예시문제를 순서대로 큐에 push 하게 되면 아래 그림처럼 채워집니다. 자, 이제부터 알고리즘을 설계해봅시다. 1. 큐를 선언하여 입력되는 값을 큐에 넣습니다. 2. 우선 큐의 front 값에 대해서 처리해줍..
-
[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[..