본문 바로가기

분류 전체보기242

[백준] 2637: 장난감 조립 - JAVA https://www.acmicpc.net/problem/2637 풀이X, Y, K가 주어지는데 X를 만드는데 부품 Y가 K개 필요하다는 뜻이다. 다른 부품으로 만들어지지 않는 기본 부품이 몇개씩 필요한지 구하는 문제이다. 완제품의 번호는 N으로 주어져있다. 따라서, N부터 탐색하면 된다. 위상정렬을 이용했는데 X를 만드는데 Y가 필요하다면 Y의 위상정렬 배열에 +1해줬다. N부터 시작하여 연결된 부품의 위상을 빼가면서 0이 되면 큐에 추가하는 식으로 구현했다.  메모리: 15960KB시간: 148ms언어: Java 11import java.util.*;import java.io.*;public class Main { static class Node { int from; i.. 2024. 5. 17.
[백준] 15817: 배수 공사 - JAVA https://www.acmicpc.net/problem/15817 풀이파이프의 길이와 각 길이 파이프들의 개수가 주어진다. 이 파이프들을 갖고 x길이를 만드는 문제이다. 길이가 짧은것부터 주어지므로 따로 정렬할 필요는 없었다. 길이가 짧은 파이프부터 보면서 x부터 0으로 내려가면서 역순 탐색을 통해 dp배열에 값을 누적시켰다.  메모리: 14324KB시간: 232ms언어: Java 11import java.util.*;import java.io.*;public class Main { static class Pipe { int length; int count; public Pipe(int length, int count) { this.leng.. 2024. 5. 17.
[프로그래머스] 블록 이동하기 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/60063 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이두 점의 좌표, 방향, 시간을 Node클래스에 담아서 진행했다. 방문처리는 가로를 0, 세로를 1로 놓고 3차원 배열로 처리했다. 이동했을 때 두 점이 모두 방문한 곳이라면 진행시키지 않았다. 귀찮은 구현문제였다.  메모리: 69MB시간: 5.70ms언어: Java 11import java.util.*;class Solution { static class Node { int x1.. 2024. 5. 17.
[백준] 19598: 최소 회의실 개수 - JAVA https://www.acmicpc.net/problem/19598 풀이회의의 시작, 종료 시간이 주어지고 최의실을 배정해야 한다. 회의실의 개수를 최소로 해야한다. 시작시간 순으로 정렬을해서 차례대로 회의실에 집어넣었다. 우선순위큐에 종료시간을 넣고, 우선순위큐의 peek이 새로 들어갈 회의의 시작시간보다 작다면 그 방을 사용할 수 있다.  메모리: 48764KB시간: 668ms언어: Java 11import java.util.*;import java.io.*;public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputS.. 2024. 5. 17.
[백준] 13335: 트럭 - JAVA https://www.acmicpc.net/problem/13335 풀이n개의 트럭이 길지 w의 다리를 건너는데 1을 가는데 1의 시간이 소요되고 다리가 견딜 수 있는 무게는 L이다. 다리 위에 L넘게 올라갈 수없다. 먼저 간 트럭이 다리를 벗어날 때까지 기다려야한다. 큐에 다리위에 있는 트럭들을 저장하고 sum에 트럭의 무게를 더해줬다. 큐에 넣을 때 다리를 벗어나는 시간까지 같이 넣어주었다. 시간을 늘리면서 큐의 맨 앞에 있는 트럭이 다리를 벗어날 시간이라면 큐에서 삭제, sum에서 무게를 빼주었다. `sum + 다음에 들어올 트럭의 무게`가 L보다 작거나 같으면 큐에 트럭을 넣어주었다.  메모리: 14444KB시간: 136ms언어: Java 11import java.util.*;import java.. 2024. 5. 17.
[백준] 15810: 풍선 공장 - JAVA https://www.acmicpc.net/problem/15810 풀이만들어야 할 풍선의 개수와 한 사람이 풍선 하나를 만드는데 얼마나 걸리는지가 주어진다. 만들어야 할 풍선의 개수가 1,000,000개까지 주어지므로 연산과정에서 타입으로 long을 선택했다. 걸리는 시간을 기준으로 이분탐색을 진행했다. `left`는 1로, `righ`t는 (`소요 시간 배열의 최댓값 \* 풍선 목표량`) 으로 했다. `(left + right) / 2` 의 시간동안 각각 몇개씩 풍선을 만들 수 있는지 계산하여 더해줬고, 목표량보다 적으면 `left`를 `mid + 1`로, 크거나 같으면 `right`를 `mid - 1`로 해줬다. 계산값이 목표량보다 크거나 같을 경우 답을 갱신해줬다.  메모리: 93420KB시간: .. 2024. 5. 17.
[알고리즘] 이분 탐색 - JAVA 이분 탐색이분탐색은 탐색할 대상이 정렬된 상태에서 사용한다. 데이터의 특정 값을 찾기 위해 대상을 둘로 나눠 절반씩 줄여나가는 원리이다. 대상을 반씩 줄이기 때문에 시간복잡도는 O(logN)이다. 주어진 데이터에서 중복되지 않은 값이 주어질 때, 데이터 내에 특정 값이 존재하는지 여부를 확인하는 방법으로 많이 사용한다. 동작 방식은 다음과 같다. 1. 배열의 중간 값을 가져온다. 2. 중간 값과 검색 값을 비교한다.    - 중간 값이 검색 값과 같다면 종료한다. (mid = key)    - 중간 값보다 검색 값이 크다면 중간 값 기준 오른쪽 구간을 탐색한다.(right = mid-1)    - 중간 값보다 검색 값이 작다면 중간 값 기준 왼쪽 구간을 탐색한다.(left = mid+1) 3. 값을 찾거.. 2024. 5. 17.
[백준] 24337: 가희와 탑 - JAVA https://www.acmicpc.net/problem/24337 풀이a와 b중 큰 값을 먼저 놓고 왼쪽, 오른쪽에 다른 건물들을 배치하면 된다. a = 3, b = 5 라고 주어졌다면 5를 먼저 가운데에 세우고 왼쪽에 1 2, 오른쪽에 4 3 2 1을 배치한다. 즉, 1 2 5 4 3 2 1 과 같이 된다. 그 후 건물의 개수 N을 맞춰줘야 하는데 모자란 개수를 첫번째 건물을 세운 뒤에 1로 채워넣는다. 2번위치에 채우는이유는 첫 건물이 2 이상일 경우 앞에 1을 놓으면 a가 달라지기 때문이다.  메모리: 28116KB시간: 272ms언어: Java 11import java.util.*;import java.io.*;public class Main { public static void main(.. 2024. 5. 17.
[네트워크] 컴퓨터네트워크 및 인터넷 역사 네트워크의 구성 요소1. network edge    보통의 사용자들, 서버들은 가장자리(edge)에 위치한다.    웹브라우저들이 가장자리에 있다. 2. network core    사용자들을 연결시켜주는 특수한 역할을 하는 컴퓨터들.(라우터)    서로 연결되어있는 라우터들의 집합체이다. 3. access networks    장치들을 연결시켜주는 링크들.    즉, 네트워크에 접속하는 네트워크이다. 호스트가 네트워크 코어에 접속하는데 도움을 주는 중간 단계 네트워크이다.    유선(랜선), 무선(와이파이) 등.  프로토콜프로토콜이란 서로 다른 개체가 의사소통을 하기 위해 일정한 룰이 필요한데, 그 룰을 프로토콜이라고 한다. 의사소통을 위해 정해진 규칙.  패킷 스위칭패킷 스위칭(Packet swit.. 2024. 5. 17.
[백준] 23883: 알고리즘 수업 - 선택 정렬 3 - JAVA https://www.acmicpc.net/problem/23883 풀이선택정렬은 O(n^2)의 시간복잡도를 갖기때문에 그대로 구현하면 시간초과가 났다. 따라서 정렬이 되는 TreeMap을 이용했다. TreeMap에 숫자와 처음 인덱스를 넣고 뒤에서 부터 꺼내면서 인덱스 교체가 필요할 경우 교체해주었다.  메모리: 122416KB시간: 1564ms언어: Java 11import java.util.*;import java.io.*;public class Main { static int[] arr; static int N, K, cnt, ans_a, ans_b; public static void main(String[] args) throws Exception { Buffered.. 2024. 5. 17.

티스토리툴바