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

1. 문제 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 2. 풀이 과정 한 장소에서 여러 곳으로 뻗어나갈 수 있기 때문에, 단순 dfs나 bfs로는 풀리지 않는다. 한 장소에 방문하면, 지금까지 방문한 장소를 모두 고려해 갈 수 있는 장소를 탐색한다. 방문한 장소를 찾아서 4방위 탐색해서 dfs로 들어가면 된다. +) 중복 방지를 위해 visited 배열을 사용한다. 비트마스킹으로 경로 방문 체크를 한다. import java.io.*; pub..

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 2. 풀이과정 dfs문제 + 문자열 정렬 1) 문자열을 정렬하기 위해서 지역 이름들을 하나의 문자열로 concat해서 사용 2) 사전순 정렬 3) 공항 이름이 모두 3자리이므로, 3개씩 잘라서 배열에 담아서 반환 import java.util.*; class Solution { static int N; static A..

1. 문제 https://programmers.co.kr/learn/courses/30/lessons/43236 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 2. 풀이과정 0~distance 범위를 이진탐색을 통해 답을 찾는다. 매 loop마다 중간값보다 작으면 합치고, cnt를 센다. 1) cnt가 n개 이상이면, 값을 줄여야 하므로 right = m-1 2) cnt가 n개 이하면, 값을 늘려야 하므로 left = m+1 3) cnt == n이 되는 중간값은 여러 개 있을 수 있다. 그 중 ..

1. 문제 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 2. 풀이과정 1) 시작점 = 출발점이므로, 출발점은 어디든 결과는 같다. 따라서 시작점은 0으로 고정했다. 2) 순서에 따라 결과가 달라지는 순열 문제이다. 그리고 마지막에 도착지 => 출발지까지 값도 고려해주는 걸 잊지말자. import java.io.*; import java.util.*; public class Boj10971 { st..

1. 문제 https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 2. 풀이과정 경우의 수 문제에 대각선의 특징을 이용하는 아이디어가 필요한 문제다. 우선, 모든 경우의 수를 고려하면 시간 복잡도는 O(2^(N*N))이고, 최대 2^100이므로 시간 초과가 난다. x+y가 짝수인 집단과 홀수인 집단을 나눈다. 이들은 서로 절대 같은 대각선 상에 있을 수 없기 때문에, 독립적으로 계산한 후 결과들을 더해주면 되는 것이다. 나눠보면, 체크보드처럼 그려지는 것을 확..

1. 문제 https://www.acmicpc.net/problem/3954 3954번: Brainf**k 인터프리터 각 테스트 케이스에 대해서, 프로그램이 종료된다면 "Terminates"를, 무한 루프에 빠지게 된다면 "Loops"를 출력한다. 무한 루프에 빠졌을 때는, 프로그램의 어느 부분이 무한 루프인지를 출력한다. ([ www.acmicpc.net 2. 풀이과정 문제도 문제지만, 이해가 어려웠던 문제였다.. 헷갈렸던 부분을 정리해보면, 1) - : -1이 되는 순간 255로! 즉 숫자는 0~255까지만 취급한다. 2) 명령 실행 횟수가 50_000_000초과하면, 현재 상태는 무한 루프를 돌고 있는 것이다. 정상 종료는 그 전에 끝나는 경우다. 해결 방법 : 무한 루프 외엔 일반 계산이다. 무한..

1. 문제 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 2. 풀이 과정 필요한 데이터를 만들어서 푸는 MST문제이다. MST 문제 해결 방법은 Kruskal과 Prim이 있는데 정점 기준으로 데이터를 기록했기 때문에, Prim을 사용했다. 1. 섬마다 번호 붙이기 2. 섬과 섬까지 거리 구하기 가로, 세로 각각 for문 돌면서 최솟값 갱신시켜나감 3. MST 구하기 *cycle없이 다 이어진, cost가 최소인 그래프 ..

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://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWL2vlPKMlQDFAUE SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 2. 풀이과정 *라이브러리는 Scanner외에 사용할 수 없게 되어있다. 숫자를 담을 배열은 최대 999까지 있으므로 크기를 1000으로 잡아준다. 가능한 숫자가 0, 1이라면 10, 11, 100, 110, 101, 111를 사용 가능한 숫자로 넣어줄 것이기 때문이다. 이때 10같은 경우는 2번, 100같은 경우는 3번 터치해야 하며, 이 값은 values에 기록한다. values에서 ..

1. 문제 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 2. 풀이 과정 소수 구하기는 에라토스테네스의 체를 사용했고, 연속된 수의 합은 dp를 활용했다. 2부터 N까지 보면서, 소수가 보이면 values배열에 더한 값을 저장한다. 예시로 N=15일 때를 생각해보면, i=2 values = [2] i=3 values = [5, 3] i=4 values = [9, 7, 4] i=5 values = [14, 12, 9, 5] i=6 values = [20, 18, 15, 11, 6] => result++; ... 15보다 큰 값은 N(15)가 될 가능성이 없으므로,..