.

문제17829번: 222-풀링 (acmicpc.net)풀이재귀로 분류되어있는 문제이지만 구현으로 풀었다.1. N*N 행렬을 여러 개의 2*2 행렬로 나눈다2. 2*2 행렬에 포함된 수를 일차원 행렬에 넣어 Arrays.sort()로 정렬 -> 두 번째로 큰 숫자를 구한다3. 도출된 숫자들로 이루어진 N/2*N/2 행렬을 만들어 같은 방식으로 진행한다4. 1*1이 될 때까지 반복한 후 출력코드 1import java.util.*;import java.io.*;public class boj_17829 { static int[][] matrix; public static void main(String[] args) throws IOException{ BufferedReader br = ..

문제24445번: 알고리즘 수업 - 너비 우선 탐색 2 (acmicpc.net)풀이 11. 인접 행렬 생성 (무방향)2. bfs탐색 -> 큐에서 노드를 꺼내 인접 노드를 방문 (내림차순으로)3. 방문체크된(큐에 넣은) 순서 정보를 따로 저장하여 출력하기 주어진 테스트 케이스, 만든 테스트 케이스 모두 통과됐지만메모리 초과가 발생했다. 인접 행렬은 직관적이고 구현이 간단하지만, 이차원 배열이므로노드 개수가 많을 경우 메모리 사용량이 상당히 많아진다. 인접행렬 메모리 초과 이유메모리 제한 : 512MB노드 수 : 5 간선 수 : 1  각 배열 원소는 int형이므로 4byte를 차지한다.최악의 경우(N=100,000) 필요한 메모리는100,000 * 100,000 * 4 = 40,000,000,000 byte..

문제11509번: 풍선 맞추기 (acmicpc.net) 풀이 1처음 접근 : 재귀 -> 테케는 통과되었으나, 제출 결과 시간 초과 1. arr 배열에 값 입력받기2. 인덱스 0부터 탐색 -> 해당 인덱스 뒤에 (해당 인덱스 값-1)인 숫자가 있는지 검사 -> 모두 방문처리, count++3. 모든 인덱스를 다 방문처리할 때까지 반복 시간 초과가 뜬 이유시간 제한 : 2초입력값 : 1  각 N개의 풍선에 대해, 현재 풍선 높이보다 1 낮은 풍선이 있으면 solve 메서드를 재귀 호출.이때, 이미 방문한 풍선은 무시한다.최악의 경우 '5, 4, 3, 2, 1'과 같이 모든 풍선 높이가 연속적으로 감소하여 모든 풍선에 대해 재귀 호출이 일어난다.-> 시간 복잡도 O(N^2) 1,000,000^2 >>>> 2억..

문제https://www.acmicpc.net/problem/2458 풀이먼저, N*N 행렬에 1을 삽입해 방향 그래프를 나타낸다.플로이드 알고리즘으로 i->k, k->j 가능하면 arr[i][j] = 1 삽입한다. 여기까지 진행하면 비교 가능한 모든 경우가 구해진 것이다.이때, 자신의 키가 몇 번째인지 알 수 있는 것은 어떤 경우일까?예제 입력 1로 예시를 들어보자. 다음은 플로이드 알고리즘을 수행한 후 행렬의 값이다. 0 1 0 1 1 1  0 0 0 0 0 0  0 1 0 1 0 1  0 1 0 0 0 1  0 1 0 1 0 1  0 0 0 0 0 0  4번 학생은 자신의 키가 몇 번째인지 알 수 있다.왜냐하면 총 6명 중 자신의 앞에 3명, 자신의 뒤에 2명이 있다는 사실을 알 수 있기 때문이다...

문제https://www.acmicpc.net/problem/1389 풀이N*N 배열을 생성한 후, 모든 원소를 INF값으로 초기화한다.INF로 초기화하는 이유는, 나중에 플로이드 알고리즘으로 비용의 최솟값을 업데이트할 때 기존 값(INF)보다 작은지 비교하기 위함이다. 입력받은 대로 N*N 배열에 1로 간선을 표시해준다.A와 B가 친구이면 B와 A도 친구 -> 무방향 그래프이므로 (A, B) (B, A) 모두 간선 표시 플로이드 알고리즘으로 임의(k)의 노드를 거쳐 도달할 수 있다면, 몇 명의 친구를 거쳐야 하는지 업데이트한다.'행 == 열' 인 경우 제외, 비용이 1인 경우 이미 비용이 최솟값이므로 제외.  각 노드의 케빈 베이컨 수 구하기 -> arr의 각 행에 해당하는 원소의 합 구하기 최솟값을 ..

문제https://www.acmicpc.net/problem/11404풀이방향 그래프에서 각각의 노드에 도달하기 위한 최소 비용을 구하는 문제이다.출발 도시, 도착 도시를 양 정점으로 하는 간선의 비용을 이차원 배열에 나타낸 후,플로이드 알고리즘을 이용하여 최솟값으로 업데이트 한다.플로이드 알고리즘은 어떤 노드를 거쳤을 때 더 적은 비용으로 갈 수 있다고 판단되면 그 값으로 업데이트하는 것이다.k(0코드import java.util.*;import java.io.*;/*입력: * 노드 개수 * 간선 개수 * 출발노드 도착노드 간선비용 * * 출력: * i행 j열로 갈 때 드는 최소 비용 * * 1. arr의 모든 원소를 INF로 초기화 * 2. 입력받는 동시에 arr를 채운다. 최솟값으로. * 3. 다른..

문제https://www.acmicpc.net/problem/14248 풀이시작 위치를 기준으로 이동 가능한 돌을 연쇄적으로 찾아가기-> 큐로 bfs를 구현하는 것이 적절해보인다. bfs 함수 :시작 위치를 큐에 넣는다. 큐에서 하나를 꺼내 이동 가능한 위치를 구한 후 모두 큐에 넣는다. -> 큐가 빌 때까지 반복- 큐에 넣을 때마다 count++로 이동 가능한 돌의 개수를 셈- 이동 가능한 위치인지 판별하는 방법 : 현재 위치에서 현재 위치에 적힌 숫자만큼 왼쪽, 오른쪽으로 이동 가능한지 (범위를 벗어나지 않는지) 확인- 맨 앞은 오른쪽, 맨 뒤는 왼쪽으로 이동할 수 있는지만 검사하면 됨코드import java.io.*;import java.util.*;public class boj_14248 { ..

문제15970번: 화살표 그리기 (acmicpc.net) 풀이1. 점 개수(N)를 입력받음2. int[100000] arr에 좌표를 인덱스로, 색깔을 값으로 저장3. arr의 모든 인덱스를 돌면서, 값(색깔)이 있으면 그 좌표의 화살표 최소 거리를 구해서 누적4. 누적값 출력코드import java.io.*;import java.util.*;public class Main { static int N; static int ans; static int[] arr = new int[100000]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(ne..

문제https://www.acmicpc.net/problem/9663 풀이*백트래킹 문제에 아직 익숙하지 않아서 풀이 방법을 본 후에 코드를 짰다. (참고 블로그)https://chanhuiseok.github.io/posts/algo-23/https://chanhuiseok.github.io/posts/baek-1/ NxN 체스판에 N개의 퀸을 서로 공격할 수 없도록 놓는 문제이다.퀸이 놓인 자리의 가로, 세로, 대각선에 다른 퀸이 놓일 수 없게 해야 한다. 가로, 세로, 대각선인지 검사한 후 제외하는 아이디어까지는 생각해냈는데,N개의 퀸을 놓는 모든 경우의 수를 구하기 위해서는 어떤 구조로 코드를 작성해야 좋을 지 떠올리는 게 힘들었다. 그리고 참고한 풀이에서 이차원 배열을 사용하지 않고 일차원 배열..

문제https://www.acmicpc.net/problem/4485풀이이차원 배열에서 (0, 0)부터 출발하여 (N-1, N-1)에 도착할 때, 지나온 좌표에 쓰여진 값들의 합이 최소가 되도록 만드는 문제이다. 이 문제는 완전 탐색과 DP를 합친 다익스트라 알고리즘을 이용하여 푸는 문제이다. 먼저 문제를 러프하게 풀어보자.(0, 0)와 인접한 좌표는 (0, 1)과 (1, 0)이다. 두 좌표의 값은 각각 5, 3이므로 값이 더 작은 3을 선택(1, 0)와 인접한 좌표는 (1, 1)과 (2, 0)이다. (0, 0)은 지나온 자리므로 고려하지 않는다. 두 좌표의 값은 각각 9, 3이므로 3을 선택...이런 식으로 (N-1, N-1)까지 구하기 하지만 매번 인접한 좌표들의 값만을 비교해서 경로를 선택하는 것은..