본문 바로가기

전체 글

 (169)
[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]프로그래머스 - 단어 변환 - 문제 내용 https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr - 문제 접근 방법 문제를 읽어보면 begin단어에서 target단어로 되기까지 과정이 탐색한 단어와 begin 단어는 한글자 빼고 모두 같은걸 알수 있다. 그리고 단어의 스펠링이 바뀔수 있는 모든 경우의수를 하나씩찾고 아니면 되돌아와서 다른 스펠링을 바꿔서 다시 찾고 해야한다. 그래서 해당문제는 백트래킹..
[JAVA]BOJ(백준) - 미로 탐색 - 2178 - 문제 내용 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net - 문제 접근 방법 가장먼저 모두 탐색하는 것이 아니라 최소의 칸수 즉, 최단 거리를 구하는 문제라 BFS 방식을 쓰는것으로 생각했다. 그리고 다른 DFS 문제와 마찬가지로 상하좌우를 탐색하는데 인접한 모든 값들을 살핀다. 또 미로의 값을 하나씩 탐색할때마다 이전값+1을 해줌으로써 한단계씩 넘어갈 때 마다 값을 증가시킨다. 가장 시간이 많이 걸렸던 점은 그래프의 경우 노드를 큐에 넣고 빼고를 반복하면 되는데 이건 ..

티스토리툴바