문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 이 문제는 숫자와 공백으로 이루어진 문자열에서 숫자를 뽑고, 최댓값과 최솟값을 찾는 문제이다. C++에서는 파이썬처럼 split 함수를 사용할 수 없기 때문에, split함수를 직접 구현하거나, 문자열에서 특정 문자를 구분자로 활용해 부분적인 문자열을 추출하는 방법으로 라이브러리와 getline을 활용해 공백을 분리해줄 수 있다. #include #include #include #include using namespace std; int main(){ // 공백 분리할 문자열 선언 str..
문제 링크 5569번: 출근 경로 상근이가 사는 도시는 남북 방향으로 도로가 w개, 동서 방향으로 도로가 h개 있다. 남북 방향 도로는 서쪽부터 순서대로 번호가 1, 2, ..., w로 매겨져 있다. 또, 동서 방향 도로는 남쪽부터 순서대 www.acmicpc.net 문제 풀이 이번 문제는 최단거리 경로 찾기이다. 추가적으로 제약사항이 존재하는데, "이 도시는 교통 사고를 줄이기 위해서 교차로를 돈 차량은 그 다음 교차로에서 다시 방향을 바꿀 수 없다. 즉, 교차로에서 방향을 바꾼 후, 1 블록만 이동한 후 다시 방향을 바꿀 수 없다." 라고 한다. 따라서 이 경우, 동쪽과 북쪽(x, y 방향이라고 하자)방향으로만 이동해 2가지의 방향이라고 생각할 수 있지만, x방향으로 바꿀 수 있는지의 유무, y방향으..
문제 링크 2502번: 떡 먹는 호랑이 첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤ A ≤ B)가 존재한다. www.acmicpc.net 문제 풀이 이번 문제는 DP 문제이다. "예를 들어 첫째 날에 떡을 1개 주었고, 둘째 날에는 떡을 2개 주었다면 셋째 날에는 1+2=3개, 넷째 날에는 2+3=5개, 다섯째 날에는 3+5=8개, 여섯째 날에는 5+8=13개를 주어야만 무사히 산을 넘어갈 수 있다."라는 문구에서, 피보나치 수열의 향기가 느껴졌다. 첫째 날과 둘째 날을 A, B라고 했을 때, 두 값을 구하기 위해 피보나치 수열을 통해 규칙을 찾을 수 있었다. 첫째 날 : A ..
문제 링크 1577번: 도로의 개수 첫째 줄에 도로의 가로 크기 N과 세로 크기 M이 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 둘째 줄에는 공사중인 도로의 개수 K가 주어진다. K는 0보다 크거나 같고, 50보다 작거나 같은 자 www.acmicpc.net 문제 풀이 이 문제는 [0, 0]에서 최단경로로 [N, M]에 도달하기 위한 방법의 수를 구하는 문제이다. 다들 한번씩 경로에 1을 표시해서 총 몇가지의 길이 존재하는지 문제를 풀어봤을 것이다. 이것을 알고리즘으로는 DP로 풀 수 있다. 공사중인 도로 만약 [1, 1]인 지점으로 가기 위해서는 최단거리이므로 무조건 [0, 1] 혹은 [1, 0]을 통과해야 한다. 따라서 [1, 1]까지의 경로는 [0, 1]까지의 경로와 [1, 0]까지의..
문제 링크 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 문제 풀이 이 문제는 두 문자열 사이에 공통적으로 존재하는 부분 문자열 중, 가장 길이가 긴 문자열을 찾는 문제이다. 이 문제를 풀기 위해서는 LCS 알고리즘을 사용해야 한다. LCS 알고리즘 이 알고리즘은 길이가 가장 긴 부분 문자열을 문자열1의 길이 * 문자열2의 길이 만큼의 시간복잡도로 찾을 수 있다. 문자열1의 i번째 문자와 문자열2의 j번째 문자가 같다면, 문자열1의 i-1번째 문자와 문자열2의 j-1번째 문자 배열의 결과에 1을 ..
문제 링크 4883번: 삼각 그래프 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 그래프의 행의 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N개 줄에는 그래프의 i번째 행에 있는 정점의 비용이 www.acmicpc.net 문제 풀이 이번 문제는 DP 문제이다. 이 문제의 경우, 가장 위쪽 가운데 정점에서 가장 아래쪽 가운데 정점으로 가는 최단 경로를 찾아야 한다. 규칙 찾기 그림을 보면, 각 정점 사이의 간선들은 화살표로 표시되고 있다. 일방통행으로, 반대로 갈 수는 없기 때문에, 각각의 정점 별 최선의 경로를 찾아볼 수 있다. 먼저, 3열의 왼쪽 정점들은 위 그림과 같이 두 개의 경로에서 내려올 수 있다. 따라서 두 경로 중 낮은 비용의 경로를 선택하..
문제 링크 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 문제 풀이 이번 문제는 DP 문제이다. DP 문제는 규칙성을 찾는것이 중요하다고 생각했기 때문에, 자릿수를 1부터 늘려가면서 규칙을 찾아보았다. 규칙 찾기 입력값이 '1'일 경우, [ 1 ] 만 가능하기 때문에 답은 1일 것이다. 입력값이 '11'일 경우, [ 1, 1 ], [ 11 ] 이므로 답은 2이다. 입력값이 '111'일 경우, [ 1, 1, 1 ], [ 1, 11 ], [ 11, 1 ] 로 답은 3이다. 입력값이 '1111'일 경우, [ 1, 1, 1, 1 ]..
