Jonyo Programming

[BOJ 14003(G1)리뷰] 가장 긴 증가하는 부분수열 문제 시리즈를 풀었다. 이 문제들을 푸는데 필요한 알고리즘인 LIS알고리즘을 정리해놓았다. 이 문제는 시리즈 중 가장 어려운 문제이다. 입력데이터가 1,000,000이므로 O(N²)로는 풀수가 없고 lower bound를 이용하여 O(NlogN)으로 풀어야 한다. 게다가 이 문제는 부분 수열까지 출력해야 하는 조건이 있다. 부분 수열을 출력하기 위하여 trace라는 스택에 각 값의 lower bound를 기록했다. 만약 {10,20,10,30,20,50} 이라면 lower bound는 {1,2,1,3,2,4} (인덱스 1부터 시작) 가 된다. 그리고 가장 긴 증가하는 부분수열의 길이는 4가 된다. 이제 뒤에서부터 > val; arr.push_ba..

[BOJ 1138(S2) 리뷰] 아 그리디 너무 어렵다 .. 그리디인걸 알고 풀어도 잘 안풀리는데 코테에서 그리디임을 발견하고 풀 수 있을지 모르겠다. 키가 1부터N까지인 사람들이 있다. 이 사람들은 각각 왼쪽에 자기보다 키 큰 사람이 몇명있었는지 기억한다. 우리는 그 정보를 토대로 줄을 세워야 한다. 입력이 2 1 1 0 으로 주어지면 1보다 키 큰사람이 왼쪽에 2명, 2보다 키 큰사람이 왼쪽에 1명, 3보다 키 큰사람이 왼쪽에 1명, 4보다 키 큰사람이 왼쪽에 0명 이고 이때 올바르게 줄을세우면 4 2 1 3이 된다. 이제 이걸 어떻게 푸느냐가 문제다. 물론 완전탐색으로도 풀 수있으나 문제의 본질은 아니라 생각한다. 이 문제는 키가 가장 작은 1부터 시작한다. 1보다 키가 작은 사람은 없으므로 1의 ..

[BOJ 1339(G4) 리뷰] 쉬운듯 어려운 문제이다. 자리수가 가장 높은 알파벳에 최대한 높은 값을 주어야하는 그리디 문제이다. 그리디 문제이지만 이 문제는 백트래킹으로도 풀수가 있다. 알파벳의 갯수가 최대 10개 등장하니 각각의 알파벳을 9부터 0까지의 값으로 변경하여 계산하면 10!에 문제를 풀 수 있다. 그러나 나는 백트래킹말고 그리디+시뮬레이션으로 풀고싶었다. 그래서 일단 머리속에 떠오르는대로 구현을 하고 예제TC가 다 잘 나오길래 제출을 했더니 오답처리가 되었다. 예제에서 놓친 예외사항이 있었다. 처음에 구현했을땐 문자열을 입력받아 check배열을 통해 각각의 문자열의 INDEX에 자리수를 저장하고, 저장된 자리수를 우선순위큐에 담아 자리수 큰 숫자부터 높은숫자를 부여할 생각이였다. 그러나 ..

[BOJ 1966(S3) 리뷰] 시뮬레이션 문제다. 설명에 나온대로 프린터 큐가 존재하고 큐에 있는 각각의 작업마다 중요도가 있다. 큐의 맨앞 작업부터 하나씩 내보내야 하는데 만약 뒤에서 기다리고 있는 작업 중 현재의 작업보다 중요도가 높은 작업이 있다면 현재의 작업을 맨 뒤로 보내고 중요도가 높은 작업먼저 수행해야 한다. 이 때 M번 작업이 몇번만에 수행이되는지를 출력해야 한다. 가장 먼저 떠올렸던 구현은 큐가 빌때까지 반복문을 돌며 계속해서 뒤에있는 큐중 중요도가 있는작업이 있는지 확인하고 있다면 현재 큐를 뒤로 보내는 작업이다. 이 작업은 시간복잡도 O(n^2)에 수행된다. N이 100이하이므로 이 코드도 충분히 통과가 가능하지만, 나는 O(n)에 구현하기 위하여 우선순위큐를 이용했다. 우선순위큐를..

[BOJ 17140(G4) 리뷰] 풀면서 이게 시간내에 통과될까? 라는 생각을 몇번했는지 모르겠다. 구현방법은 바로 떠올랐는데 어떻게 하면 효율적으로 처리할수 있을지가 문제였다. 아무리 고민해도 더 좋은 코드가 떠오르지 않아 그냥 처음 생각한 방법대로 했는데 TC가 약해서인지 통과되었다. 이 문제는 R연산과 C연산을 통해 이루어진다. R연산을 하면 각 행마다의 숫자와 등장횟수를 오름차순으로 변경해주면 된다. 예를들어 1 1 2 라는 행이 있으면 1이 2번등장 2가 1번등장했으므로 -> 2 1 1 2 로 변경된다. 1 2 1 2 1 3 3 3 3 라는 행렬이 있으면 1 2 2 1 0 0 1 1 2 1 3 1 3 3 0 0 0 0 으로 변경된다. 가장 큰 행을 기준으로 나머지값은 0으로 채워주는 작업도 필요..

[BOJ 9020(S1) 리뷰] 소수관련 문제를 풀다가 풀게 된 문제이다. 문제는 설명에 나온대로 2이상의 짝수가 주어지면 그 짝수는 소수 두개의 합으로 이루어진다는것이다. 예를들어 14는 3+11로 이루어지며 10은 5+5로 이루어진다. 만약 짝을 이루는 소수가 두개라면 두 소수간의 차이가 적은것을 출력하면 된다. 나는 소수인지 판별하는 val값을 2부터 n-1까지 증가시키며 만약 val이 소수일경우 n-val의 값이 소수인지 확인 후 그 값이 소수라면 출력하도록 했다. 예를들어 n이 8이라면 2부터 7까지 소수인지 확인을 한다. 3이 소수이므로 isUsed[3]=1이 되고 또 증가하며 5가 소수이고 isUsed[8-5]가 1이므로 두 수를 출력하면 된다. 루프를 돌때마다 확인배열을 초기화시켜주면 가장..

[BOJ 2529(S2) 리뷰] 오랜만에 백트래킹 카테고리에서 문제를 풀었다. 실버문제라 그런지 쉽게 구현을 떠올릴 수 있었다. 전형적인 백트래킹 방법을 통해서 부등호 조건에 맞지 않는 경우 가지치기를 하면 된다. 다만 출력할때 021 이런식으로 맨 앞자리에 0이 오는경우가 있으므로 문자열로 출력해야 한다. 이때 어떻게 할까 고민을하다 그냥 string객체에 max,min함수를 써봤는데 잘 동작했다. #include #include #include #include using namespace std; char ans[10]; string ansmin("987654321"); string ansmax("0"); vector sign; bool isUsed[10]; int k; void go(int n) {..

입력 첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다. 둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다. 출력 첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다. [BOJ 17144(G5) 리뷰] 골드5문제인데 왤케 어렵냐 .. 설명만 봤을땐 정말 간단해 보이는데 은근 구현하는게 까다로웠다. 문제를 풀때 주의해야 할 점은 미세먼지가 퍼질때 확산이 한번에 처리되어야 한다는점이다. 한번에 처리되지 않는다면 이전 칸에서 확산된 미세먼지가 다음 칸의 ..

[BOJ 17142(G4) 리뷰] 지난 연구소, 연구소 2 문제에 이어 다른버전의 문제이다. 근데 연구소 2 문제와 코드 한줄차이라 올릴까 말까 고민했다. 문제 설명을 잘 보면 지난 연구소 2와 동일한 조건인데, 기존에 바이러스였던 위치는 새로 바이러스가 퍼지는것이 아니므로 퍼지는 시간을 계산할때 포함시키지 않는다는 소리다. 그렇기에 아래처럼 방문한 곳이 기존의 바이러스 위치라면 거리값을 return 할때 포함하지 않도록 했다. 너무 간단해서 뭔가 놓친게 있나 싶어 문제를 다시 읽어봤는데 별 다른 문제점을 못찾길래 제출했더니 정답이 나왔다. (솔직히 정답나올지 몰랐음 이왜맞??..) #include #include #include #include #include using namespace std; #d..

[BOJ 17141(G5) 리뷰] 지난번 풀었던 연구소 문제의 다른 버전이다. 저번엔 백트래킹으로 풀었지만 이번엔 next_permutation 함수를 이용했다. 지난번에는 벽을 세워 바이러스를 막아야했다면 이번엔 바이러스를 퍼지게할 위치를 고른다음 가장 빨리 바이러스가 퍼지는 위치에서 바이러스가 퍼지는 시간의 최소값을 출력해야한다. 그냥 주어진 시뮬레이션대로 구현하면 되는거라 별도의 디버깅없이 한번에 구현하고 바로 정답처리가 되었다. 1.먼저 next_permutation함수를 이용해서 총 K개의 바이러스 중 M개의 바이러스를 선택하여 벡터에 담는다. 2.선택된 바이러스의 좌표값을 기준으로 BFS를 수행하여 최대 DIST배열을 통해 최대 거리를 측정한다. 3.바이러스가 끝까지 퍼지지 않았다면 그 값은 ..