택시짱의 개발 노트

링크 https://programmers.co.kr/learn/courses/30/lessons/43105 코딩테스트 연습 - 정수 삼각형 | 프로그래머스 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 풀이 삼각형의 이동 방향은 왼쪽, 오른쪽으로 이동 한다. 이때 왼쪽 끝과 오른쪽 끝에 있는 정수는 항상 바로 위 한개의 정수를 통해서 올수 있고 나머지 가운데 있는 정수는 왼쪽 오른쪽에서 올수 있기 때문에 조건을 3가지로 나누었다. #include #include #include #include using namespace std; long long dp[550][550]; int solution(vector tri..

링크 https://programmers.co.kr/learn/courses/30/lessons/43104 코딩테스트 연습 - 타일 장식물 | 프로그래머스 대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개의 나선 모양처럼 점점 큰 타일을 붙인 형태였다. 타일 장식물의 일부를 그리면 다음과 같다. 그림에서 타일에 적힌 수는 각 타일의 한 변의 길이를 나타낸다. 타일 장식물을 구성하는 정사각형 타일 한 변의 길이를 안쪽 타일부터 시작하여 차례로 적으면 다음과 같다. [1, 1 programmers.co.kr 풀이 N번째 도형의 크기는 N-1 번쨰 + N-2 번째 도형의 합..

링크 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다. www.acmicpc.net 풀이 여러 단어가 주어졌을때 단어를 숫자로 변환한 값의 최대 합을 구하는 문제이다. 문제를 풀기전에 생각 해봐야 할것은 1. 알파벳이 어느 위치에 있는지 2. 알파벳이 얼마나 나오는지 위의 두가지를 이용하면 문제를 풀 수 있다. 2번째 예시를 예로 들어보겠습니다. 알파벳의 위치에 따라 체크를 해주게 되..

링크 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동 www.acmicpc.net 풀이 시작점에서 끝점까지 이동하는데 걸리는 최소 시간을 구하는 문제이다. 저는 최소를 보자마자 BFS가 떠올랐고, 여기서..

링크 https://www.acmicpc.net/problem/3190 3190번: 뱀 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따 www.acmicpc.net 풀이 어렸을때 했던 뱀 게임처럼 사과를 먹으면 길이가 늘어나고 꼬리나 벽에 닿으면 끝나는 그런 게임과 같은 문제이다. 뱀을 구성하기 위해서..

링크 https://programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 | 프로그래머스 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 풀이 간단한 BFS로 풀 수 있다. 일단 양방향 그래프를 만든 후 출발지에서 도착한 위치와 거리를 저장할수 있는 구조체를 만들었다. 이전 노드에서 다음 노드에 도착 하였을때 거리를 1 증가 시켜 주었고 방문 여부를 확인하기 위해서 visited배열을 모두 -1로 초기화 하고 방문한 위치를 기억 하기 위해 visited을 거리만큼 갱신 했고 가장 큰 거리와 visited배열과 비교하여 거장 먼 노드의 갯수를 찾을..

링크 https://programmers.co.kr/learn/courses/30/lessons/43237 코딩테스트 연습 - 예산 | 프로그래머스 국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것입니다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있습니다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정합니다. 1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정합니다. 2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 programmers.co.kr 풀이 정해진 예산의 총액 이하에서 가능한 최대의 총 예산을 구해야 한다...

링크 https://programmers.co.kr/learn/courses/30/lessons/42861 풀이 n개의 섬 사이에 다리를 건설하는 비용이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 최소 비용을 찾아야 한다. 방법을 생각해 보면 섬과 섬사이의 비용이 가장 작은순서대로 정렬하여 연결하면 되지만 이미 연결된 섬을 다시 연결 하면 안되고 건너 뛰어야 된다는 생각을 해볼 수 있습니다. 이때 필요한 알고리즘은 크루스칼(Kruskal)알고리즘을 이용할 수 있습니다. 크루스칼 알고리즘은 탐욕적인 방법을 이용하여 그래프의 모든 정점을 최소 비용으로 연결하는 방법입니다. 1. 최소비용으로 연결된 노드를 찾기 -> priority_queue를 이용 2. 섬과 섬이 이미 연결되어 있..