택시짱의 개발 노트

링크 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 www.acmicpc.net 풀이 정사각형 4개가 연결되어 만들어진 도형에 들어가는 수의 합중 가장 큰 값을 구하는 문제 이다. 처음에는 모든 좌표를 ne..

링크 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2보다 크거나 같고, 1024보다 작거나 같은 2의 제곱꼴이다. 블록은 적어도 하나 주어진다. www.acmicpc.net 풀이 DFS로 풀었습니다. 각각의 DFS에 도달 하였을때 board를 저장해 주고 3중 반복문을 이용하여 위 오른쪽 아래 왼쪽으로 기울인 후 5번이 넘어가면 최대값을 찾아 출력 하였습니다. #include #include #include #include #include #i..

링크 https://programmers.co.kr/learn/courses/30/lessons/12929?language=cpp 코딩테스트 연습 - 올바른 괄호의 갯수 | 프로그래머스 올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미합니다. )(나 ())() 와 같은 괄호는 올바르지 않은 괄호가 됩니다. 괄호 쌍의 개수 n이 주어질 때, n개의 괄호 쌍으로 만들 수 있는 모든 가능한 괄호 문자열의 갯수를 반환하는 함수 solution을 완성해 주세요. 제한사항 괄호 쌍의 개수 N : 1 ≤ n ≤ 14, N은 정수 입출력 예 n result 2 2 3 5 입출력 예 설명 입출력 예 #1 2개의 괄호쌍으로 [ (()) programmers.co.kr 풀이 올바른 괄호의 갯수를 찾는 문..

링크 https://programmers.co.kr/learn/courses/30/lessons/12971 코딩테스트 연습 - 스티커 모으기(2) | 프로그래머스 N개의 스티커가 원형으로 연결되어 있습니다. 다음 그림은 N = 8인 경우의 예시입니다. 원형으로 연결된 스티커에서 몇 장의 스티커를 뜯어내어 뜯어낸 스티커에 적힌 숫자의 합이 최대가 되도록 하고 싶습니다. 단 스티커 한 장을 뜯어내면 양쪽으로 인접해있는 스티커는 찢어져서 사용할 수 없게 됩니다. 예를 들어 위 그림에서 14가 적힌 스티커를 뜯으면 인접해있는 10, 6이 적힌 스티커는 사용할 수 없습니다. 스티커에 적힌 숫자가 배열 형태로 주어질 때, 스 programmers.co.kr 풀이 스티커가 원형으로 연결이 되어 있고, 하나의 스티커를..

링크 https://www.acmicpc.net/problem/2169 2169번: 로봇 조종하기 첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다. www.acmicpc.net 풀이 로봇은 아래, 오른쪽 ,왼쪽 으로만 갈수 있다고 한다. 이때 맨 좌표의 맨 윗줄은 항상 오른쪽으로만 갈수 있기 때문에 첫줄은 오른쪽으로 값을 더해 준다. 이후 2번째 줄부터 N번째 줄까지는 x, y좌표에 도착 하려면 위, 오른쪽, 왼쪽에서 내려올수 있는 경우의 수가 있기 때문에 위에서 내려와 오른쪽으로 가는 값을 tmp[0] 배열에 저장하고 위에서 내려와 왼쪽으로 가는 값을 t..

링크 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번째 예시를 예로 들어보겠습니다. 알파벳의 위치에 따라 체크를 해주게 되..