알고리즘 - SWEA/D4

[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()를 통해서 ..

[백준] 14502번 : 연구소 Gold4(골드4) - JAVA[자바]

[Gold IV] 연구소 - 14502 문제 링크 성능 요약 메모리: 294788 KB, 시간: 748 ms 분류 너비 우선 탐색, 브루트포스 알고리즘, 그래프 이론, 그래프 탐색, 구현 제출 일자 2024년 1월 7일 13:56:40 문제 설명 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울..

[SW expert Academy] SWEA 7829번 보물왕 태혁 자바(Java)

[D4] 보물왕 태혁 - 7829 문제 링크 성능 요약 메모리: 17,688 KB, 시간: 103 ms, 코드길이: 1,017 Bytes 제출 일자 2024-01-05 23:50 접근 방식 1. 한 자연수의 모든 약수를 주어지고 자연수를 찾는 것이다. 2. P의 최소값 x 최대값을 구한다면 자연수를 구할 수 있다. 3. (혹은 값이 한개 있다면 제곱수) 풀이 코드 import java.util.StringTokenizer; import java.util.Arrays; import java.io.BufferedReader; import java.io.InputStreamReader; class Solution { public static void main(String args[]) throws Except..

[SW expert Academy] SWEA 1233번 사칙연산 유효성 검사 자바(Java)

[D4] [S/W 문제해결 기본] 9일차 - 사칙연산 유효성 검사 - 1233 문제 링크 성능 요약 메모리: 18,612 KB, 시간: 105 ms, 코드길이: 1,313 Bytes 제출 일자 2024-01-04 23:18 접근 방법 1. 예제로 있는 그래프는 중위순회를 통하여 계산이 되어야하는 그래프이다. 2. 중위 순회 그래프의 특징은 피연산자는 전부 리프 노드여야한다는 것이다. 3. 값을 입력 받으면서 만약 입력 받은 값이 - 피연산자라면 리프 노드인지 확인하고 ( 자식 노드가 없어야 함) - 연산자라면 리프 노드가 아닌지 확인한다. ( 자식 노드가 있어야 한다.) 풀이 코드 import java.util.StringTokenizer; import java.io.BufferedReader; impo..

[SW expert Academy] SWEA 1231번 중위순회 자바(Java)

[D4] [S/W 문제해결 기본] 9일차 - 중위순회 - 1231 문제 링크 성능 요약 메모리: 19,112 KB, 시간: 125 ms, 코드길이: 1,065 Bytes 제출 일자 2024-01-04 00:54 접근 방법 1. 완전 이진 트리임으로 배열로 할 수 있다. 2. 이진 트리에서는 왼쪽 자식 노드는 현재 인덱스 * 2, 오른쪽 자식은 현재 인덱스 * 2 + 1이다. 3. 인덱스를 구한후 N보다 작다면 호출 한다. ( 중위 순회는 LVR(왼쪽가운데오른쪽 순서로 진행) 4. 순서대로만 구현하면 아주 쉬운 문제 풀이 코드 import java.util.StringTokenizer; import java.io.BufferedReader; import java.io.InputStreamReader; cl..

[SW expert Academy] SWEA 1227번 미로2 자바(Java)

[D4] [S/W 문제해결 기본] 7일차 - 미로2 - 1227 문제 링크 성능 요약 메모리: 24,708 KB, 시간: 148 ms, 코드길이: 2,406 Bytes 제출 일자 2024-01-02 23:22 접근 방법 1. 간단한 미로 문제이다. 2. 테두리는 벽이기 때문에 배열 처리를 따로 해주지 않아도 됨 3. 배열을 입력 받으면서 시작 지점과 목표 지점을 저장한다. 4. 상,하,좌,우 확인 후 예외상황(벽이거나,방문했을 때)이라면 넘어간다. 5. 예외가 아니라면 방문 처리 후 큐에 삽입해준다. 풀이 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Queue; import java.util.Lin..

[SW expert Academy] SWEA 1219번 길찾기 자바(Java)

[D4] [S/W 문제해결 기본] 4일차 - 길찾기 - 1219 문제 링크 성능 요약 메모리: 17,964 KB, 시간: 107 ms, 코드길이: 1,725 Bytes 제출 일자 2024-01-02 00:50 접근 방법 1. 일단 테스트 케이스는 10개임 ( 명시가 안돼서 불편했다.) 2. 그래프는 총 100개의 노드가 있고 0부터 99까지 있음 3. 0부터 99까지 가야한다. 최대 간선은 두개뿐이기에 배열은 [100][2]로 생성 4. 만약 [start][0]이 존재한다면 [1]에 저장한다. 5. 스택에 넣어준 뒤 빼주면서 visit에 방문처리를 해준다. 6. 만약 방문이 된 곳이라면 넘어가고 방문 하지 않았다면 스택에 넣어줌 풀이 코드 import java.util.StringTokenizer; im..