본문 바로가기

구현

 (60)
[백준 / BOJ] 9466 텀 프로젝트 문제 출처 : www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 문제 해결 강의를 신청한 학생들은 텀 프로젝트를 수행해야한다. 각 학생들마다 팀을 하고싶은 학생이 다르고, 한 학생이 한명의 학생만 선택할수있다. 학생들의 팀원선택이 사이클을 이루면 해당 학생들은 팀을 이뤘다고할때, 팀을 이루지못한 학생들의 수를 구하는 문제다. 풀이 학생들의 사이클을 찾으면 되는 문제인데, 시간초과를 조심해야한다. 풀이의 핵심은 한 학생을 기준으로 그룹을 찾을때마다, 해당 그룹안에 포..
[백준 / BOJ] 8982 수족관 1 문제 출처 : www.acmicpc.net/problem/8982 8982번: 수족관 1 입력의 첫 줄은 수족관의 경계에 있는 꼭짓점의 개수 N(1 ≤ N ≤ 5,000)이 주어진다. N은 짝수이다. 수족관의 경계는 항상 꼭짓점 (0, 0)부터 시작한다. 그리고 마지막 꼭짓점은 (A, 0)의 형태로 끝난 www.acmicpc.net 물이 들어있는 수족관이있다. 수족관의 바닥에 구멍이 뚫려있을때, 각 구멍을통해 빠져나간후 남은 물의 양을 구하는 문제다. 풀이 범위가 크지않아 완전탐색으로도 풀리는 문제다. 각 구멍의 좌표를 기준으로 왼쪽, 오른쪽으로 탐색하며 현재의 높이보다 수족관의 바닥의 높이가 높을경우, 높이를 올려주며 남아있는 물의 양을 구해주면된다. 1. 구멍이 있는 바닥의 x1(시작 x 좌표) 부터..
[백준 / BOJ] 2495 연속구간 문제 출처 : www.acmicpc.net/problem/2495 2495번: 연속구간 여덟 자리의 양의 정수가 주어질 때, 그 안에서 연속하여 같은 숫자가 나오는 것이 없으면 1을 출력하고, 있으면 같은 숫자가 연속해서 나오는 구간 중 가장 긴 것의 길이를 출력하는 프로그램을 www.acmicpc.net 여덟자리 정수가 주어졌을때, 연속해서 나오는 정수들의 최대 갯수를 구하면된다. 풀이 입력받고 연속해서 나오는 정수들의 최대갯수를 구하면 된다. 정수로 입력받고 한자리씩 짤라가며 해도 되지만, String을 사용하면 훨씬 편하게 할수있다. 소스코드 https://github.com/devxb/JJUNalgo/blob/master/2495%20%EC%97%B0%EC%86%8D%EA%B5%AC%EA%B0%8..
[백준 / BOJ] 1083 소트 문제 출처 : www.acmicpc.net/problem/1083 1083번: 소트 크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전 www.acmicpc.net N크기의 정수배열과 S가 주어졌을때, 정수들의 순서를 최대 S번 바꿔서 사전순으로 가장 뒤에있는 것을 출력하는 문제다. 예를들어, 5 10 20 30 40 50 5 는 50 20 10 30 40 이 출력되어야한다. 풀이 그리디로 풀리는 문제였다. 사전순으로 가장 뒤에있는단어는 1. 앞에있는 단어가 뒤에있는 단어보다 클수록 사전순으로 앞선다. 이런 조건이있다. 따라서, 현재 위치에서 S번 뒤로 ..
[백준 / BOJ] 19591 독특한 계산기 문제 출처 : www.acmicpc.net/problem/19591 19591번: 독특한 계산기 숫자, '+', '*', '-', '/'로만 이루어진 길이가 106 이하인 수식이 주어진다. 계산 과정 중의 모든 수는 −263 이상 263 미만이며, 0으로 나누는 경우는 없다. 숫자 앞에 불필요한 0이 있을 수 있다. www.acmicpc.net 수식이 주어졌을때, 계산을 하는 문제다. 계산을 할때 규칙이 있는데, 가장 앞, 혹은 가장뒤에있는 것만 계산할수있다. 이때, 곱하기 나누기를 더하기 빼기보다 먼저 계산하고, 수식 우선순위가 같다면 계산결과가 큰것부터 계산한다. 풀이 문제에서 하란대로만 구현하면 풀리는문제다. deq자료구조를 이용했다. 숫자을 저장하는 deq, 연산자를 저장하는 deq을 각각 만들고..
[백준 / BOJ] 20157 화살을 쏘자 문제 출처 : www.acmicpc.net/problem/20157 20157번: 화살을 쏘자! 호준이는 요즘 활 쏘기에 푹 빠져 있다. 열심히 활 쏘기를 연습하던 호준이는 쏠 때 마다 10점이 나오는 경지에 이르렀다. 이렇다 보니 한 방향으로 있는 과녁에 쏘는 것에 실증을 느낀 호준이는 www.acmicpc.net 풍선들의 (X,Y)가 주어졌을때, 호준이가 화살을 쏠때, (화살은 포물선이 아닌 직선으로 날라감) 한번에 터트릴수 있는 풍선의 최대갯수를 구하는 문제다. 풀이 풍선의 갯수가 10만개이다. 일반적인?? 완전탐색으로 모든경우를 볼경우 O(N^2)이 나와서 시간초과가 뜬다. 완전탐색으로 풀되, 저장을 다르게 해야하는데, 나는 딕셔너리에 {기울기, 해당 기울기의 풍선의 갯수} 로 저장해 주는식으로 ..
[백준 / BOJ] 2872 우리집엔 도서관이 있어 문제 출처 : www.acmicpc.net/problem/2872 2872번: 우리집엔 도서관이 있어 상근이는 컴퓨터 공학의 일인자가 되기 위해 책을 매우 많이 구매했다. 하지만, 집에 책장이 없어서 책을 탑처럼 쌓아놓고 있다. 오늘은 오랜만에 상근이가 집에서 휴식을 취하는 날이다. 상근 www.acmicpc.net 상근이가 책을 정리할려고한다. 책은 1 2 3 4 5 ... N 순서대로 정리해야한다. 책을 정리하는 방법은 임의의 책 한권을 뽑아서 가장 앞에 놓는다. 최소 몇번의 이동으로 책을 정리할수있는지 출력하는 문제다. 풀이 i번째 책이 i+1번째 책보다 낮은위치에 존재하는지 확인해주며 풀면 되는 문제다. 예를들어, 9 1 2 3 4 5 7 6 8 9 의 책이 있다고 하자. (9번은 움직이지 않아도..
[백준 / BOJ] 2174 로봇 시뮬레이션 문제 출처 : www.acmicpc.net/problem/2174 2174번: 로봇 시뮬레이션 첫째 줄에 두 정수 A, B가 주어진다. 다음 줄에는 두 정수 N, M이 주어진다. 다음 N개의 줄에는 각 로봇의 초기 위치(x, y좌표 순) 및 방향이 주어진다. 다음 M개의 줄에는 각 명령이 명령을 내리는 순 www.acmicpc.net 로봇의 위치와 각 명령이 주어졌을때, 시뮬레이션을 안전하게 돌릴수 있는지 확인하는 문제다. 명령은 다음 3개가 있다. L: 로봇이 향하고 있는 방향을 기준으로 왼쪽으로 90도 회전한다. R: 로봇이 향하고 있는 방향을 기준으로 오른쪽으로 90도 회전한다. F: 로봇이 향하고 있는 방향을 기준으로 앞으로 한 칸 움직인다. 로봇이 명령을 수행하다가 다른로봇 혹은 벽과 충돌할경우..

티스토리툴바