본문 바로가기

Algorithm221

[백준] 20207: 달력 - JAVA https://www.acmicpc.net/problem/20207 풀이일정들의 시작, 종료 날짜가 주어지고, 달력에 배치해야 한다. 달력에 배치할 때 주의해야 할 규칙은 다음과 같다. - 시작일이 가장 앞선 일정부터 차례대로 채워진다. - 시작일이 같을 경우 일정의 기간이 긴 것이 먼저 채워진다. - 일정은 가능한 최상단에 배치된다. 365일만큼 배열을 만들고, 일정이 있는 구간에 `+1`하여 누적합했다. 빈칸이 있으면 최상단에 배치되기때문에 누적합하여 높이와 길이를 정할 수 있기 때문이다. 일정이 없는 날짜가 나오면 `이전까지 누적했던 길이 * 높이`를 답에 더해주었다.  메모리: 14480KB시간: 136ms언어: Java 11import java.io.*;import java.util.*;publ.. 2024. 5. 19.
[프로그래머스] 주사위 고르기 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/258709 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이n개의 주사위를 2명이 나눠가진다. 주사위에 쓰인 수의 구성은 모두 다르다. 나눠 가진 주사위들의 합을 구해 점수가 큰 쪽이 승리하는데, A가 승리할 확률이 높도록 주사위를 나눠야 하는 문제이다. 먼저 주사위를 어떻게 나눌지 완탐했다. getDice()메소드를 만들어 비트마스킹을 이용해 어떤 주사위를 A가 선택할지 정해주었다. 선택이 완료되면 calculateWinRate()메소드를 통해 승률을.. 2024. 5. 19.
[백준] 1593: 문자 해독 - JAVA https://www.acmicpc.net/problem/1593 풀이문자열 W와 S가 주어진다. S를 W의 길이만큼 잘라 그 안의 문자 순서를 바꿨을 때 W로 만들 수 있는 개수를 세는 문제이다. map을 두개 선언하여 하나에는 W에 들어있는 문자와 개수를 담았다. 또 다른 하나는 W의 길이만큼 S를 잘라 개수를 담았다. 슬라이딩 윈도우를 이용해 S를 탐색하면서 map의 개수를 조정하여 map 두 개가 같은지 비교하여 같을 경우 답을 하나 증가시켰다.  메모리: 149420KB시간: 900ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOE.. 2024. 5. 19.
[백준] 16169: 수행 시간 - JAVA https://www.acmicpc.net/problem/16169 풀이컴퓨터마다 계급이 있어서 i번 컴퓨터가 동작하기 위해서는 i-1번 컴퓨터들이 먼저 동작을 해야한다. 위상정렬을 이용해 구현했다. 컴퓨터들의 정보를 저장하고, 계급의 오름차순으로 i번과 i+1을 연결시키는 연결리스트로 저장했다. 위상정렬을 위한 배열도 저장하여 이 값이 0인 것부터 큐에 넣어 처리해주었다.   메모리: 14148KB시간: 128ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Computer { int idx; int rank; int speed; public Compu.. 2024. 5. 19.
[백준] 1039: 교환 - JAVA https://www.acmicpc.net/problem/1039 풀이정수 N의 i번 위치와 j번 위치의 숫자를 바꿀 수 있다. 이 행위를 K번 반복할 때 최댓값을 구해야 한다. 위치를 바꿀 때 바꾼 수가 0으로 시작하면 안된다. n번 수행했을 때 나온 수를 방문처리 하기 위해 이차원 배열로 방문처리했다. bfs탐색을 통해 숫자와 바꾼 횟수를 저장해가면 진행했다.  메모리: 54616KB시간: 244ms언어: Java 11import java.io.*;import java.util.*;public class Main { static final int MAX = 1_000_001; static int answer; static class Node { int num; .. 2024. 5. 18.
[백준] 2150: Strongly Connected Component - JAVA https://www.acmicpc.net/problem/2150 풀이SCC는 정점들의 부분집합이며, 그 부분집합에 들어있는 서로 다른 두 정점 u, v에 대해 u에서 v로 가는 경로, v에서 u로 가는 경로가 모두 존재하는 경우를 말한다. 간선의 정보가 주어질 때, SCC의 개수와 그 안의 정점들을 출력해야 한다. SCC를 구하는 방법으로 코사라주 알고리즘과 타잔 알고리즘이 있다. - 코사라주 알고리즘   방향 그래프, 역방향 그래프, 스택을 사용하여 SCC를 구한다. 방향 그래프와 역방향 그래프가 동일한 SCC를 구성한다는 것을 이용한다.   1. 방향 그래프의 모든 정점에 대해 dfs를 수행하여 끝나는 순서대로 스택에 삽입한다.   2. 아직 방문하지 않은 정점이 있는 경우 다시 DFS를 수행한다... 2024. 5. 18.
[백준] 2792: 보석 상자 - JAVA https://www.acmicpc.net/problem/2792 풀이M가지 보석을 N명의 학생들에게 나눠주어야한다. 보석을 받지 못하는 학생이 있어도 된다. 따라서 질투심을 몇 개로 할지를 변수로 두고 이분 탐색을 했다. 질투심을 mid로 했을 때 보석을 받는 학생의 수가 N보다 작으면 정답이 될 수 있다. N보다 크면 left를 mid + 1로, 그렇지 않으면 right를 mid - 1로 좁혀가면서 탐색한다.  메모리: 34892KB시간: 356ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { Buffer.. 2024. 5. 18.
[백준] 7578: 공장 - JAVA https://www.acmicpc.net/problem/7578 풀이A열과 B열에 같은 숫자들을 연결할 때, 케이블들이 서로 교차하는 부분의 개수를 세는 문제이다. A열: 1 2 3 4 5 B열: 2 4 1 3 5 위와 같이 주어졌을 때, B열에서 A열로 줄을 쏴주었다. B열의 2에서 A열의 2로 줄을 쐈을 때, A열의 2보다 오른쪽에 이미 연결된 점이 있다면 그 점이 교차하는 점이다. B열은 앞에서부터 순서대로 보는데, A열의 연결된 점 오른쪽으로 연결된 점이 있다는 것은 B열의 앞쪽 점과 연결되어 있다는 것이므로 교차한다는 것이다. A열의 인덱스를 저장해주었고, B열의 점이 A열의 어떤 인덱스와 연결되는지 저장했다. 세그먼트 트리를 이용해 A열의 인덱스부터 N까지 구간합을 구해 교차점이 몇개인지 구.. 2024. 5. 18.
[백준] 10868: 최솟값 - JAVA https://www.acmicpc.net/problem/10868 풀이N개의 정수 배열의 a~b구간에서의 최솟값을 찾아야 한다. 세그먼트트리를 만들어 구간별로 최소값을 갖는 배열의 인덱스를 저장했다. a~b구간에서 최솟값의 인덱스를 찾아 배열의 값을 출력하면 된다. 인덱스를 저장하지 않고 최솟값 자체를 세그먼트트리에 저장하는 것도 좋다.  메모리: 48788KB시간: 600ms언어: Java 11import java.util.*;import java.io.*;public class Main { static class SegmentTree { int[] tree; int treeSize; public SegmentTree(int arrSize) { .. 2024. 5. 18.
[프로그래머스] 표 병합 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/150366 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이union-find를 이용한 구현 문제였다. MERGE명령에 대한 설명을 읽고 union-find를 사용해야겠다고 생각했다. 병합된 셀의 어느 위치를 선택하더라도 병합된 셀로 접근한다는 부분에서 union-find에서 find를 해야겠다는 생각이 들었다. parent 배열을 1차원으로 만들기 위해 2501사이즈의 배열로 만들었다. 표의 크기가 50X50이기 때문에 (r,c)의 좌표를 (r-1)X.. 2024. 5. 18.

티스토리툴바