[백준] 1321 - 군인 접근 매 쿼리가 들어왔을 때 1번 부대부터 n번 부대까지의 구간합을 각각 알아낼 수 있다면 lower_bound로 O(logN)만에 답을 탐색할 수 있다. 구현 값의 업데이트가 많이 일어나므로 세그먼트 트리 또는 펜윅트리를 사용한다.(나는 구현이 좀 더 쉬운 펜윅트리를 사용했다.) 펜윅트리나 세그먼트 트리로 저장할 경우 ...

문제 링크 조건식에서 오른쪽을 모두 왼쪽으로 넘겨서 정리하면, (ai-bi)+(aj-bj)>0이 된다. 즉, 배열을 하나로 정리할 수 있다. 또한 i와 j의 순서는 결국 상관이 없게되기 때문에 배열을 정렬해도 문제가 없다. 이제 1 이상인 배열의 갯수는 nC2, 즉 (n*(n-1))/2로 계산해주면 된다. 음수의 경우 upper_bound를 이...

문제 링크 첫 위치와 마지막 도착지를 ‘R’이라고 두고 각 ‘R’과의 사이 중에서 최댓값을 출력한다. 어차피 가장 마지막에 도달하기 위해서는 ‘R’을 이용해야만 하기 때문이다. 소스코드 #include <string> #include <vector> #include <map> #includ...

문제 링크 배열이 주어질 때 해당 배열의 부분배열이 팰린드롬이 될 수 있는지를 판단하는 문제. 완전 탐색으로 현재 위치부터 두 칸 뒤부터 동일한 원소가 하나라도 존재하면 반드시 YES. 소스코드 #include <string> #include <vector> #include <map> #i...

문제 링크 현재 테트리스 게임 내에 남아있는 블록의 상태가 주어질 때, 가로 1 세로 2짜리 블록만으로 모든 블록을 제거할 수 있는지 여부를 출력하면 된다. 즉, 현재 남아있는 블록 중에서 세로 길이가 홀수인 블록이 있다면 불가능을 출력하면 된다. 이 때 주의할 점은 이미 모든 줄이 채워진 부분은 사라질 수 있으므로 그것을 고려한 이후에 홀수높이가 ...

문제 링크 내가 보기에는 KTX타고 지나가면서 봐도 trie문제인데.. 이게 왜 해시에 있는걸까.. 다른 풀이를 봐야할 듯 하다.. 소스코드 #include <string> #include <vector> using namespace std; struct trie { trie* arr[26]...

문제 링크 map을 이용하여 각 이름마다 완주한 선수들이 몇명인지 세주고, 참가자 명단에서 비교하며 완주한 사람이 더 적으면 그 이름을 return했다. 소스코드 #include <string> #include <vector> #include <map> using namespace std;...

문제 링크 나는 방법을 딱히 찾지 못해서 조인을 이용했다. 그러나 전부 담아야 하는 목록이 많아진다면 이 방법으로는 해결하기가 어렵다.. 무언가 효율이 좋은 방법을 차후에 찾아보는 것으로 하자. 소스코드 SELECT A.CART_ID FROM (SELECT CART_ID FROM CART_PRODUCTS WHERE NAM...

문제 링크 문제 루시와 엘라 찾기 이름에 el이 들어가는 동물 찾기 중성화 여부 파악하기 오랜 기간 보호한 동물(2) DATETIME에서 DATE로 형 변환 루시와 엘라 찾기 조건문에서 String형식으로 된 데이터를 처리할 수 있는지 보는 문제인 것 같은데.. 사실 앞에서도 비슷한게 나왔어서 왜 있는지는 잘.. 소스코드 ...

문제 링크 문제 이름이 없는 동물의 아이디 이름이 있는 동물의 아이디 NULL 처리하기 이름이 없는 동물의 아이디 IS NULL조건을 사용할 수 있는지 묻는 문제. 소스코드 SELECT ANIMAL_ID FROM ANIMAL_INS WHERE NAME IS NULL; 이름이 있는 동물의 아이디 IS ...