본문 바로가기

분류 전체보기

 (234)
[문제해결기법] 3. 자료구조1 1. RMQ : Range Minimum Query (범위 최소 쿼리) 배열의 부분배열에서 최솟값을 찾기 (1) O(n^3) 전처리, O(1) 질의 : brute force 방식으로 가능한 RMQ(a,b)에 대한 답을 모두 저장해놓는다. n^2칸을 채워야하고, 한 칸을 채울 때 최대 O(n)시간이 걸린다. (2) O(n^2) 전처리, O(1) 질의 : 가능한 RMQ(a,b)에 대한 답을 모두 저장하는데, RMQ(a,b+1) = min(RMQ(a,b) , A[b+1])을 사용하여 n^2칸을 각각 O(1)의 시간으로 채울 수 있다. (3) O(n) 전처리, O(sqrt(n)) 질의 : 배열을 sqrt(n) 묶음으로 나눈 후 각 묶음의 최솟값을 구하는데에 O(n)이 걸리며, RMQ(a,b)를 구하..
[문제해결기법] 2. 기초수학 1. 벡터의 외적 : cross product 2. 외적의 응용 : 부호 점검 3. CCW 알고리즘 : Counter-Clock Wise 세 점이 주어졌을 때 A->B와 A->C 두 벡터의 외적의 부호가 방향을 결정함. int ccw(int x1, int y1, int x2, int y2, int x3, int y3){ int tmp = x1*y2 + x2*y3 + x3*y1; tmp -= (y1*x2 + y2*x3 + y3*x1); if(tmp > 0) return 1; // a에 대해 b가 반시계 방향(왼쪽)에 있음 else if(tmp < 0) return -1; // a에 대해 b가 시계 방향(오른쪽)에 있음 else return 0; } 4. 응용 : 선분의 교차 여부 a-b를 이은 벡터 A에 ..
[문제해결기법] 1. C++ 1. 사용 언어 C : 가장 익숙하지만 지원 기능이 적음 C++ : STL에서 제공하는 기능을 활용 Java : java.util에 유용한 기능이 많다. 실행시간이 느려서 속도에서 제한을 받음 Python : 프로그래밍이 쉽지만, 실행시간이 가장 느리다. 2. 문제 해결 -> 기본적으로 자료구조, 알고리즘, 프로그래밍 능력을 묻는 문제 3. auto for(auto a : A){ ~ } 4. for : 반복문 5. pair 6. STL : standard template library made by HP in 1994 코드를 짧고 빠르게 작성할 수 있도록 도와줌. 7. template template const T& my_max(const T&x, const T&y){ return (y { 1, 3 } ..
[C++/BOJ] 7576 : 토마토 (bfs/dfs) https://www.acmicpc.net/problem/7576 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 ..
[C++/BOJ] 1107 : 리모컨 (완전탐색) https://www.acmicpc.net/problem/1107 문제 수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다. 리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다. 수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오. 수빈이가 지금 보고 있는 채널은 100번이다. 입력 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤..
[C++/BOJ] 16236 : 아기 상어 (bfs/dfs) https://www.acmicpc.net/problem/16236 문제 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가지고 있고, 이 크기는 자연수이다. 가장 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한다. 아기 상어는 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없고, 나머지 칸은 모두 지나갈 수 있다. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 따라서, 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있다. 아기 상어가 어디로 이동할지 결정하는 방법은 아래와 같..
[C++/BOJ] 2468 : 안전 영역 (bfs/dfs) https://www.acmicpc.net/problem/2468 문제 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사하려고 한다. 이때, 문제를 간단하게 하기 위하여, 장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정한다. 어떤 지역의 높이 정보는 행과 열의 크기가 각각 N인 2차원 배열 형태로 주어지며 배열의 각 원소는 해당 지점의 높이를 표시하는 자연수이다. 예를 들어, 다음은 N=5인 지역의 높이 정보이다. 6 8 2 6 2 3 2 3 4 6 6 7 3 3 2 7 2 5 3..
[C++/PGS] Lv.2 : 다리를 지나는 트럭 (큐) https://school.programmers.co.kr/learn/courses/30/lessons/42583 문제 설명 트럭 여러 대가 강을 가로지르는 일차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 다리에는 트럭이 최대 bridge_length대 올라갈 수 있으며, 다리는 weight 이하까지의 무게를 견딜 수 있습니다. 단, 다리에 완전히 오르지 않은 트럭의 무게는 무시합니다. 예를 들어, 트럭 2대가 올라갈 수 있고 무게를 10kg까지 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다. 경과 시간다리를 지난 트럭 / 다리를 건너는 트럭 / 대기..
728x90

티스토리툴바