SiO2whocodes

https://www.acmicpc.net/problem/14719 문제각 열의 기둥 높이가 주어지고 그 사이에 채워지는 칸의 수를 출력하는 문제 접근 방법이게 맞는 방법인진 모르겠지만 W가 최대 500이어서 왔다갔다 두번하는 식으로 했다.처음에는 왼쪽에서 오른쪽으로 가면서 지금까지 가장 높았던 기둥(curMax)의 높이와 인덱스를 저장한다.그러면서 현재 보고 있는 기둥이 curMax 기둥보다 낮을 경우 -> curMax - 현재 기둥 높이 를 tmp에 더한다.이때 tmp는 임시로 고인 빗물의 양이다.그리고, 현재 보고 있는 기둥이 curMax 기둥보다 같거나 높을 경우 -> 지금까지의 고인 물이 고이는 것이 확정되므로tmp 값을 result 에 더해주고 tmp를 0으로 초기화한다. 문제는 tmp에 임시..

https://www.acmicpc.net/problem/2504문제주어진 올바른 괄호 문자열에 대해서만 규칙대로 값을 계산해서 출력하는 것규칙은 (()[[]]) 이런 문자열이라면 2*(2+3*3) = 22 가 된다. 접근방법다른 블로그들을 참고해서 풀었는데, 풀이 방법은 '겉 괄호는 본인이 끝날때까지 안쪽 괄호 모두에게 영향을 미친다'라고 생각하면 될 것 같다.그리고 계산식을 모두 풀어서 최대한 긴 다항식으로 만든다. 가 포인트인듯뭔말이냐면 위에서 2*(2+3*3) -> 2*2 + 2*3*3 으로 만든다는 것임이걸 만드는 방향으로 코드를 짜서 풀었다. 따라서 tmp 변수를 선언해두고 answer 변수에 값을 더해가면서 풀어야 함(, [ 가 나오면 우선 tmp에 2를 곱한다. 이제 앞으로 나오는 계산에는..

https://www.acmicpc.net/problem/1987DFS알파벳으로 구성된 보드판에서 좌측상단부터 시작해서 중복되지 않은 칸을 지나면서 상하좌우로 이동할 수 있다.이때 최대 몇칸까지 지날 수 있는지 구하는 문제 접근 방법상하좌우 이동하는 경우들로 DFS로 풀었다. 오답노트처음에 지나온 알파벳들을 기억하려고 벡터에 지나온 문자들을 담아두고 찾는 식으로 했다가 시간초과나서알파벳 개수 (26)만큼 boolean 배열에 방문 여부 체크하면서 가는걸로 고쳤다. 아 그리고 visit 배열 처음에 0으로 초기화 안해줬더니 랜덤값 들어가던데 (아니 그냥 Int 배열은 다 0 들어가더만) 근데 왜 DFS함수 시작할 때 방문하는걸로 하면 왜 안될까유그러면 visit배열을 다시 false로 바꿔주지 않아도 되는..

https://www.acmicpc.net/problem/9935 평범한 문자열1개와 폭발 문자열1개를 입력받고, 평범한 문자열에서 폭발 문자열은 모두 사라지게 한 결과를 출력하는 문제폭발문자열이 사라짐으로 인해 합쳐진 문자열이 또다시 폭발 문자열을 포함한다면 그것도 폭발시켜야함! 접근방법Swift String의 range와 replacesubrange를 사용해보았는데 대차게 시간초과 떠서,,얌전히 C++로 풀었다네요ㅋㅋ,,Stack문제는 Stack으로..접근방법을 한마디로 요약하면 "Stack에 문자를 하나 넣을 때 마다 폭발물을 검사하자"입니다.평범한 문자열을 모두 순회하면서 한글자씩 Stack에 넣을 건데요, 이때 한글자가 들어갈 때마다폭발물 문자열 길이 만큼 스택 상단의 문자열을 뽑아서 폭발물인지..

https://www.acmicpc.net/problem/9184if a 20 or b > 20 or c > 20, then w(a, b, c) returns: w(20, 20, 20)if a 이 문제는 -50~50 범위의 정수인 a,b,c가 주어지면 w(a,b,c)를 구해서 출력하는 문제다. 접근방법입력받는대로 계산할 수도 있지만 그러면 재귀함수를 너무 많이 호출하게 돼서 시간복잡도가 커지는 문제 -> 그래서 DP로 풀어야 하는데이번에도 다 저장해두고 사용하는 방법으로 풀었다. 그래도 계산하는 횟수가 101*101*101 정도라 시간초과가 안나는 것 같다.3차원 배열 arr[a][b][c]에 3중 반복문을 돌면서 차례차례 값을 저장한다. 숫자 하나라도 0 이하면 함숫값이 1이기 때문에 차곡차곡 ..

https://www.acmicpc.net/problem/11660  DP 동적계획법이런 표에서 주황색 점 위치(시작점)와 파란색 점 위치(끝점)가 주어지면, 빨간테두리의 박스에 속한 숫자들의 합을 구하는 문제근데 이제 빨간 박스가 M개 주어지고 M이 100,000까지 될 수 있고, NxN에서 N은 1024까지 될 수 있는.. 접근 방법처음에 엥 표 저장해두고 [r1][c1] ~ [r2][c2] 까지 다 더하면 되는거 아닌가? 했지만 실버1인걸 보고 DP로 풀었음..이전에 내가 생각해온 DP는 미리 구해놓고 쓰기 였는데 예를들면 한 행에서 각 원소의 값을 그 원소까지의 합으로 치환한다.위의 표에서 첫번째 행을 예로들면, 1 2 3 4 -> 1 3(1+2) 6(1+2+3) 10(1+2+3+4).이때 치환할..

https://www.acmicpc.net/problem/15663 백트래킹N과 M (5)와 비슷하게 N개의 자연수 중에 M개를 뽑아 만들 수 있는 수열을 모두 사전순으로 출력하는 문제인데차이점은 N개의 자연수가 중복가능임그래도 N개의 숫자 중에 M개를 뽑아야 하는 것을 변함이 없어서그냥 중복된 숫자가 있는 숫자 카드가 N개 있고, 그 중 M개를 뽑아서 나열한 수열을 중복되지 않게, 사전순으로 출력하믄댐! 접근방법N과 M(5) 코드에서 수열을 담고 있는 배열을 vector가 아닌 set으로 바꿔주면 됨~setvectorint>, lessvectorint>>> 이렇게 선언하면 사전순으로 수열이 정렬되어서 set에 들어감 오답노트set에서 vector 정렬 안될 줄 알고 string으로 넣었다가 9, 10 ..

https://www.acmicpc.net/problem/15654 백트래킹N개의 서로 다른 정수가 주어지고, 그 중에 M개를 뽑아서 만들 수 있는 가능한 수열을 사전순으로 모두 출력하는 문제 접근 방법백트래킹으로 재귀함수 써서 풀었다.재귀함수 파라미터로는 n, m, 수열을 담고 있는 배열(candidate), n개의 숫자의 방문여부를 담고 있는 배열을 갖고 다녔음입력받은 n개의 숫자를 num array에 넣어두고(sort해줌 - 사전순으로 출력하려고), 수열의 첫째자리 부터 담아가면서 방문여부 체크하고재귀함수 호출하기 반복그러다가 수열이 m자리가 되면 결과 배열에 넣고 재귀함수를 종료함 코드를 좀..지저분하게 쓴 것 같긴한데..차차 나아지겠죠머 오답노트아 근데 C++ 백준에서 돌릴 때 vector.si..

https://www.acmicpc.net/problem/18406 구현, 문자열머선 문제냐 하면123402 라는 문자열이 주어지면, 반갈죽!해서 양쪽 자릿수 합이 같은지 확인하는 문제임같으면 LUCKY 출력, 다르면 READY 출력*문자열은 늘 짝수자릿수 (즉 12345 같은 5자릿수 안들어옴) 1234021+2+3 = 6, 4+0+2 = 6 이니 이건 LUCKY 접근방법C++for 문을 두개 써서 front, back 변수에 각각 앞부분의 합과 뒷부분의 합을 저장하고 둘을 비교함swift배열하나 두고, prefix, suffix로 배열 쪼개서 reduce로 합 구해서 바로 비교하고 출력 (고차함수 쓰고 싶어서 swift로도 풀었는데, string -> int 배열 만들려다가 고군분투함..) 오답노트-..

https://www.acmicpc.net/problem/1439 그리디, 문자열S=001100 이런 이진수로 구성된 문자열이 주어지고, 연속하는 같은 숫자는 한꺼번에 뒤집을 수 있음이때 모든 문자를 같은 문자로 만드려면 최소 몇번 뒤집어야할까! 가 문제임 접근방법1. 0과 1 각각 묶음의 갯수를 구함2. 둘 중 최소를 출력함 (단, 둘 중 하나가 0인 경우 = 원래도 모두 같은 문자로 구성된 문자열이었다는 거 -> 0 출력)끄읕~ 오답노트- C++에서 string.size()가 unsigned int 인가 그래서 바로 for문 조건에 넣어버리면 오류나서 한번 변수로 담아줘야함..(원래 이랬나..)- cur(현재 연속하고 있던 문자)를 안바꿔줘서 틀렸었음~앗차차- cout 안에 삼항연산자 안들어가고 밖에..