본문 바로가기
반응형

분류 전체보기714

[ 백준 / 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.
[백준/1918] 후위표기식 ( java ) www.acmicpc.net/problem/1918 어떤 표기식보다 후위표기식을 그나마 가장 안다고 생각했는데 알고보니 제대로 안 것이 아니였다. ;; 연산자 우선순위에 따라서 결과값이 바뀌는 것인데, 제대로 고려하지 못했다. 따라서 연산자 우선순위를 고려하여서 수정하였다. 먼저 괄호가 있는 경우와 없는 경우로 나누어야 한다. 괄호가 있는 경우는 쉽다. 괄호가 끝나면 연사자를 stack으로 출력하면 된다. 왜냐하면 괄호는 하나의 연산단위로 계속 묶어주기 때문이다. 하지만 괄호가 없는 경우를 고려해야 한다. 이때 연산자 우선순위를 따져준다. 핵심은, 연산자를 계속 stack에 저장하면서 이전 stack값과 비교하는데, 현재의 자신보다 이전 연산자 우선순위가 같거나 높으면 출력한다. 예를 들어 stack의 .. 2021. 1. 10.
반응형

티스토리툴바