네발로 코딩하는 포메라니안

문제 https://www.acmicpc.net/problem/10472 10472번: 십자뒤집기 당신에게 3x3 크기의 보드가 주어진다. 각각의 칸은 처음에 흰색 혹은 검은색이다. 만약 당신이 어떤 칸을 클릭한다면 당신이 클릭한 칸과 그 칸에 인접한 동서남북 네 칸이 (존재한다면) 검은색 www.acmicpc.net 풀이 과정 데이터는 3x3으로 총 9개의 수가 주어지므로, int하나로 비트마스킹을 사용했다. 특정 상태까지의 최단 시간을 구하는 문제이므로 BFS를 사용했고 검은색은 1, 흰색은 0으로 비트마스킹해서 전체 값이 0이면 모두 흰색이므로 종료하도록 했다. import java.io.BufferedReader; import java.io.InputStreamReader; import java...

1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/87946?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 풀이 과정 - bfs + 비트마스킹 - 입력이 8개이하이므로 비트마스킹(32bit)을 사용 class Solution { int n, answer; public void bfs(int k, int[][] dungeons, int visit, int cnt){ answer = Math.max(answer, cnt); for(int i=0; i

1. 문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LuHfqDz8DFAXc SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 2. 풀이과정 순서에 대한 순열에서 1)중간에 결과보다 작은 값이되거나 2)비트마스킹으로 불필요한 연산을 가지치기하는 것이 핵심이다. 예를 들어 N = 5일 때, 1~3까지 0~2번째 중에 하나씩 선택했다고 하면, 뒤에는 나머지는 3, 4번째 중에 선택한다. 이때 1~3까지 012, 021, 102, 120, 201, 210 순서가 가능한데, 이들 모두가 남은 것들의 최적값은 같다. 남아..

1. 문제 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 2. 풀이 과정 재귀 + 2차원 배열 DP문제라고 할 수 있다. 처음엔 순열을 돌려서 전체 탐색을 했는데 경우의 수가 16!으로 결국 시간 초과가 발생했다. 해결 방안이 떠오르지 않아, 질문을 보고 힌트를 얻어 풀 수 있었다. 이 문제의 key point는 2가지다. 1) 루프는 시작점이 어디든, 더해지는 값이 같기 때문에 값의 총합은 같다. => ..