본문 바로가기
반응형

Algorithm66

[ 백준 / 3780] 네트워크 연결 ( JAVA ) www.acmicpc.net/problem/9938 9938번: 방 청소 처음 6개의 술은 규칙 1에 의해서 1, 3, 5, 7, 9, 2번 서랍에 보관할 수 있다. 7번째 술은 규칙 3을 적용할 수 있다. 1번 서랍에 들어있는 술을 2로, 2번 서랍에 들어있는 술을 3으로, 3번 서랍에 들어있 www.acmicpc.net Union-Find를 통해서 해결이 가능하다. 처음에 문제를 이해하는데 오래 걸렸다. 이 문제의 특징은 단순히 union으로 관계를 설정하고, find를 통해서 관계를 발견하는 것이 끝이 아니다. 거리가 존재하기 때문에, 이를 계속 업데이트 해주어야 한다. 따라서 parent 배열 이외에도 dis 배열을 하나 만들어서 계속 거리 값을 최신화했다. 처음에 단순히 부모의 값만 저장하여 계.. 2021. 1. 12.
[ 백준 / 10775 ] 공항 ( 자바 ) www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 문제는 2가지로 풀이가 가능하다. Greedy를 통해서 푸는 방법, Union-Find로 푸는 방법이 있다. 1. Greedy 1초에 1억번 연산이 가능하다는 것에 근거하여, Greedy로 풀어서 최악의 경우가 되어도 시간초과가 되지 않는다. 2. Union-Find union과 find에서 어떠한 연산을 해주어야 하나? union에서는 부모를 찾은 후, 부모보다 1 작은 값은.. 2021. 1. 12.
[ 백준 / 3665 ] 최종 순위 ( 자바 ) www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 위상정렬문제인데 기존 문제보다 조금 복잡하다. 왜냐하면 보통의 위상정렬은 A가 B보다 앞에있다! 이런식으로 단순하게 하나씩만 관계를 설정하면 된다. 하지만 이번 문제는 순서가 미리 정해져 있으며, 순위의 선후관계가 바뀌는 경우다. 따라서 순위에 따라서 모든 관계를 추가해주어야 한다. 예를 들어, 5 4 3 2 1의 순위가 있다면 5의 경우는 4 3 2 1을 List[]에 저장하고 inDegree는 0이다.. 2021. 1. 11.
[ 백준 / 1107 ] 리모컨 ( 자바 ) www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 여러가지 경우의 수를 고려해야 한다. * 방법1 v1. 내가 고려했던 것은, 100에서 +,-를 이용해서 이동하기 자릿수에 따라서 모든 경우의 숫자를 만들고 +,-를 이용해서 이동하기 v2. + 0을 누르고 이동하기 + 자릿수가 하나 적을 때 + 자릿수가 하나 많을 때 ================================================================ * 방법2 .. 2021. 1. 11.
[ 프로그래머스 / 멀리뛰기] (자바) programmers.co.kr/learn/courses/30/lessons/12914 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr 계단을 오른다.... (1칸, 2칸) or 멀리뛰기를 한다... (1칸, 2칸) 등은 모두 dp를 사용한다. 전형적인 문제이다. 반복적인 조합을 이용해서 최선의 결과를 찾아야 하는 것이다. 여기서는 1칸,2칸만 사용이 가능하다. 따라서 1칸과 2칸만을 이용한다. 가장 먼저 초기화를 해준다. dp[1]과 dp[2]를 해준.. 2021. 1. 11.
[백준 / 2252] 줄 세우기 ( 자바 ) www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 전형적인 위상정렬 문제이다. 학교 수업의 커리큘럼을 짜거나 순서를 정할 때 유용하다. A가 B보다 앞선다고 할 때 어떻게 코드로 표현할 것인가? inDegree라는 배열을 만들어서 B에게 +1을 한다. 그렇다면 B앞에 1개가 있다고 선언하는 것이다. 그렇다면 B앞에 무엇이 있는 것인가? 이것은 List[] 에 관리한다. 리스트 배열에서 A의 리스트에 B를 추가한다. 이전 문제에서.. 2021. 1. 11.
[ 백준 / 1406 ] 에디터 ( 자바 ) www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 에디터 문제를 처음보고 구현으로 생각했다. 그래서 케이스를 나눠서 substring을 이용했다. 커서의 위치는 index를 이용하였다. 하지만 그렇게 문제를 풀면 시간초과가 났다. package bj; import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { B.. 2021. 1. 10.
[ 프로그래머스] 조이스틱 ( 자바 ) programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 조이스틱을 이용할 때, 일방적으로 왼쪽으로 가거나 오른쪽으로 가는 것이 끝이 아니다. 왼쪽으로 오른쪽으로 언제든지 최소이동을 위해 갈 수도 있음을 알아야 한다. 하지만 일방적으로 모두 왼쪽오른쪽으로 계속 완전탐색을 하는 것도 좋은 방법은 아니다. 엄청난 중복으로 인해서 시간초과가 나는 것이 당연하기 때문이다. 따라서 적절하게 case를 나누어주어야 한다. .. 2021. 1. 10.
[백준/2805] 나무 자르기 ( 자바 ) www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이 문제는 이진트리를 이용한 최댓값을 구하는 문제이다. 정해진 범위 내에서 최대한의 높이를 잘라서 원하는 길이 M을 얻어야 한다. 1. 익숙한 유형이었는데 실수했던 부분은, min 값을 나무길이의 최소값으로 잡았다. M의 길이는 1부터 20억까지라고 되어 있다. 즉, min값은 나무길이 중 최솟값보다 더 작은 1도 될 수 있다. 정해진 공식에 따라서 문제를 푸는 습관이 었.. 2021. 1. 10.
반응형

티스토리툴바