본문 바로가기

알고리즘/BOJ

 (95)
[JAVA]BOJ(백준) - 절댓값 힙 - 11286 문제 내용 https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 접근 방법 x가 0일때 절댓값이 가장 작은수를 출력하라는 말을듣고 우선순위큐를 사용할 생각을 할 수 있었다. 하지만 기존의 우선순위와는 다르게 큐를 만들면서 정렬을 할때 절댓값 기준으로 한번 정렬. 절댓값이 같다면 오름차순으로 정렬. 이렇게 두번 정렬이 필요하다. 그러기 위해선 우선순위큐를 만들때 Comparator로 객체를 생성해 값 o1, o2를 비교해주기..
[JAVA]BOJ(백준) - 나이트의 이동 - 7562 문제 내용 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 기존에 풀던 BFS 문제인데 단지 방향을 나타내는 배열만 바뀌었을뿐.. 문제 접근 방법 지금까지 상하좌우만 판단하던 문제에서 상하좌우가 8가지 방향(나이트 이동방향)으로 이동하면서 목표점까지 몇번 이동했는지 체크하면 되는 문제이다. 말의 이동방향을 나타내는 배열은 y축으로 +2 일때 x축으로 +1,-1 y축으로 -2 일때 x축으로 +1,-1 x축으로 +2 일때 y축으로 +1,-1 x축으로..
[JAVA]BOJ(백준) - 벽 부수고 이동하기 - 2206 문제 내용 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 최단거리를 찾는 BFS에 벽을 한번 부수고 지나갈 수 있는 조건이 추가된 문제이다. 문제 접근 방법 첫번째로 생각한 방법. BFS를 돌리는데 벽의 존재 여부에 따라 경우의수가 나뉜다는 생각을해서 벽을 처음 만날때마다 백트래킹으로 옳은길인지 아닌지를 하나씩 판단해야겠다 라는 생각을 했다. 그리고 문제에서 입력으로 주어진 2차원 배열 map의 요소값을 1씩 증가시키..
[JAVA]BOJ(백준) - 숨바꼭질 - 1697 - 문제 내용 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net - 문제 접근 방법 개인적으로 너무너무 아쉬운 문제다... 알고리즘 문제 풀때 1~2시간 고민하고 답안보이면 다른 분들 풀이를 참고하는 편인데 이건 내능력으로 충분히 풀수 있는 문젠데 생각하지 못해서 다풀지 못한문제다..ㅠ 문제를 풀기위해 가장먼저 생각한건 수빈(N)의 위치와 동생(K)의 위치가 처음부터 같다면 0을 출력. 만약 수빈이의 위치가 동생 위치보..
[JVAV] BOJ(백준) - 토마토 - 7569 - 문제 내용 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net - 문제 접근 방법 이문제는 전에 풀었던 토마토(7576) 문제와 그냥 똑같은 풀이방법으로 푼다고 생각하면된다. 하나 다른점은 토마토박스가 3차원배열로 돼있고 상하좌우 뿐만아니라 위아래의 경우도 생각해야 한다는점만 다르다. 이말은 토마토박스를 3차원 배열로 받고 위아래 경우를 어떻게 처리할지만 알면 바로 풀수 있다는 말이다. 위아래의 경우는 단순히 상하좌우처럼..
[JAVA] BOJ(백준) - 토마토 - 7576 - 문제 내용 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net - 문제 접근 방법 익은 토마토 기준으로 상하좌우에 있는 익지 않은 토마토들이 하루가 지날때마다 익어가는 문제이므로 상하좌우의 토마토가 0인지 판단만 해준다면 풀수 있는 문제라고 생각했다. 그리고 주의할점은 처음에 익은 토마토는 여러개가 있을 수도 있어서 동시다발적으로 익어가는 상황도 고려해야한다는 점이다. 그래서 처음에 큐에는 익은 모든 토마토들의 행과 열의 위치값..
[JAVA]BOJ(백준) - 미로 탐색 - 2178 - 문제 내용 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net - 문제 접근 방법 가장먼저 모두 탐색하는 것이 아니라 최소의 칸수 즉, 최단 거리를 구하는 문제라 BFS 방식을 쓰는것으로 생각했다. 그리고 다른 DFS 문제와 마찬가지로 상하좌우를 탐색하는데 인접한 모든 값들을 살핀다. 또 미로의 값을 하나씩 탐색할때마다 이전값+1을 해줌으로써 한단계씩 넘어갈 때 마다 값을 증가시킨다. 가장 시간이 많이 걸렸던 점은 그래프의 경우 노드를 큐에 넣고 빼고를 반복하면 되는데 이건 ..
[JAVA]BOJ(백준) - 유기농 배추 - 1012 - 문제 내용 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net - 문제 접근 방법 가장 먼저 집단화된 배추들의 개수를 알수있다면 배추벌레의 수도 알 수 있다. 그래서 단지번호붙이기(2667)처럼 집단 하나하나를 dfs로 세다보면 답이나온다. 필요한 것들 -> 방문배열, 배추맵, 벌레수 세주는 변수, count한 벌레 넣을 리스트, 상하좌우 배열 여튼 단지번호붙이기(2667) 문제와 비슷데 이문제가 더 간단하다고 생각하고 입력값에 대해 어떻게 함수를 어떻게 ..

티스토리툴바