본문 바로가기

전체 글

(24)

[Java] BitSet BitSet BitSet은 비트들로 이루어진 백터이고, 각 비트는 인덱스를 통해 개별적으로 접근할 수 있다. 이러한 점에서 boolean 배열과 유사하다. 동적으로 크기를 확장할 수도 있으며, 필요에 따라서 더 많은 비트를 저장하기 위해 자동으로 크기를 조정한다. 초기값은 false. 메소드들은 여기서: https://docs.oracle.com/javase/8/docs/api/java/util/BitSet.html BitSet vs. boolean 배열 boolean 배열의 각 boolean 값은 1비트가 아닌 1바이트를 사용한다. 이는 컴퓨터가 다룰 수 있는 정보의 최소 단위가 바이트이기 때문. BitSet 클래스는 비트 단위의 연산을 지원하여, 비트 레벨에서 빠른 연산을 수행할 수 있도록 해준다. ..

[Java] 백준 2411 - 아이템 먹기 https://www.acmicpc.net/problem/2411 풀이 아이템을 체크포인트 삼아 문제를 여러 작은 행렬 경로 문제로 나누기! 예를 들어, 예제 입력 1의 경우에는 아래와 같이 구역을 나눠서 각 구역마다 행렬 경로 문제 적용 구역을 나눈다고 표현했는데 사실 아이템을 왼쪽 아래 (1, 1) 와 가까운 기준으로 정렬하고 차례대로 먹으로 가면 됨 추가로, 시작점 (1, 1)과 도착점 (N, M)에도 아이템이 있다고 생각하면 구현 때 편함 코드 더보기 import java.io.*; import java.util.*; public class Main { public static class Point { public int row, col; public Point(int r, int c) { row..

[Java] 백준 31716 - 현대모비스 자율 주행 테스팅 1 https://www.acmicpc.net/problem/31716 풀이 한 트랙에서 1열 → N열로 이동하는 최소거리는 BFS 돌리면 금방 나오는데 한 트랙에서 다음 트랙으로 넘어갈때 이동 거리를 꼼꼼하게 처리해줘야 한다. 특히, 해당 트랙 도착점의 행과 다음 트랙 시작점의 행을 맞춰주는 작업이 필요하다. 코드 더보기 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new S..

[Java] 백준 1707 - 이분 그래프 https://www.acmicpc.net/problem/1707 풀이 각 노드마다 1과 -1을 번갈아 매기면서 그래프 탐색 (BFS/DFS): 1이 들어가야할 노드에 이미 -1이 들어가있으면 NO -1이 들어가야할 노드에 이미 1이 들어가있으면 NO 별 문제없이 그래프 탐색이 끝나면 YES 코드 더보기 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int K = Integer.parseInt(br.readLin..

[Java] 백준 16724 - 피리 부는 사나이 https://www.acmicpc.net/problem/16724 풀이 단순히 구역의 개수만 출력하는 문제라 유니온 파인드 같은 알고리즘 없이도 풀이가 가능한 것 같다. 특정 칸에서 방향 따라 이동하면서 구역의 번호를 매기면 되는데 이동하다가 1. 아직 확인되지 않은 칸에 도착 ⇒ 현재 번호를 매김 2. 현재 번호가 적힌 칸에 도착 ⇒ 사이클이니까 이동 금지하고 비어있는 칸에서 새로운 구역 번호를 매기면서 이동 시작 3. 이전 번호가 적힌 칸에 도착 ⇒ 두 구역이 연결됐으니까 구역 카운트 하나 줄이고 비어있는 칸에서 새로운 번호를 매기면서 이동 시작 코드 더보기 import java.io.*; import java.util.*; public class Main { public static void ma..

[Java] 백준 7579 - 앱 https://www.acmicpc.net/problem/7579 풀이 얼핏 봐도 배낭 문제를 많이 닮아 있다 dp[i][w] = 최대 무게가 w인 배낭에서 i번째 물건까지 판단했을 때의 최대 가치 dp[i][m] = 최대 메모리가 m인 상태에서 i번째 앱까지 판단했을 때의 최대 비용 하지만 이렇게 하기에는 m이 최대 10,000,000까지 커져서 안됨 대신 기준점을 메모리가 아닌 비용으로 잡으면 dp[i][c] = 최대 비용이 c인 상태에서 i번째 앱까지 판단했을 때의 최대 메모리 사용량 여기서 c는 최대 100×100 위의 식을 이용해서 우리 원하는 메모리를 초과하는 비용의 최소를 구하면 끝! 코드 더보기 import java.io.*; import java.util.*; public class Ma..

[Java] 백준 21276 - 계보 복원가 호석 https://www.acmicpc.net/problem/21276 풀이 조상-자손 관계를 이용해서 위상 정렬 부모-자식 관계를 출력하는 건 전체 출력에서 자식의 이름이 한 번만 등장한다는 점을 이용할 수 있음. 가장 밑에서 부터 위로 올라가면서 자식들을 출력하는데 이미 나온 이름은 출력하지 않도록 하면 됨. 문자열 처리를 위해 HashMap 사용 코드 더보기 import java.io.*; import java.util.*; public class Main { public static class Person { public String name; public int indegree, outdegree; public ArrayList ancestors; public ArrayList descendants..

[Java] 백준 31577 - 랜섬웨어와 비트코인 https://www.acmicpc.net/problem/31577 풀이 15*8 = 20*6 즉, 모든 종류의 파일을 각각 6개씩 저장하는 게 가능 가장 간단한 구현 방법 120칸 짜리 배열에 1, 2, … , 19, 20 을 6번 저장하고 해당 배열을 15개로 나누면 된다 (각 배열 정렬도 잊지 말고 하기!) 코드 더보기 더보기 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { StringBuilder sb = new StringBuilder(); int[] arr = new int[8]; for (int i = 0; i < 120; i++)..

이전 1 2 3 다음

티스토리툴바