전체 글

[백준] 17829번 : 222-풀링 Silver2(실버2) - JAVA[자바]

[Silver II] 222-풀링 - 17829 문제 링크 성능 요약 메모리: 114204 KB, 시간: 552 ms 분류 분할 정복, 구현, 재귀 제출 일자 2024년 1월 12일 14:49:42 문제 설명 조기 졸업을 꿈꾸는 종욱이는 요즘 핫한 딥러닝을 공부하던 중, 이미지 처리에 흔히 쓰이는 합성곱 신경망(Convolutional Neural Network, CNN)의 풀링 연산에 영감을 받아 자신만의 풀링을 만들고 이를 222-풀링이라 부르기로 했다. 다음은 8×8 행렬이 주어졌다고 가정했을 때 222-풀링을 1회 적용하는 과정을 설명한 것이다 종욱이는 N×N 행렬에 222-풀링을 반복해서 적용하여 크기를 1×1로 만들었을 때 어떤 값이 남아있을지 궁금해한다. 랩실 활동에 치여 삶이 사라진 종욱이..

[백준] 14500번 : 테트로미노 Gold4(골드4) - JAVA[자바]

[Gold IV] 테트로미노 - 14500 문제 링크 성능 요약 메모리: 31664 KB, 시간: 508 ms 분류 브루트포스 알고리즘, 구현 제출 일자 2024년 1월 12일 15:02:43 문제 설명 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어져 있으며, 각각의 칸에는 정수가 하나 쓰여 있다..

[백준] 11725번 : 트리의 부모 찾기 Silver2(실버2) - JAVA[자바]

[Silver II] 트리의 부모 찾기 - 11725 문제 링크 성능 요약 메모리: 99136 KB, 시간: 2072 ms 분류 그래프 이론, 그래프 탐색, 트리, 너비 우선 탐색, 깊이 우선 탐색 제출 일자 2024년 1월 11일 23:22:34 문제 설명 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. import java.io.BufferedReader; import java.io.Inpu..

Dijkstra algorithm

데이크스트라(다익스트라) 알고리즘 - Dijkstra algorithm 다이나믹프로그래밍기법을 사용한 알고리즘 기법 대표적인 최단 경로(Shortest Path) 탐색 알고리즘이다. 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려준다. 특징 1. 현재 노드에서 다른 노드로 가는 최단 거리( 가중치는 음의 간선을 포함하지 않는 양수만 가짐) 2. (현재노드까지 비용 + 다음 노드로 가는 비용) < (다음 노드로 가는 기존 비용) 이라면 갱신 3. 하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 그대로 사용한다는 특징이 있다. 구체적인 동작 과정 1. 출발 노드 설정 2. 출발 노드 기준 각 노드의 최소 비용을 저장 3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드 ..

[백준] 1753번 : 최단경로 Gold4(골드4) - JAVA[자바]

[Gold IV] 최단경로 - 1753 문제 링크 성능 요약 메모리: 121704 KB, 시간: 1288 ms 분류 데이크스트라, 그래프 이론, 최단 경로 제출 일자 2024년 1월 11일 22:06:30 문제 설명 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대..

[백준] 5639번 : 이진 검색 트리 Gold5(골드5) - JAVA[자바]

[Gold V] 이진 검색 트리 - 5639 문제 링크 성능 요약 메모리: 16088 KB, 시간: 376 ms 분류 그래프 이론, 그래프 탐색, 재귀, 트리 제출 일자 2024년 1월 10일 21:12:46 문제 설명 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다. 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다. 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다. 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다. 전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예..

[SW expert Academy] SWEA 1238번 Contact 자바(Java)

[D4] [S/W 문제해결 기본] 10일차 - Contact - 1238 문제 링크 성능 요약 메모리: 19,376 KB, 시간: 118 ms, 코드길이: 1,821 Bytes 제출 일자 2024-01-10 09:45 접근 방식 1. 배열을 통해서 인접행렬을 만들어준다. 2. visit 배열을 통해 방문 여부를 확인해준다. 3. bfs를 통해서 관련 노드 방문 처리를 해준다. 4. bfs 중 현재 연결 노드 중 최대값을 저장하여 마지막에 출력해준다. 1. 배열을 통해서 인접 행렬을 만들어준다. && visit 배열을 통해 방문 여부 확인 // 1 ~ 100까지 방문처리를 위한 visit 배열과 노드 연결을 위한 인접 행렬 visit = new boolean[101]; map = new boolean[10..

[SW expert Academy] SWEA 1861번 정사각형 방 자바(Java)

[D4] 정사각형 방 - 1861 문제 링크 성능 요약 메모리: 90,440 KB, 시간: 536 ms, 코드길이: 2,631 Bytes 제출 일자 2024-01-09 23:23 접근 방식 1. 입력 받은 배열을 for문을 통해 전부 확인한다. 2. bfs()를 통해서 상,하,좌,우로 갈 수 있는 경우의 수를 모두 확인해준다. 3. 만약 더 이상 갈 곳이 없다면 result에 갱신한다. -> 이 과정에서 같다면 방의 번호가 더 작은 방으로 해야함 1. for문을 통해 전부 확인 // for문을 통해서 전부 bfs를 통해 각 값 확인 for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ bfs(new Point(i,j,1)); } } 2. bfs()를 통해서 ..