분류 전체보기
BaekJoon 2096번: 내려가기(C++)
https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 풀이법 1) 메모리의 제한이 4MB이므로 최소한의 배열을 이용하여 풀어야 하는 DP 문제이다. max와 min 모두 2차원의 3x2배열을 만들어서 최대 값과 최솟 값을 구하였다. 2) 자세한 이해는 코드를 보며 공부하는 것이 더 효율적이리라 생각한다. (1차원 배열로는 min max 값을 정확하게 구할 수 없으므로 나머지 연산자를 활용하여, 최대와 최솟값을 구해두었다.) 점화식을 잘못 세운 분들을 위한 Hidd..
Programmers Level 3: 멀리 뛰기
https://programmers.co.kr/learn/courses/30/lessons/12914# 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr 풀이법 1) DP를 활용하면 쉽게 풀 수 있는 문제이다. (queue를 활용하여 풀 수 있으나 시간 초과에 유의해야 한다.) 2) 개인적으로 kakao 프로그래머스 level2 문제보다 쉽다고 생각했기에, 오래 걸리지 않고 문제를 풀 수 있었다. arr[1]=1 arr[2]=2 arr[3]=3 arr[4..
Programmers Level2: 메뉴 리뉴얼
https://programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 풀이법 1) Map 자료형과 조합(Combination)을 이용한 구현 문제이다. 2) map 자료형에 몇 번의 해당 값이 나왔는지를 확인할 수 있도록 하고 course 배열 안의 값에 따라 이를 확인하여 result를 만드는 과정이 중요한 부분이었다. string s = orders[j]; sort(s.begin(), s.end()); vector ind; fo..
Programmers Level 2: 뉴스 클러스터링(C++)
https://programmers.co.kr/learn/courses/30/lessons/17677 코딩테스트 연습 - [1차] 뉴스 클러스터링 뉴스 클러스터링 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브 programmers.co.kr 풀이법 1) 문자열을 활용한 교집합 합집합 문제이다. 2) char 값을 정제하여 string에 붙이기 위해서 string.push_back 함수를 사용할 수 있다는 것을 익힐 수 있었으며, 교집합 계산 시에 break 함수를 사용하지 않으면 정답을 얻을 수 없었다. #include #include #include using namespac..
Programmers Level 2: 카카오프렌즈 컬러링 북
https://programmers.co.kr/learn/courses/30/lessons/1829 코딩테스트 연습 - 카카오프렌즈 컬러링북 6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5] programmers.co.kr 풀이법 1) BFS를 활용하여 문제를 해결했다. DFS를 쓰는 것이 더 좋을 수도 있으나, 손에 익는 방식으로 문제를 빠르게 푸는 연습을 통해 programmers 툴을 익혀보았다. 2) visited 배열을 선언하여 방문한 곳을 표시하고, 같은 색으로 이뤄진 공간을 확인하기 위해 상하좌우의 배열을 활용하였다. int vx[4]={1,0,0,-1}; int vy[4..
BaekJoon 1238번: 파티(C++)
https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 풀이법 1) 다익스트라 알고리즘을 사용하면 풀 수 있는 문제이다. 2) From배열과 To배열로 나누어서, 방문할 마을까지의 최소거리 + 다시 돌아가는 최소거리를 최종 배열일 dist에 넣고 가장 긴 것을 찾으면 되는 문제이다. 3) 다익스트라 알고리즘을 알고 있다면 쉽게 풀 수 있으나, 모르는 경우 어려울 수 있는 문제이기에 기초 개념을 꼭 익히는 것을 추천한다. ..
Programmers Level 2: 방문 길이(C++)
https://programmers.co.kr/learn/courses/30/lessons/49994# 코딩테스트 연습 - 방문 길이 programmers.co.kr 풀이법 1) 단순히 구현으로 풀 수 있는 문제이다. 2) 3차원 방문 배열을 생각해 내어서 문제를 해결하였다. (3차원 배열을 활용하지 않을 시에 test case 8~20번이 막히는 현상이 발생한다.) 0: 왼쪽, 1:위쪽, 2:오른쪽, 3:아랫쪽 으로 임의로 정의했다. 3) 보다 편한 구현을 위해 제일 좌측 우측 상단을 (0,0)으로 재 정의하여 문제를 해결했다. 대표적인 예시를 들자면, L의 경우 visited[x][y-1][2]=true; visited[x][y][0]=true; 기존의 위치에서는 좌측으로 이동하지만, 새롭게 이동할 ..
Programmers Level 2: 땅따먹기(C++)
https://programmers.co.kr/learn/courses/30/lessons/12913 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟 programmers.co.kr 풀이법 1) DP를 활용해서 푸는 것이 중요한 문제이다. 2) DFS나 For문을 이용해서 문제를 풀 경우 시간 초과가 발생한다. 3) 단순히 각 행 별로 가장 큰 값을 가져 오는 경우 1 2 3 5 3 2 1 100 1 1 2 3 같은 배열의 경우 5+100+3과 같은 규칙에 어긋나는 경우가 발생하므로 arr 배열을 새로 만들고 여기에 현재..
Programmers Level 2: 멀쩡한 사각형(C++)
https://programmers.co.kr/learn/courses/30/lessons/62048?language=cpp 코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 programmers.co.kr 풀이법 1) 단순한 구현 문제이다. 2) y증가량/x증가량을 이용하여 기울기를 구하고, 1부터w까지의 값을 확인하여 식을 만들었다. 이 후 값보다 작은 정수들을 최종 answer에 더 해주어 문제를 해결하였다.(대칭이 존재하니 x2는 필수!) -> double 대신 float를 사용하게 되면 완전한 정답을 얻을 ..
BaekJoon 11727번: 2xn 타일링 2(C++)
https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 풀이법 1) DP를 활용하여 푸는 문제이다. 점화식을 구하는 것이 중요하다. 2) a1=1, a2=3, a3=5, a4=11 임을 시도한다면 알 수 있다. 기존의 배열에 2x1을 더하는 것과, 1x2 혹은 2x2를 더하는 경우를 나누어서 생각해 주면 된다. arr[n-1]에 2x1을 더하는 경우에 arr[n]을 만들 수 있다. arr[n-2]에 1x2를 더하는 경우 또한 arr[n]을 만들 수 있다. arr[n-2]에 2x2를..