알고리즘

[프로그래머스] 가장 가까운 같은 글자 (Java)

문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 없음 풀이 크기 26의 배열을 만들어 각 알파벳이 마지막으로 등장한 위치를 저장한다. s의 모든 글자를 탐색하며 1. 만약 현재 알파벳이 한번도 등장한 적 없다면 리스트에 -1을 추가하고, 그렇지 않다면 현재 알파벳의 인덱스에서 배열에 저장된 인덱스를 뺀 값을 추가한다. 2. 배열에 현재 알파벳의 마지막 위치를 갱신한다. 코드 import java.util.*; class Solution { public List solution(String s) { List answer = new ArrayLi..

[백준] 9370. 미확인 도착지 (Java)

문제 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 알고리즘 그래프, 다익스트라 풀이 다음은 문제에서 주어진 예제 입력의 두번째 케이스를 시각화한 그래프이다. 2번 지점에서 출발하여, 1-3 혹은 3-1 도로를 지나 5번, 혹은 6번 지점으로 갈 수 있다. 이 문제에 대한 정답은 6이다. 2번 지점에서 6번 지점으로 최단 경로로 가려면 2-1-3-6 으로 1-3을 지나가야하기 때문이고, 5번 지점에서 6번 지점으로 최단 경로로 가려면 2-5 로 1-3 혹은 3-1을 지나가지 않기 때문이다. 따라서 시작..

[백준] 17197. Fence Planning (Java)

문제 17197번: Fence Planning Farmer John's $N$ cows, conveniently numbered $1 \ldots N$ ($2 \leq N \leq 10^5$), have a complex social structure revolving around "moo networks" --- smaller groups of cows that communicate within their group but not with other groups. Each cow is situate www.acmicpc.net 알고리즘 그래프, 너비우선탐색(BFS) 풀이 그룹을 판별하지 않은 각 소를 시작으로 그래프를 탐색해 묶인 소들의 miny, minx, maxy, maxx 좌표를 찾는다. 울타리는..

[백준] 24482. 깊이 우선 탐색 4 (Java)

문제 24482번: 알고리즘 수업 - 깊이 우선 탐색 4 깊이 우선 탐색 트리는 1, 2, 3, 4번 노드로 구성된다. 1번 노드가 루트이다. 1번 노드의 자식은 4번 노드이다. 4번 노드의 자식은 3번 노드이다. 3번 노드의 자식은 2번 노드이다. 5번 노드는 1번 노드 www.acmicpc.net 알고리즘 그래프, 깊이우선탐색(DFS) 풀이 초기화 1. 양방향 인접리스트로 그래프를 저장 2. 모든 정점의 깊이를 -1로 초기화 3. 정점 번호를 내림차순으로 방문한다는 조건이 있으므로 인접 리스트를 내림차순으로 정렬한다. DFS R을 시작으로 현재 정점의 깊이를 저장하고 깊이를 1씩 늘리며 방문하지 않은(depth[next] != -1) 다음 정점에 대해 재귀 호출한다. 코드 import java.io...

[백준] 21736. 헌내기는 친구가 필요해 (Java)

문제 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net 알고리즘 그래프, 너비우선탐색(BFS) 풀이 도연이의 위치 (x,y)에서 시작하여 상하좌우로 너비우선탐색을 진행하며 만난 사람(P)의 수를 센다. 이때, 그래프에 P를 O로 바꾸어 입력해야함에 주의한다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java...

[백준] 16936. 나3곱2 (Java)

문제 16936번: 나3곱2 나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다. 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 www.acmicpc.net 알고리즘 브루트포스 알고리즘, 해시맵 풀이 수열 B의 원소와 개수를 해시맵에 저장하고 각 원소를 시작으로 dfs를 진행한다. 각 숫자를 사용할 수 있다면 (해시맵에 저장된 value가 1 이상이라면) 수열 A에 수를 저장한 후, 해시맵의 value를 1 감소시키고 다음 두 가지 수로 분기한다. 1. 현재 수가 3으로 나누어떨어진다면 3으로 나눈 수 2. 2를 곱한 수 N번 분기했다면 저장한 수열 A를 출력한다. 각 분기가 반환되면 수열 A에..

[백준] 16943. 숫자 재배치 (Java)

문제 16943번: 숫자 재배치 두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0 www.acmicpc.net 알고리즘 브루트포스 알고리즘, 백트래킹 풀이 A, B의 크기가 최대 109 이므로 숫자의 개수는 최대 10개이다. 10개의 숫자를 나열하는 경우의 수는 10! = 약 360만개이므로 모든 경우의 수를 탐색해 답을 구한다. A에 포함된 각 숫자의 개수를 크기 10의 1차원 배열에 담는다. 예를 들어 remain[3] = 2 라면 A에 3이 2개 포함되어있다는 의미이다. 숫자 선택 dfs 를 진행하며 i번째 수의 남은 개수가 1 이상이라면..

[백준] 1644. 소수의 연속합 (Java)

문제 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 알고리즘 에라토스테네스의 체, 투 포인터 풀이 에라토스테네스의 체를 이용해 N 이하의 소수를 리스트에 삽입하고, 투 포인터를 이용해 O(N) 의 시간복잡도로 경우의 수를 구한다. 에라토스테네스의 체를 이용한 소수 판별 소수인지 저장할 N+1 크기의 boolean형 변수 prime을 선언한다. prime은 2부터 N까지 모두 true로 초기화한 상태로, 즉 모두 소수라고 가정한 상태로 시작한다. i를 2부터 N의 제곱근까지 1씩 증가시키며 만약 i가 소수라면 i의 배수는 i를 약수로 가지기 때문에 모두 합성수로 변경한다. N의 제곱근까지 수행하는 이유는 N의 약수 중 하나는 반..

[백준] 16940. BFS 스페셜 저지 (Java)

문제 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net 알고리즘 그래프, 너비 우선 탐색(BFS), 해시셋 풀이 다음 그래프에 대해 (1 2 3 4 5 6 7 8 9 10 11 12) 라는 방문 순서가 있다면 다음과 같이 판별할 수 있다. 시작 노드인 1이 3개의 인접 노드를 가지고 있으므로 다음 3개의 수(2~4번째)는 1의 인접 노드이어야한다. 그 다음 노드인 2가 2개의 인접 노드를 가지고 있으므로 다음 2개의 수(5~6번째)는 2의 인접 노드이어야한다. ... 모든 노드가 위 조건을 만족하면 올바른 순서임을 알 수 있다. 표로 나타내면 다음과 같다. 빨간색 숫자가 검사할 숫자 파란색 숫자가 그의 인접한 노드가 위치해야하는..

[백준] 12946. 육각보드 (Java)

문제 12946번: 육각 보드 크기가 N × N인 육각 보드가 주어진다. 아래 그림은 N = 1, 2, 3, 4인 경우의 그림이다. 육각 보드의 일부 칸을 색칠하려고 한다. 두 칸이 변을 공유하는 경우에는 같은 색으로 칠할 수 없다. 어떤 칸 www.acmicpc.net 알고리즘 그래프, 깊이우선탐색(DFS) 풀이 육각 보드이므로 인접한 칸이 [상,하,좌,우]가 아니라 [상, 우상, 좌, 우, 하, 우하] 6가지이고, 임의의 칸과 인접한 6칸이 모두 색칠되어야하는 경우 3가지 색이면 모두 색칠할 수 있으므로 정답은 최대 3이 된다. 따라서 X인 칸을 시작으로 DFS를 진행하며 색을 칠한다. 색은 칠하지 않은 경우 0, 색칠된 경우 1, -1 로 표현한다. 인접한 칸이 아직 칠해지지 않았다면 칠해야하므로 ..