코딩테스트/소프티어
-
[문제] Softeer Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai [문제 풀이] 중앙값이라 해서 헷갈릴 수 있지만 문제를 천천히 읽어보면 하나도 어려울게 없는 문제이다. 배열에서 3개의 숫자를 골랐을때 지정한 숫자가 3개의 숫자의 중앙값 즉, 최소도 최대도 아닌값이기만 하면 되는 문제이다. 총 몇개가 나올 수 있냐가 해당 문제에 중요 포인트이고 이건 배열을 sort를 이용해 정렬할때 해당값의 앞에 있는 숫자 * 해당 값의 뒤에 있는 숫자가 답이 나온다. 문제에서 n은 5만이고 q는 20만이다. q의 값을 돌릴동안 n을 차례대로 모두 방문하면 시간초과가 나오기 쉽기 때문에 해당 문제를 해결하기 위해서 이진탐색을 응용하자. [회고] 이진탐색을 생각안하고 단순히 방문했..
[C++] 자동차 테스트[문제] Softeer Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai [문제 풀이] 중앙값이라 해서 헷갈릴 수 있지만 문제를 천천히 읽어보면 하나도 어려울게 없는 문제이다. 배열에서 3개의 숫자를 골랐을때 지정한 숫자가 3개의 숫자의 중앙값 즉, 최소도 최대도 아닌값이기만 하면 되는 문제이다. 총 몇개가 나올 수 있냐가 해당 문제에 중요 포인트이고 이건 배열을 sort를 이용해 정렬할때 해당값의 앞에 있는 숫자 * 해당 값의 뒤에 있는 숫자가 답이 나온다. 문제에서 n은 5만이고 q는 20만이다. q의 값을 돌릴동안 n을 차례대로 모두 방문하면 시간초과가 나오기 쉽기 때문에 해당 문제를 해결하기 위해서 이진탐색을 응용하자. [회고] 이진탐색을 생각안하고 단순히 방문했..
2023.08.25 -
[문제] Softeer Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai [문제 풀이] 백트래킹을 이용해서 순서대로 방문하는것을 확인하는 문제이다. 처음 고민했던 부분은 bfs에서는 방문한 순간 모두 방문처리를 하는데 해당 문제에서 방문처리를 어떻게 하냐가 고민이었다. 그래서 앞서 말한 백트래킹을 이용해서 visited 처리를 할 수 있었다. void backTrack(int x, int y, int idx){ if(idx == m){ answer++; return; } for(int i = 0;i 백트래킹 -> 방문확인 풀기 순서가 되게 함수를 만들었다. 이제 여기에 추가로 idx 변수와 seq 벡터를 이용해서 순서대로 방문을 하는지를 확인만 해주면 된다. 오랜만에 백..
[C++] 순서대로 방문하기[문제] Softeer Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai [문제 풀이] 백트래킹을 이용해서 순서대로 방문하는것을 확인하는 문제이다. 처음 고민했던 부분은 bfs에서는 방문한 순간 모두 방문처리를 하는데 해당 문제에서 방문처리를 어떻게 하냐가 고민이었다. 그래서 앞서 말한 백트래킹을 이용해서 visited 처리를 할 수 있었다. void backTrack(int x, int y, int idx){ if(idx == m){ answer++; return; } for(int i = 0;i 백트래킹 -> 방문확인 풀기 순서가 되게 함수를 만들었다. 이제 여기에 추가로 idx 변수와 seq 벡터를 이용해서 순서대로 방문을 하는지를 확인만 해주면 된다. 오랜만에 백..
2023.08.25 -
[문제] https://softeer.ai/practice/info.do?idx=1&eid=633 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai [문제 풀이] 조건에서 N과 M이 3000이 안되니 n^2 으로도 시간제한 안에 충분히 풀 수 있었던 문제였기에 LCS 알고리즘을 응용해서 풀었다. N의 배열과 M의 배열을 이중으로 교차시키고 제일 많이 나오는 연속된 숫자를 답으로 체크하였다. * LCS 알고리즘에 관한 설명은 이쪽에 있다. https://yoon-1212.tistory.com/108 [코드] #include #include #include using namespace std; int main(int argc, char** argv) { int n,m,k; ..
[C++] 비밀 메뉴2[문제] https://softeer.ai/practice/info.do?idx=1&eid=633 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai [문제 풀이] 조건에서 N과 M이 3000이 안되니 n^2 으로도 시간제한 안에 충분히 풀 수 있었던 문제였기에 LCS 알고리즘을 응용해서 풀었다. N의 배열과 M의 배열을 이중으로 교차시키고 제일 많이 나오는 연속된 숫자를 답으로 체크하였다. * LCS 알고리즘에 관한 설명은 이쪽에 있다. https://yoon-1212.tistory.com/108 [코드] #include #include #include using namespace std; int main(int argc, char** argv) { int n,m,k; ..
2023.01.16