코드 낙서장

문제 주소 : programmers.co.kr/learn/courses/30/lessons/49190 코딩테스트 연습 - 방의 개수 [6, 6, 6, 4, 4, 4, 2, 2, 2, 0, 0, 0, 1, 6, 5, 5, 3, 6, 0] 3 programmers.co.kr 문제 확인 문제를 단순화 하기 위해 방이 만들어 지는 경우의 수를 생각 해 봅시다. 1. 방문한 점을 다시 방문한다. 방문한 점을 기록해 재방문 하면 방의 개수를 늘립니다. 2. 방문한 선을 다시 방문한다. 방의 개수를 샐 때 작은 삼각형 형태로 잘린 방도 방으로 취급합니다. 대각선으로 이동할 때 방문한 선을 다시 방문하는 경우이므로 대칭인 대각선을 방문한 적이 있다면 방 개수를 하나 더 늘려야 합니다. 풀이 주어진 arrow의 크기는 ..

문제 주소 : www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순 www.acmicpc.net 문제 확인 dfs풀이, 연산자 우선순위가 동일 하기 때문에 단순 완전 탐색으로 풀 수 있다. 풀이 연산자 우선순위가 없기 때문에 현재 식을 계산하면 스텍 top의 값만 변경, 계산하지 않으면 스택에 push 합니다. 괄호 중첩을 빼기 위해 전 단계에서 bool 변수 추가합니다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 ..

문제 주소 : www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 문제 확인 dfs 형태로 문제풀이 최소 개수를 찾는 문제이기 때문에 놓을 사다리 수를 0개부터 4개까지 순서대로 탐색합니다. 풀이 놓을 사다리 수를 0개부터 탐색하며 가능한 경우를 찾는 즉시 출력합니다. dfs, 의미없는 탐색을 줄이기 위해 세로 방향 탐색 시 의미가 중복되는 사다리는 넘어갑니다. //while(!a[i][j - 1] && !a[i][j + 1]) i++; 코드 1 2 3 4 5..

문제 주소 : www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제 확인 간단하게 dfs 그래프 탐색으로 해결할 수 있는 문제 아래 그림과 같이 최대 4번의 깊이 탐색으로 해결 할 수 있습니다. ㅜ 형태의 모양은 dfs를 통해 탐색하기 까다로우므로 따로 함수를 만들어 탐색하도록 합니다. 풀이 처음 배열을 초기화 할 때 최대값을 미리 저장해두고 탐색 시 기대값 계산에 사용합니다. 이를 통하여 가지치기를 진행합니다. 탐색 시 이전 방향으로 돌아가는 것을 막기 위..

문제 주소 : www.acmicpc.net/problem/12094 12094번: 2048 (Hard) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 문제 확인 2048(easy) 문제와 같은 방식, 최대로 움직일 수 있는 횟수가 10번이다. 완전 탐색으로 구현을 하면 시간초과가 나기 때문에 탐색에서 가지치기를 해 주어야 한다. 풀이 가지치기 조건 1. 배열 값이 변화가 없는 경우 2. 현재 최대값 이상으로 변화할 수 없는 경우 앞으로 n번 움직일 수 있을 때 매번 합처지는 경우를 생각하면 기대값은 (2^n * 현재..