알고리즘

[Java/자바 백준 14999] 주사위 굴리기

풀이 풀이에 앞서 최근에 코테를 봤는데 이 문제 비슷한게 나왔습니다. 처음으로 코테를 가서 풀어서 다른 사람 키보드 때문에 멘탈도 살살 털리구 집중을 못했네요 ㅜㅜ 핵심은 dice 리스트에 바닥 동 서 남 북 위 순으로 현재 값을 계속 바꿔주면서 담아주는 방법을 쓰겠습니다. 하나를 예로 들자면, 동쪽으로 굴리자면 바닥에 있던 0번째 인덱스 값이 서쪽으로 가서 2번째로, 동쪽에 있던 1번째 인덱스 값이 바닥으로 가서 0번째로, 서쪽에 있던 2번째 인덱스 값이 위쪽으로 가서 5번째로, 남쪽에 있던 3번째 인덱스 값은 그대로 북쪽에 있던 4번째 인덱스 값도 그대로, 마지막으로 위쪽에 있던 5번째 인덱스 값은 동으로 이동하게 됩니다. 나머지 서 남 북으로 이동할 때에 맞춰 인덱스 값을 변경해주고 현재 위치에 맵..

[Java/자바 백준 17140] 이차원 배열과 연산

풀이 문제 자체 해석이 조금 오래 걸린 문제... r 연산 기준을 예시로 들면 1 2 3 4 5 3 1 [해당숫자, 갯수] [1 , 2개] [2, 1개] [3, 2개] [4, 1개] [5, 1개] 이들을 정렬해야하는데 1. 갯수가 낮은 순서대로 정렬하고 2. 갯수가 같다면 해당숫자가 낮은 순서대로 정렬하시면 됩니다. 구현문제라 디버깅 돌리시면 푸시면 되는데 저는 check를 arraylist로 받아서 check를 해당 연산할때 숫자가 잇는지 없는지 판단했습니다. 또 나머지를 0으로 채워줘야 할때를 연산을 하고나서 x,y 인덱스가 커질 수도 있지만 작아질 수도 있는거에 유의해서 풀었습니다. import java.io.*; import java.util.*; class hash implements Compa..

[Java/자바 swea 5648] 원자 소멸 시뮬레이션

풀이 고려해줄 사항 1. map의 크기 정의 처음엔 2000*2000이면 가능하겠다 생각해서 풀다가 0.5초에 충돌하는 경우를 해결하지 못했습니다. *2를 해주어서 map의 크기를 늘려주어 이를 해결해줬습니다. input 원자들의 값들도 *2 해주고 + 2000씩 해주어야합니다. 2. map[nx][ny] 값이 0일 경우는 그냥 옮겨주고 0이 아닐 경우에는 map[nx][ny]= map[nx][ny] + 현재 에너지 로 잡고 queue를 넣어주지 않았습니다. 이렇게 되면, 처음 도달한 원자 값만 큐에 있기 때문에, 이 원자값을 현재 map 위치의 값과 비교해주어서 조건에 해당하면 현재 map위치의 값에 있는 원자 에너지값을 모두 더해주었습니다. 3. 원자 에너지가 0인 경우 원자 에너지가 0인 경우는 에..

[Java/자바 swea 5653] 줄기세포배양

풀이 조건 1. map의 크기 map은 무한대로 크다고 하였으니 K에 따라서 여유있게 잡아줘야합니다. 2. 생명력이 높은순으로 같은 시간에 두개의 세포가 같은 곳에 퍼져나가는 경우가 있습니다. pq를 사용해서 생명력이 높은 순서대로 꺼내주도록 합니다. 3. 시간별로 진행. 시간별로 진행하므로,, pq랑 별개로 temp 큐를 만들어서 pq에서 temp로 넣어주고 pq가 비게되면 temp에서 다시 pq로 넣어줍니다. 4. 활성화 비활성화. 생명력 크기만큼 시간이 지나야 활성화가 되고, 또다시 생명력 크기만큼 시간이 지나면 죽으므로 현재 curLife를 2배로 지정해서. original이 크면 활성화를 시작하구 curlife가 0이 된다면 큐에 넣어주지 않습니다. import java.io.*; import ..

[Java/자바 swea 4013] 특이한 자석

풀이 처음 스택을 쓰려고 했는데 엄청 복잡했습니다... 그래서 2차원 배열을 통해 구현했습니다. map 4x8 2차원 형태로 저장하구 , arr에 시계면 1, 반시계면 -1, 회전 하지않는다면 0 으로 담았습니다. 받은 인덱스 값을 바탕으로 왼쪽,오른쪽을 나눈 뒤 오른쪽일 땐, map[idx][6]번과 map[idx-1][2] 을 비교해준 뒤 값을 arr 를 넣어주고 왼쪽도 비슷한 로직으로 arr 넣어줍니다. arr를 기준으로 시계,반시계로 돌려줍니다 시계방향은 끝에 있는 값을 처음으로 넣어줍니다. 반시계방향은 처음 값을 마지막으로 넣어줍니다. 풀이 완료!! import java.io.*; import java.util.*; public class Solution { static int[][] map; ..

[Java/자바 swea 1868] 파핑파핑 지뢰찾기

풀이 우선 map에 character 형식으로 담아준 뒤, 팔방탐색을 통해 지뢰의 개수를 넣어줬습니다. 지뢰의 개수가 0 일때가 핵심 !! map[i][j]=0 일때 주변의 0들을 탐색하며 붙어있는 0들도 같이 한번의 탐색하며 방문 처리를 합니다 . 0인것들을 전부 다 방문처리를 한 후 다시 반복문을 통해서 방문하지 않은 것들의 개수를 세주면 풀이 완료! import java.io.*; import java.util.*; public class Solution{ static char[][] map; static boolean[][] visited; static int[] dx = {0,1,0,-1, 1,1,-1,-1}; static int[] dy = {1,0,-1,0, 1,-1,1,-1}; static..

[Java/자바 swea 5643] 키 순서

풀이 나보다 작은 사람들과 큰 사람들의 리스트를 만들어주었습니다. 큐를 이용해서 작은 사람들을 찾아가는 로직을 구현했고 나보다 작은 사람들 중 방문하지 않았다면 큐에 bfs를 이용했습니다. import java.io.*; import java.util.*; class Edge{ int height; public Edge(int height) { super(); this.height = height; } } class Solution { static Queue q_small=new LinkedList(); static Queue q_big=new LinkedList(); public static void main(String[] args)throws Exception { // TODO Auto-genera..

[Java/자바 swea 8458] 원점으로 집합

풀이 1) 좌표와 원점까리 거리 중 홀수는 홀수끼리, 짝수는 짝수끼리 존재해야 같이 도달할 수 있습니다. 좌표들 중 거리가 짝수랑 홀수가 섞여 있으면 정답 x 2) max값이 원점에 도달하는 거리를 계산해야합니다. max%2 == sum%2 과 sum>= max보다 크거나 같은지 조건을 따져주면서 sum을 1,2,3,4, 씩 더해주면서 값을 구해야합니다. 수학문제는 어렵네요 ㅜㅜ import java.io.*; import java.util.*; class Solution { public static void main(String[] args)throws Exception{ // TODO Auto-generated method stub BufferedReader br= new BufferedReader(..

[Java/자바 백준 4485] 녹색 옷 입은 애가 젤다지?

풀이 최단 경로를 묻는 bfs 문제입니다 map에는 루피값을 넣어주고 check에 해당 경로까지 최솟값을 갱신해주면서 bfs를 풀었습니다. 아래처럼 방문한 적이 있든 없든, check에 해당 경로까지 최솟 값이 있으므로 조건을 줘서 다음경로까지의 거리합 > 현재 경로까지의 거리합 + 다음 경로 거리값 이면 큐에 넣어줬습니다. if(check[nx][ny]>check[x][y]+map[nx][ny]) { check[nx][ny]=check[x][y]+map[nx][ny]; queue.offer(new int[] {nx,ny}); } import java.io.*; import java.util.*; // bfs문제 check 현재 위치를 도달할 수 있는 최솟값을 갱신하면서 탐색 public class Ma..

[JAVA/자바 정올 1681] 해밀턴 순환회로

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=954&sca=3030 JUNGOL www.jungol.co.kr 풀이 백트래킹, 순열 문제입니다. 회사에서 출발해서 배달 장소들의 순열을 돌고 다시 회사로 도착하므로 0 -> 배달지의 순열 -> 0 ( 문제 설명에서는 1을 회사라 소개하지만 코드상 0이 회사입니다) 이런식으로 구현해서 풀었지만 시간초과가 났습니다. 이후 백트래킹 기법을 추가했습니다. permutation 함수에서 파라미터를 val을 받아서 현재의 배달 비용을 저장하고, min_val(조건에 부합하는 최솟값)과 비교를 해줘서 val 크다면 다음 순열로 백트래킹. import java.io.*; import java.util.*; public..