본문 바로가기

C++61

후위표기식 1918 c++ 푼것중 가장 티어가 높은 골드2 문제다!!!! ~~ 후위표기식은 Data Structure 에서 배우는 내용이다. ​ 문제에서 우선순위에 따라 괄호를 무조건 주는게 아니다. 이것때문에 코드가 뒤죽박죽 헷갈리고 말았다. 가령 곱셈은 생략한다. ​ 먼저, 나름의 규칙을 정한다. 0. 기호들은 스택에 푸시한다 )가 오면 (가 올때까지 있는 기호들 싹다 프륀트 1번과 상관없이 * 나 / 들은 우선순위라는게 존재하기때문에 얘네가 입력되면 스위치켜준다.[2-1] : 입력받을떄 스택의 최상단에 *나/가 있으면 바로 출력 2번에서 스위치를 킨상태로 문자가 입력되면 그뒤에 *나/를 출력(pop) 3번에 문자대신 ( 가 입력되면 스위치 꺼준다. *,/, (가 아닌 문자가 입력될때 스택 최상단이 (가아니면 하나 출력(pop.. 2023. 1. 12.
백준 실4 수찾기 1920 c++ 이분탐색 막구현은 너무 쉽다. 다만 시간제한이 걸려있다는점. 시간복잡도가 입력값에 엄청 큰 영향을 준다는점. 그래서! 이중 for문 을 썼었는데 (n의 제곱) 시간오바돼서 이분탐색(시간복잡도 log n ) 을 썼다. ​ 이분탐색이 뭐냐? 시작점과 끝점 (배열의 인덱스를 말함) 을 변수에 넣어주고 마구 돌려요 잘 읽어보면 temp가 우리가 찾고자 하는 숫자에요? 그럼 얘가 mid보다 큰지 안큰지를 비교를통해 left 혹은right값을 mid 바로 우 혹은 좌로 바꿉니다!!!!그래서 범위를 반씩 쪼개는거에요. 마치 업다운 게임처럼 ,,,, ​ 단. 이걸 쓰려면 정보가 들어있는 배열(여기선 벡터) 걔네들이 오름차순 정렬이어야 합니다. 정렬이 되어있어야해요. ​ 그리고 9번줄은 안써주면 cout, cin 이녀석들이 시간.. 2023. 1. 10.
백준10799 쇠막대기 c++ 이번 문제는 깔끔한 알고리즘을 떠올리는것이 어려웠던 문제이다. ​ 오로지 '(' 와 ')' 만 주어지고 열리자마자 닫혀야 이것이 레이저라는것을 알 수 있다. ​ 생각: 아 그럼 열리자마자 닫힐때 즉 열려있을때 어떤 표시를 해놓으면 닫힘이 들어올때 바로 그 순간이 레이저구나!! 열려있으면 스위치를 1로 해놓고 닫힐때 그순간 스위치를 꺼버리면 되네!!!????? ​ 일단 퍼즐 한조각은 찾았다.. 그~~다음에 흠,, 레이저가 지나가면 그앞에녀석들은 모두 하나의 조각이 되어 전체개수를 세는데 그것의 일부분이 된다. 그럼 전체 개수를 int sum;으로 놓고 레이저 앞의 녀석들 즉 레이저가 자르는 그 순간의 조각의 높이를 체크하여 그걸 더하면 되겠네?? -> 에러, 이유는? 봐바 높이가 있어, 근데 블록이 끝나는.. 2023. 1. 9.
수열 2559 c++ queue,vector,sort 시간초과에 걸렸던 문제였다. 처음 접근 vector a에 다 받아놓고 vector sum에 합을 넣어놓는다. -> 이중 for문을 써서 for(int i = 0; i < n - k; i ++){ arrsum = 0; for(int j = i; j < i + k; j++){ arrsum += a[i]; } sum.push_back(arrsum); } 이러고 밑에서 sort(sum.rbegin(), sum.rend()); 하고 sum[0] 을 출력하면 된다 ​ 그런데 시간초과!!!! 이유는? 이중배열.. 그럼 이중배열을 안쓰며 한큐에 해결할수 있는건? 바로바로 큐 를 이용하는것이다. ​ 큐의 크기가 k 가 되기전까진 넣기만 하고 k일때부터 그들의 합을(합은 애초에 넣을때부터 누적해야한다 arrsum) vec.. 2023. 1. 8.
색종이 2563 c++ (이중배열 이용) 의문 : 어떻게 좌표들을 두개도아니고 여러개를 받아서 겹치는 부분을 계산할 수 있을까,,?? 한번만 겹친다는 전제가 있다면 vector pair써서 어떻게든하겠는데 그걸 알 수가 없잖아. ​ 생각해보니 체크된걸 또 체크해도 변하지 않는게 있다. 바로바로 값을 초기화해주는것 ex 변수 p 값이 1인데 p = 1이라고 해봤자 불변. ​ 그렇다면 도화지 사이즈는 100X100이고 이를 이중배열로 찍어보면 어떨까???? 좌표 점이랑 넓이랑 헷갈릴수도 있으니 좌표가 면을 가리킨다고 보면 안헷갈린다. ​ 이렇게 arr을 101까지 한 이유는 100번째는 99로 표현되기에 101까지해야 배열 넘버가 100까지 존재한다. (헷갈리지않기위해 한것) ​ 일단 좌하단꼭짓점만 좌표를 주니까 +10씩 해야한다. 그게 10~17.. 2023. 1. 3.
백준 단어뒤집기2 17413 c++(이중vector, tag기능) 고려해야할점이 태그는 온전하게 출력 태그가 아닌부분은 공백기준으로 reverse~ ​ 우선 태그를 고려하지않고 하면 스택을 이용하면 돼서 간단하다. sstream으로 공백마다 스택에넣어주고 출력후 한칸 띄워주기! ​ 하지만!! 저놈의 태그때문에 끵끵앓다가 떠올랐다 이중벡터. ​ 왜 이중벡터를 이용했을까????? ​ 우선 공백으로 문장을 쪼개는건 피치못할 일이다. 하지만 태그는 공백과 상관없는점. 그렇다면 쪼개기전에 태그별로 벡터에 넣어놓으면 되겠네???? 하지만 문자열을 하나씩확인해서 이거로 닫힐때까지가 태그이다. 그럼 < 열렸을때 int swt (스위치역할) 얘를 1로해주고 닫힐때 0으로해주며 스위치가 1일때 벡터에 쫙쫙쫙 넣어준다. 그럼 벡터에 넣어진녀석들은 사실 하나의 그룹인것이다. .. 2022. 12. 24.

티스토리툴바