[BOJ 14502] 연구소 연구소 성공시간 제한메모리 제한제출정답맞은 사람정답 비율2 초512 MB124386849392953.977%문제인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.2 0 0 0 1 1 0 .. [BOJ 7576] 토마토 토마토 성공시간 제한메모리 제한제출정답맞은 사람정답 비율1 초256 MB4081911733749228.538%문제철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 .. [Algorithm] Queue,Pair,Vector 출처: https://sarah950716.tistory.com/5 [알고리즘 정복기]출처: https://sarah950716.tistory.com/4 [알고리즘 정복기] 1) 정의FIFO(First In First Out, 선입선출) 자료구조 2) 용도① BFS(Breadth First Search, 너비우선탐색)② 특별한 알고리즘을 사용하는 것이 아니라 직접 문제 상황을 구현하는 문제들 중 FIFO의 구조를 가지는 문제를 풀 때 (Ex. 다리에 올라갈 수 있는 최대 하중과 각 트럭의 무게가 주어질 때, 모든 트럭이 다리를 지나가는 데 걸리는 최소 시간을 구하는 문제. 다리에 먼저 올라간 트럭이 먼저 나오게 되기 때문에 queue를 이용해 구현하면 풀 수 있다.) 3) 사용법queue를 사용하기 위해.. [Algorithm] Parametric Search 7이 아니고 9 임.최소한 몇 개의 연속된 값을 ???????? 우리가 주목할 부분 위와 같은 방법은 구간 x가 가능한지 판단할려면 O(n)이 소요된다. 최악의 경우 n번 곱하기 n 이라서 최악의 경우 O(n^2) 의 시간복잡도를 가진다. N [Algorithm] 이진탐색 문제n개의 오름차순으로 정렬된 숫자가 주어지고, 그 후 q개의 질문이 주어진다. 각각의 질문은 특정 숫자가 n개의 숫자 내에 존재하는지를 판별하는 것이다. 모든 q개의 질문에 대하여 답을 하는 프로그램을 작성하시오. 입력첫 번째 줄에 숫자의 개수 n, 그리고 질문의 개수 q가 주어진다 ( 1 ≤ n ≤ 100,000, 1 ≤ q ≤ 100,000) 이는 오름차순으로 정렬되어 주어진다. 두 번째 줄에 n개의 숫자가 주어진다. 세 번째 줄에 q개의 질문이 주어진다. 각 수는 21억보다 작은 정수다. 출력각 질문에 대하여 숫자가 존재하면 YES, 아니면 NO를 한 줄에 하나씩 출력한다. 예제 입력10 4 1 2 4 8 10 11 12 14 15 19 4 5 8 17 예제 출력YES NO YES NO 우선 in.. [Algorithm] Binary Search (재귀호출을 사용하지 말고~) * while 문을 사용하여 구현할 수 있다.* 생각보다 어렵다. 구현하는 과정이 생각보다 복잡하다. 하지만 각각의 변수가 무슨 역할을 하는지 말로 명확히 정의를 한다면 구현하는 데 도움이 될 수 있다. // 비재귀호출#include int binarySearch(int arr[], int myStart, int myEnd, int value){ // arr의 start부터 end까지 중에서 // value를 찾아 그 위치를 반환하는 함수. // 만약, 없다면 -1을 반환한다. int start, end; // start는 value보다 항상 작은 값을 가리킴. // end는 value보다 항상 큰 값을 가리킴. int mid; // 범위를 초과하는 value의 값일 경우 없다고 말해야 함. if(arr.. [Algorithm] Binary Search (재귀호출을 사용하여~) 1. 개념과 원리 배열에 있는 특정 숫자를 검색할려면 O(n)이 걸린다.더 빠르게 못하나? 할수있다!Binary Search를 사용해 할 수 있다.단, 정렬이 되어 있는 경우에만 사용이 가능하다. 1. 중간값을 본다. 이 값이랑 찾고자 하는 값이랑 비교를 한다.2. 내가 찾고자 하는 값은 왼쪽일까요 ? 오른쪽 일까요? 3. 또 중간값을 ~ 반복해서 비교하여 날릴 구간을 정한다. 2. 시간복잡도숫자를 절반씩 지워나가면서 찾는다. 200개라고 가정. - 100개 - 50개 -25개 - 12개 or 13개 - 7개 - 4개 -2개 - 1개 200개는 총 8번의 비교를 하게 된다. O(logN) 이다. 의문점: 결국은 정렬을 해야 하니.. nlog(n) 이 아니냐 ? 맞음 이미 배열이 정렬되어 들어온다고 가정해.. [Algorithm] 적록색약 적록색약 성공한국어 시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB60993474278258.445%문제적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다.크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다)예를 들어, 그림이 아래와 같은 경우에RRRBB GGBBB BBBRR BBRRR RRRRR적록색약이 아닌 사람이 봤을 때 구역의 .. 이전 1 ··· 4 5 6 7 8 9 10 ··· 13 다음
