IT recording...

https://programmers.co.kr/learn/courses/30/lessons/81304?language=java 코딩테스트 연습 - 미로 탈출 4 1 4 [[1, 2, 1], [3, 2, 1], [2, 4, 1]] [2, 3] 4 programmers.co.kr [풀이] 1. 단일 노드에서 단일 노드로 가는 최단 거리를 구하는 문제 => 다익스트라 아니 근데! Trap이라는 요소가 추가되었다. 같은 노드까지 간 경우라고 하더라도, 존재하는 trap중에 어떤것들이 밟혔는지에 따라 길이 달라진다. 따라서 보통은 다익스트라에서 dist[노드] 로 노드만 고려해주지만, dist[노드][trap들이 밟힌 경우] 로 한다. 2. map 전체에서 trap들이 밟힌 경우는 boolean배열을 사용할 수도..

https://programmers.co.kr/learn/courses/30/lessons/81303?language=java 코딩테스트 연습 - 표 편집 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO" programmers.co.kr [풀이] 1. up,down에서 처음에 0에서 UP 1 시 7(마지막)으로 가는 것으로 이해했으나, 문제에서 친절히 표 범위를 벗어나는 입력은 주어지지 않는다고 했었다. 2. LinkedList처럼 노드를 연결해서 문제를 푼다. 3. 제거 C 할 때 맨 첫 행이면 prev갱신 안해도 되고..

https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net [풀이] 양팔 저울의 양쪽에 올릴 수 있는 모든 추의 조합을 구해서 O(N^4)로도 할 수 있겠지만 그건 당연히 시간 초과일 것.. 끙끙대다가 풀이를 보았고 dp를 이용해서 푸는 문제라는 것을 알게 되었다. dp = boolean[N+1][30001]; //n번째 추를 올려놓았을 때 만들 수 있는 추의 무게에 true를 표시한다. -> 예를 들어 (왼쪽) 추+a+b = c+d+e+f (오른쪽) =>..

https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다. www.acmicpc.net [풀이] 1. 링크드리스트로 맵을 구성한다. 파란색 라인이 있는 쪽은 isBlue를 true로 설정하고, 자식에 그냥 child, blueChild를 연결함 2. 모든 말의 순열을 구하고, 점수를 계산해나간다. static void permutation(int count){ if(count>=11){ Arrays.fill(Mal,root); //처음 말들 초기화 answer = Math.max(answer,gameStart()); for(int i=1;i 40 Node middle25 = new Node(25); Node ..

https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net [풀이] 1. 원판 돌리기 static void rotate(int n,int d,int K){ if(d==0){ //시계방향 for(int k=0;k=2;j--){ Map[n][j] = Map[n][j-1]; } Map[n][1] = tmp; } } else if(d==1){ //반시계방향 for(int k=0;k 주의) 평균 구할 때 double로 소숫점 살려야함 [코드] im..

https://www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net [풀이] 다음과 같은 조건을 주의해야 한다. 파란색인 경우에는 A번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 바꾼 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 가만히 있는다. 체스판을 벗어나는 경우에는 파란색과 같은 경우이다. 원래 있는 칸(A) 이동하려는 칸(B)이 1. 흰색인 경우 -> 이동하려고 한 칸(B)에 그대로 이동, Arr뒤에 붙인다. 2. 빨간색인 ..

https://www.acmicpc.net/problem/17779 17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net [풀이] 시간 제한 1초에 총 1억번 연산이다. 여기서 N은 20까지, 우리가 정해야 할 것은 1 삽가능이다. (왜 4중 for문은 안된다고만 생각했을까.. 왜 다른 범위 조건을 내가 찾아야 한다고 생각했을까.. 시간복잡도 볼껄..) 0. 문제에서 x는 row이고, y는 col이다. (헷갈려서 몇 번 엎었다.) 1. 우선 좌표 중에서 어느 점을 기준점으로 할 것인지, d1과 d2를 어떻게 설정할 것인지..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net [풀이] 문제에 조건이 많고, 어떻게 풀이해야 할지 감이 잘 안와서 20분 넘게 펜으로 고민해본 문제이다. 문제를 보고 상어가 이동하면서 체크해야 할 것은 "가장 가까운 거리에 위치하는 물고기 파악" 이었다. 근데 이를 어떻게 판단할 것인가? 문제에서 상어는 못 가는 곳도 있어서 운이 나쁘다면 상어는 삥 돌아가야 하는 경우가 존재할 것이다. 최단거리는 그럼 어떻게 찾을 수 있을까? 1. 처..

https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net [풀이] 1. 바이러스 중 활성화 시킬 M개의 조합을 dfs를 통해 구한다. void dfs(int index, int count) , VirusVisit boolean 배열을 이용해서 조합을 구한다. static boolean[] visit = new boolean[N]; static ArrayList Active = new ArrayList(); //N개 고르기 dfs(0,0); static void ..

https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net [풀이] 1. 행 길이와 열 길이에 따라 각 초마다의 연산이 달라지니, 각 길이를 담아놓을 변수가 필요하다. 1-1. R 연산을 한다면 행 길이는 그대로고 열길이가 달라진다. 1-2. C 연산을 한다면 열 길이는 그대로고 행길이가 달라진다. 각 행,열의 길이 갱신은 모든 연산 중 가장 큰 값을 기준으로 하니, 각 행,열 연산마다 Math.max 연산을 해주며 갱신한다. 2. 갱신은 H..