본문 바로가기

시뮬레이션33

[자바] 백준 12100 - 2048 (Easy) (boj java) 문제 : boj12100 (상당히 귀찮은편인) 단순 시뮬레이션 문제이다. 최대 5번 이동이라고 했으므로, 처음 상태에서 상하좌우 4방향으로 움직이는걸 최대 5번 반복하면 된다. 즉, 최대 4^5번으로 모든 경우를 확인할 수 있다. 이 때 각 방향마다 NxN 칸의 모든 것들을 해당방향으로 움직여야 한다고 볼 수 있으므로 대략 O(N^2 x 4^5)의 시간복잡도가 된다. 그럼 남은건 상하좌우 방향으로 움직인다고 할 때, 문제에서 제시된 방법대로 동작만 되도록 시뮬레이션을 구현해주면 된다. 이 때 주의점은 예를들어 아래와 같은 경우를 보자. 2 0 0 2 0 0 2 0 0 위와 같은 경우 우측 방향으로 모두 이동시킨다고 했을 때, 우측으로 모두 붙어야 할 것이다. [A] 0 2 0 0 2 0 0 2 0 [B].. 2022. 7. 20.
[자바] 백준 1835 - 카드 (boj java) 문제 : boj1835 이걸 어찌 구해야할지 상당히 난감해보일 수 있다. 그럼 반대로 이미 출력의 답을 알고 있다고 할 때, 이 문제에서 제시된 방법대로 진행할 경우 정말 1,2,3,... 이 순서대로 뜰지 확인해볼 수 있을까? 물론 문제에서 제시된대로 코드를 구현만 하면 확인해볼 수 있다. 그렇다면, 이미 답을 알고있다고 가정하고 시뮬레이션을 돌려보자. 그리고 뽑히는 순서대로 1,2,3... 을 넣어준 후, 답의 출력순서대로 다시 짜맞춰주면 된다. 무슨 말이냐면, 아래 그림을 봐보자. 그리고 자바에서 클래스는 주소값을 기준으로 저 링크를 연결해두기 좋다. 그러니 ?로 된 카드들을 배열에 넣어두고, 해당 값들을 덱에다가 미리 넣어둔다(위 그림의 '1'에서 위쪽 파란거 3개가 배열, 아래쪽이 덱에 들어간걸.. 2022. 6. 30.
[자바] 백준 12873 - 기념품 (boj java) 문제 : boj12873 리스트를 하나 두고 미리 1부터 N까지를 순서대로 넣어놔보자. 그럼 이제 단계를 A라고 할 때, 1단계부터 N-1단계까지 A^3번을 리스트 순회하다가 해당 횟수에서 제외시키는 식으로만 진행하면 된다! 다만 이 경우 O(N*N^3) = O(N^4) 이라서 시간초과를 피하기 힘들 것이다. 약간만 생각해보면, 예를들어서 현재 6명이 리스트에 남아있고 4001단계이다. 그럼 4001 실제로 6명을 가지고 약640억번 돌아볼게 아니고, 어차피 한바퀴 돌면 제자리일테니 640억을 6으로 나눈만큼만 돌면 된다! 4001^3 % 6 = 5이다. 이런식으로 A단계에 대해 'A^3 % [현재남은수]'를 계산해서 그만큼만 움직이면 된다. 그럼 총 O(N^2)으로 줄어든다. 추가로 int가 연산이 더.. 2022. 6. 30.
[자바] 백준 21756 - 지우개 (boj java) 문제 : boj21756 배열에 실제로 값을 넣어보고, 문제에서 제시된 방법대로 시뮬레이션을 돌리듯 실제로 동작하도록 구현해보면 쉽게 풀 수 있다. 그냥 배열로 해도 되지만, 이하 코드는 ArrayList를 가지고 해봤다. 이 경우 index값은 0부터 시작되므로 index 기준으로는 짝수번을 제거해야 한다. 처음에 1부터 n까지를 ArrayList에 넣는다. -> ArrayList 하나를 더 만들고 index 번호 기준으로 홀수번호들을 새로 만든 곳에 담는다. -> 기존 ArrayList와 바꿔치기를 한다. 위의 과정을 값이 1개만 남을 때 까지 계속하면 된다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; im.. 2022. 6. 16.
[자바] 백준 24508 - 나도리팡 (boj java) 문제 : boj24508 그리디로 생각해보자. 결국 최소 횟수로 이동하면서 K개씩을 만들려면 더 빠르게 없어질 수치가 큰 값에다, 더 느리게 없어질 수치가 작은 값을 밀어넣어야 한다. 따라서 입력으로 들어온 N개의 입력값 Ai 들을 정렬해보자. 그리고 작은 값을 큰 값에 직접 밀어넣으면서 K개를 만들면 없애는 식으로 시뮬레이션을 진행하면 풀 수 있다. 약간의 그리디가 들어간 시뮬레이션 문제로 구현력(?)이 좋다면 어렵지 않게 풀 수 있다. 이하의 코드를 참고해보자. 다만 주의해야 할 예시 2가지를 들어보겠다. [1] 3 2 10000 0 0 0 [2] 5 2 10000 1 0 0 [1] 처럼 모두 0인 경우엔 이미 조건을 만족하므로 별다른 처리없이 YES를 출력해줘야 한다. [2] 처럼 하나만 0이 아닌.. 2022. 6. 8.
[ABC252] C - Slot Strategy (AtCoder Beginner Contest 252 in Java) 문제 : abc252_c arr[a][b]는 a라는 수(016(=6+10)으로 눌러야 하므로 16초가 필요하다. arr[1]의 경우엔 0->1->7이므로 7초, arr[2]는 0->2->9이므로 9초... 이런식이다. 이 중 가장 작은 것은 arr[8]로 0->2->6으로 6초가 된다. 이런식으로 arr[a][b]를 구해둘 시 arr[0]~arr[9] 각각의 초를 구하고, 그 중 가장 작은 초를 출력해주면 된다. 코드 : github ... private int getTime(int[] cnt) { int max = 0; for (int i = 0; i < 10; i++) { int calc = i+(cnt[i]-1)*10; max = Math.max(calc, max); } return max; } p.. 2022. 5. 22.
[자바] 백준 25200 - 곰곰이와 자판기 (boj java) 문제 : boj25200 에디토리얼과도 아예 다른 풀이이고, 난이도 기여의 다른 사람들 의견과도 다른 방식인걸로 보아 상당히 독특하게 푼 것 같다. 당연히 N개의 음료수에 대해 M번의 차원 이동을 실제로 해보려면 현재 이동할 차원 U, V(3, 3->2 라면 1->3으로 차원3에는 1과 3의 두개가 있을 것이다. 따라서 3->2는 3만 이동하면 안되고 1과 3을 둘 다 이동해야 한다. 그러므로 O(NM)의 시간복잡도가 필요하므로 통과할 수 없다. 그렇다면, 첫 시작을 N개의 LinkedList로 해보면 어떨까? LinkedList[N+1] 짜리에 각각 LinkedList[1]엔 1만 있고, [2]엔 2만 있고, ... [N]엔 N만 두고 시작해보자. 그럼 M개의 쿼리에 대해 U->V로 빠르게 Linked.. 2022. 5. 16.
[자바] 백준 1110 - 더하기 사이클 (boj java) 문제 : boj1110 문제에서 요구하는 대로 구현을 하면 된다. 과정을 정리하면 다음과 같다. 제시된 대로 시뮬레이션 하면서 몇 회 진행됬는지 세기만 하면 되므로 별다른 알고리즘적인 지식은 필요없다. 일반적으로 숫자 그 자체로 연산해서 구하는 방법과, 문자열로 보고 구하는 방법이 있을 것이다. 이하 코드1과 코드2에 두 가지 방법을 모두 구현했으니 코드를 참고해서 구현해보자. 코드1 (정수로 구하기) : github import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class Main { private voi.. 2022. 5. 11.
백준 15492 자바 - 뒤집기 (boj 15492 java) 문제 : boj15492 바로 직전에 풀었던 19585번 '전설'의 경우 시도횟수가 18번이었는데, 이번엔 29번이었다 ㅂㄷㅂㄷ... 이번에 포기안하고 계속 시도해본 이유는, 테스트케이스 랜덤 생성기로 400만개를 돌려보니 괜찮은 시간이 나왔기 때문이었다. 결론적으로는 '1 2 3 1 2 3 1 2 3 ...'와 같은 케이스를 제대로 못잡아 내서 시도횟수가 많아졌다(랜덤 생성기라 그런 케이스가 안나오니까) 풀고 보니 다른 분들은 해싱과 KMP 등으로 풀었다는데, KMP까진 적용이 이해가 됬는데 해싱으로 푼다니 생소하다. 해싱은 'Lexicographically Minimal Cyclic Shift' 라는걸 쓰면 된다고 한다. 처음들어본다. 내 경우엔 실력이 부족하니 몸으로 때워서 해결했다. 시뮬레이션으로.. 2022. 4. 16.
백준 2713 자바 - 규현이의 사랑을 담은 문자메시지 (boj 2713 java) 문제 : boj2713 실버치고 구현이 상당히 빡쌘 문제이다. 아마 곧 골드까지 올라갈 것 같다. 이정도면 아무리 별다른 알고리즘 필요없는 구현문제라도 골드5정도가 맞다. 내 경우엔 최대한 원툴(?)로 구현을 하고 싶었다. 따라서 약간의 아이디어를 써서 좀 쉽게 진행했다. 다음의 입력을 확인해보자. 1 4 4 ACM 4x4일 경우, 그보다 2칸씩 크게 미리 배열을 만든다. 즉 6x6으로 만들고, 외곽을 1칸씩 띄운 상태로 중앙의 4x4에 '-1'과 같이 나올 수 없는 수를 쓴다. 해당 위치에 들어가야하는데 아직 값이 안들어갔다는 의미로 사용했다. 그리고 (1,0) 지점에서 시작하고, 처음 진행하는 방향은 항상 우측방향이다. 그리고 방향은 우측:0, 아래:1, 좌측:2, 위:3 으로 정한다. 소용돌이가 진.. 2022. 3. 29.

티스토리툴바