밤이 블로그

BOJ#14499 주사위 굴리기 * 문제https://www.acmicpc.net/problem/14499 오늘 만들어진 따끈따끈한 문제입니다. 작년 하반기 삼성 SW 역량테스트 문제와 거의 흡사한데요,,제 소스가 도움이 되면 좋겠습니다. * 풀이 1. 주사위 전개도를 표현하는 자료구조를 만든다.2. 회전하는 함수를 만들고, 회전할때마다 주사위 전개도를 갱신해준다.3. 문제의 조건에 따라 시뮬레이션한다. * 나의 소스https://github.com/stack07142/BOJ/blob/master/BOJ%2314499_RollingDice/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.Input..

BOJ#7569 토마토 * 문제https://www.acmicpc.net/problem/7569 * 풀이bfs 탐색 과정에서 상, 하, 좌, 우 뿐만 아니라 위, 아래도 추가해야 하는 문제입니다. 비슷한 문제 : BOJ#7576 토마토 https://www.acmicpc.net/problem/7576 (초등부 문제가 고등부 문제보다 어렵다..왜일까요 ?.? ) * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%237569_Tomato/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util...

BOJ#2667 단지번호붙이기 * 문제https://www.acmicpc.net/problem/2667 * 풀이dfs난이도 : 하 추천 문제 (2667번 다음에 풀어보면 좋을 문제) : 2146번 - 다리 만들기 https://www.acmicpc.net/problem/2146 * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%232667_Numbering/src/Main.java import java.io.*; import java.util.ArrayList; import java.util.Collections; /** * BOJ#2667 단지번호붙이기 * https://www.acmicpc.net/problem/2667 */ public class..

BOJ#2589 보물섬 * 문제https://www.acmicpc.net/problem/2589 * 풀이 모든 육지를 대상으로 bfs 탐색을 각각 수행해주면 됩니다.주의할 점으로는 각 탐색 시 visited 배열을 초기화해줘야 합니다. * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%232589_TreasureIsland/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTok..

BOJ#2146 다리 만들기 * 문제https://www.acmicpc.net/problem/2146 * 풀이1. dfs 섬 구분하기2. bfs 섬 간 최단 거리 구하기 문제 추천 (2146번을 풀기전에 보면 좋을 문제) :2667번 - 단지번호 붙이기 https://www.acmicpc.net/problem/2667(섬 개수를 세는 문제)* 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%232146_MakeBridge/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; /** *..

BOJ#2666 벽장문의 이동 * 문제https://www.acmicpc.net/problem/2666 * 풀이1. 문제 이해벽장문을 이동을 열려있는 문이 이동한다는 것으로 바꿔서 생각해봅시다. 훨씬 편하게 문제를 이해할 수 있습니다.열려있는 문은 항상 2개 뿐이므로 하나를 F, 나머지를 S라고 해봅시다. 열려있는 문이 이동하므로 2가지 경우가 발생합니다. 1) F가 이동하는 경우2) S가 이동하는 경우 2. 풀이 설계이 문제는 벽장문의 사용 순서에 따라 탐색이 진행되고, 완전 탐색이 되어야 합니다.이 과정에서 필요한 것, 저장시켜야 하는 것, 변화하는 것들을 이용하여 dp를 정의하고 점화식을 세워보면 (정의)dp[pos1][pos2][idx] : 열린문 F의 위치가 pos1이고 열린문 S의 위치가 po..

BOJ#5557 1학년 * 문제https://www.acmicpc.net/problem/5557 * 풀이- dp[i][sum] : i번째까지 진행했을 때, 합이 sum인 경우의 개수- 구하는 값은 dp[N-2][A[N-1]]- solve(idx, sum) : dp[idx][sum]을 구하는 함수 * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%235557_FirstGrader/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * BOJ#5557 ..

순열 (PERMUTATION) - 사전순 이전 글 : 순열 (PERMUTATION) http://stack07142.tistory.com/24 순열을 사전순으로 만들려면 어떻게 해야 할까 [1, 2, 3, 4] 순열이 있을 때,---------------------------------------------------------[1, 2, 3, 4] [1, 2, 3, 4][2, 1, 3, 4][3, 1, 2, 4][4, 1, 2, 3]---------------------------------------------------------[1, 2, 3, 4][1, 2, 3, 4][1, 3, 2, 4][1, 4, 2, 3][2, 1, 3, 4][2, 1, 3, 4][2, 3, 1, 4][2, 4, 1, 3]..

BOJ#2098 외판원 순회 * 문제https://www.acmicpc.net/problem/2098 * 풀이dp 문제입니다. (주의점, 힌트)1. 사이클이므로 어느 점을 시작점으로 잡아도 상관없다.2. 마을 방문 여부를 매개변수로 넘겨주기 위해서는 ? 비트마스크를 사용하자.3. 시간 복잡도 : O(N^2 * 2^N) * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%232098_TSP/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.St..

BOJ#1182 부분집합의 합 * 문제https://www.acmicpc.net/problem/1182 * 풀이처음에는 조합을 이용해서 풀었습니다. (160ms)집합에서 1개를 고르는 경우, 2개를 고르는 경우, ...., N개를 고르는 경우 두번째 풀때는 집합의 각 원소의 2가지 경우에 대해(고르는 경우, 고르지 않는 경우)재귀 함수 호출로 답을 구하였습니다. (76ms) 주의할 점 : S가 0인 경우에는 공집합도 카운트 될 수 있음 * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%231182_SumOfSubsets/src/Main.java import java.io.*; import java.util.StringTokenizer; /** * BO..