본문 바로가기
728x90

Algorithm88

백준 28278 자바 (스택2) https://www.acmicpc.net/problem/28278 28278번: 스택 2 첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 둘째 줄부터 N개 줄에 명령이 하나씩 주어진다. 출력을 요구하는 명령은 하나 이상 주어진다. www.acmicpc.net 접근 문제에서 대놓고 스택을 활용해서 접근하라고 주어졌기 때문에 스택 자료구조를 활용하는 식으로 접근했다. 기능 목록 스택 메서드 기능 import java.util.*; import java.io.*; public class Main { public static void main(String[] args)throws IOException { BufferedReader br = new BufferedReader(new In.. 2024. 4. 20.
dx dy technique & inRange dx dy technique 예를 들어서 주어진 숫자(N)에 따라 현재위치에서 동서남북 한 칸씩 이동한다고 했을 때 어떻게 코드로 작성할 수 있을까요? N = 0일때 북쪽, N = 1일 때 동쪽, N = 2일 때 서쪽, N = 3일 때 남쪽으로 간다고 했을 때 현재 위치는 3,3입니다. 배열의 크기는 5 * 5로 하겠습니다. exam 1(그냥 구현 코드) package study1; import java.util.*; import java.io.*; import static javax.swing.text.html.HTML.Attribute.N; public class Exam1 { public static int N; public static int x,y; public static int nx, ny;.. 2024. 4. 8.
백준 15686 자바 (치킨 배달) https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 이 문제 같은 경우 기존에 풀었던 것처럼 dx, dy를 사용해서 문제를 푸려고 했으나, 4방향으로 탐색할 때 조건이 명확하지 않다. 또한 치킨집과 집을 따로 보관해야 하기때문에 2개의 List를 이용해서 문제를 해결한다. 입력할 때 집은 집끼리 List에 저장하고 치킨 집은 치킨집끼리 List에 저장한다. 이러고 나서 DFS를 치킨집 리스트를 기준으로 탐색을 진행한다. 치킨집.. 2024. 3. 11.
백준 17298 오큰수 자바 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 해당 문제를 이중 for문으로 문제를 해결하려고 하면 N의 크기가 1,000,000이기 때문에 1,000,000 * 1,000,000 연산을 수행하는 경우가 생기기에 시간초과가 발생할 것이다. 그럼 이 문제를 어떻게 해결을 해야할까? 바로 stack을 이용해 문제를 해결하는 것이다. 결국 이 문제는 i번째 숫자보다 오른쪽에 위치한 숫자중에 i보다 큰 수들 중에서도 가장 왼쪽에 있는값을 구하는 것이다. 이렇게.. 2024. 3. 7.
백준 2636 치즈 (자바) https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 위 문제에서는 외부 공기와 접촉된 치즈를 고르는 기능, 고른 치즈를 삭제하는 기능 이 2가지 기능을 구현하면 쉽게 해결하는 문제이다. 뒤에 2가지 기능은 비교적 단순하지만 앞에 기능이 생각하기 어려울 수 있다. 문제에서 예시로 보여주는 원래 치즈 모양이다. 여기서 외부 공기와 접촉된 부분과 내부 치즈에 둘러싸인 부분을 구분해야 한다. 해당 부분을 구분하기 위해 탐색을 이용한다. 나는 bfs로 구현했다. 외부 공기 (.. 2024. 2. 29.
백준 14502 연구소 (자바) https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net (난이도가 어려운 문제일수록 차분하게 필요한 기능이 무엇인지 생각을 하고 해당 기능을 하나하나 구현을 해야 한다) 이 문제를 풀려면 크게 2가지 기능이 있어야 한다. 첫 번째로 3개의 벽을 두는 모든 경우의 수를 구하는 기능, 두 번째로 3개의 벽을 뒀을때 해당 경우에서 바이러스를 퍼지게 하는 기능이다. 첫 번째 기능은 3개의 좌표를 고르는 경우를 구해야 하기 때문에 모든 경우의 수를 구한다 -> dfs 탐색.. 2024. 2. 29.
백준 4949 자바 https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마지막에 www.acmicpc.net 괄호 짝을 맞춰야 한다 -> 스택을 이용해서 풀어야 한다. (100%는 아님) 위 생각을 가지고 스택을 이용했다. 문자열을 입력받았을 때 내가 알고 싶은 건 괄호의 짝이 맞는지 확인하는 거기 때문에 일반 문자는 그냥 확인을 하지 않고 괄호만 확인한다. 만약 스택이 비어있는 상태에서 짝이 맞지 않는 ')' , ']'이 두 괄호가 들어오는 순간 더 이상 확인 안 하고 no를 출력.. 2024. 2. 29.
백준 16234 자바 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net bfs를 이용해서 문제를 푸려고 접근했다. L이상 R이하일 경우 Queue에 넣고 넣는 x,y 좌표도 indexes라는 List에 저장한다. 그럼 리스트에는 연합된 나라의 좌표가 저장 되는데 bfs 탐색이 끝나면 해당 좌표의 값들을 다 더해 리스트의 크기만 큼 나눈 후 각각의 좌표 위치에 계산한 값을 구한다. 문제를 풀면서 하루가 지났을때 1씩 더하는게 굉장히 애매 했는데 while.. 2024. 2. 21.
백준 2589 자바 https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 맨 처음 문제를 접근할 때는 보물이 묻혀 있는 2곳을 잡는 기능과 해당 보물이 묻혀 있을 때, 최단 거리를 구하는 기능으로 하면 구할 수 있다고 생각했다. 그러나 생각해보니 bfs로 탐색할 경우 첫 위치부터 갈 수 있는 거리까지 탐색을 하기 때문에 보물이 묻혀 있는 건 신경 안 써도 된다고 생각이 들었다. 이중 for문을 이용해서 육지인지 확인하고, 방문한 곳인지 확인을 한다. 둘다 해당사항이 존재하.. 2024. 2. 21.
백준 17298 자바 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net n의 크기를 보면 O(n^2)으로 풀면 시간초과가 걸리는 문제인 것을 생각을 해야 한다. 해당 문제는 stack을 활용해서 문제를 푼다. 우선 스택에 첫 번째 값의 index를 넣는다. 그 후 다음 숫자가 스택의 peek()(인덱스)의 숫자와 비교를 한다. 만약 peek()가 크다면 비교하는 숫자의 index를 스택에 넣는다. 만약 비교하는 숫자가 크다면 해당 숫자보다 큰 숫자가 나올 때까지 pop을 한 후.. 2024. 2. 15.
백준 15686 자바 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 맨 처음에 생각해 낸 방법은 치킨집 고르는 함수와 골랐을 때 최단거리 탐색하는 함수로 풀으려 했으나, 시간초과가 났다. 백트레킹을 이용해서 dfs로 한번에 풀어보니 정답을 구할 수 있었다. 집의 위치와 치킨집의 위치를 리스트에 저장해 놓고 dfs에서 탐색한다. 치킨집리스트에서 치킨집 M개를 골랐을 때 집의 위치와 치킨집의 위치를 다 비교해서 거리가 제일 짧은 것을 더한 후 저.. 2024. 2. 15.
백준 1068 자바 https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net parent라는 리스트에 입력한 값을 넣는다. 이후 노드를 삭제하는 함수를 만든다. 이때 재귀함수를 이용해서 해당 부모를 가진 노드를 삭제한다. 삭제할 때는 값을 -2로 바꿔준다. 또한 방문했던 값들은 visited 배열을 true로 바꿔준다. 삭제 이후에 리프노드 개수를 파악하는 함수를 만든다. visited가 true인것은 확인하지 않고 리프노드를 체크하는 함수를 호출한다. 리프노드를 체.. 2024. 2. 15.
728x90

티스토리툴바