본문 바로가기

분류 전체보기

 (104)
정렬 알고리즘 class Main { public static void main(String[] args) { int n = 10; int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8}; // 선택 정렬 for (int i = 0; i arr[j]) { minIdx = j; } } // 스와프 int tmp = arr[i]; arr[i] = arr[minIdx]; arr[minIdx] = tmp; } // 삽입 정렬 for (int i = 1; ..
[백준] 인구 이동 문제https://www.acmicpc.net/problem/16234   풀이이 문제 풀이의 핵심은 모든 좌표에 대해서 BFS/DFS를 수행해야 한다는 것이다. 연결되어 있지 않은 나라도 있을 수 있기 때문이다. 내가 처음에 풀었던 풀이에서부터 다음과 같은 오류들을 수정하였다. 모든 좌표에 대해 BFS 수행해야 한다.BFS 시작 시 첫 나라의 인구도 포함해야 한다.연합이 2개 이상이면 인구 이동을 수행한다.이동이 발생했는지 체크하고 반복을 결정한다. import java.util.*;class Main { static int n, l, r; static int[][] A; static int[] dx = {1, -1, 0, 0}; static int[] dy = {0, 0, 1, ..
[백준] 감시 피하기 문제https://www.acmicpc.net/problem/18428    풀이 문제 요약NxN 크기의 복도에서 선생님(T), 학생(S), 장애물(O), 빈칸(X)이 주어진다.선생님은 상, 하, 좌, 우 방향으로 감시를 하며, 장애물이 있으면 그 뒤는 볼 수 없다.학생들이 선생님의 감시를 피할 수 있도록 정확히 3개의 장애물을 배치할 수 있는지 확인해야 한다.가능한 모든 장애물 배치 경우의 수를 확인하고, 학생이 들키지 않는 경우가 존재하는지 판단해야 한다. import java.util.*;class Combination { // nCr 조합 구하는 로직 private int n; // 전체 요소 개수 private int r; // 뽑을 요소 개수 private int[] now..
[백준] 연산자 끼워넣기 문제https://www.acmicpc.net/problem/14888   풀이입력 처리n개의 숫자를 입력받고, 리스트 arr에 저장.덧셈, 뺄셈, 곱셈, 나눗셈 연산자의 개수를 입력받음.DFS(백트래킹) 활용dfs(i, now): 현재 i번째 숫자를 처리 중이고, now는 현재까지 계산된 값.모든 숫자를 처리하면 minValue, maxValue 갱신.남아있는 연산자를 하나씩 사용하면서 백트래킹 수행.연산 적용 방식덧셈, 뺄셈, 곱셈, 나눗셈 연산자가 남아있다면 사용 후 dfs 재귀 호출.연산 후에는 원상 복구하여 다른 경우의 수를 탐색할 수 있도록 함.결과 출력maxValue: 가능한 수식 중 가장 큰 값.minValue: 가능한 수식 중 가장 작은 값.  import java.util.*;publi..
[프로그래머스] 괄호 변환 문제https://school.programmers.co.kr/learn/courses/30/lessons/60058 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr    풀이빈 문자열이면 그대로 반환.p를 균형잡힌 괄호 문자열 u와 v로 분리.u가 올바른 괄호 문자열이면, v를 재귀적으로 변환 후 u + solution(v) 반환.u가 올바른 문자열이 아니라면( 를 추가하고 solution(v) 결과를 붙이고 ) 추가.u의 앞뒤 문자를 제거하고 괄호 방향을 반대로 변환하여 붙임.변환된 문자열을 반환. class Solution { // 균형잡힌 문자열의 인덱스 반환 public int bal..
[백준] 경쟁적 전염 [문제]https://www.acmicpc.net/problem/18405    [풀이]import java.util.*;class Virus implements Comparable { private int index; private int second; private int x; private int y; public Virus(int index, int second, int x, int y) { this.index = index; this.second = second; this.x = x; this.y = y; } public int getIndex() { return index; } pub..
[백준] 연구소 문제https://www.acmicpc.net/problem/14502    정답나는 완전 탐색을 이용해서 벽을 세울 수 있는 경우의 수를 구했는데 DFS/BFS를 통해서도 구할 수 있는 모양이다.풀이 방식은 다음과 같다.벽 3개를 세울 수 있는 경우의 수 다 세워보기벽이 세워진 후 바이러스 퍼지게 하기바이러스 퍼진 후 안전 영역 개수 세기안전 영역이 최댓값일 때를 저장해서 출력하기 [내 풀이]import java.util.*;public class Main { private static int[][] lab; private static int N, M; public static int BFS() { Queue queue = new LinkedList(); int..
[백준] 특정 거리의 도시 찾기 문제https://www.acmicpc.net/problem/18352   그래프를 표현하는 방법에는 두 가지가 있다. 1. 인접 행렬 (Adjacency Matrix)N x N 크기의 2차원 배열 사용 (int[][] graph = new int[N][N])graph[A][B] = 1 이면 A -> B로 가는 간선이 존재간선이 없으면 0으로 저장 2. 인접 리스트 (Adjacency List)리스트 배열 또는 리스트의 리스트 사용 (List> graph)graph[A] 리스트에 B를 저장하면 A -> B로 가는 간선이 존재 이 문제는 인접 행렬이 더 적합한데, N이 100,000개만 되어도 100,000 x 100,000 = 10,000,000,000 (100억 개) 크기의 배열이 필요하게 되기 때문이..

티스토리툴바