Coding_Test_C++
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를..
BaekJoon 1043번: 거짓말(C++)
https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 풀이법 1) 그래프의 개념에서 접근하여, 연결된 값들을 확인하는 것이 중요하다. 2) 진실을 아는 사람이 참가한 파티에 있는 모든 사람은 주인공인 지민이가 거짓말을 하는 것을 알게 된다. 3) visited배열과 while문을 활용하여 더 이상 새로운 값으로 갱신 되지 않았을 때, 최종 결과를 구하는 것이 중요하다. (값이 바뀌는 과정에서 중간 결과를 구하려 하면 오답이 나올 수 있다.) #include #..
BaekJoon 9465번: 스티커(C++)
https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이법 1) 단순 반복문으로는 시간 초과가 발생하기에 DP를 이용해서 푸는 문제이다. 2) 점화식을 세울 때, ans 배열 규칙을 찾아야 했다. ans[0][i] = max(ans[1][i-2]+arr[0][i],ans[1][i-1]+arr[0][i]); ans[1][i] = max(ans[0][i - 2] + arr[1][i], ans[0][i - 1] + arr[1][i]); 새로 ..
BaekJoon 11660번: 구간 합 구하기 5(C++)
https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 풀이법 1) 단순 반복문으로는 시간 초과가 발생하기에 DP를 이용해서 푸는 문제이다. 2) 각 행의 합을 구해두고 이를 활용하는 방식으로 문제를 해결했다. 3) 좌표가 들어오는 경우 점화식을 활용하여, sum 값을 구해 주었다. for (int i = 0; i > x1 >> y1 >> x2..