Algorithm69

• 

  백준 - 줄어드는 수 문제 설명 줄어드는 수 중 n번째인것을 출력하는 문제이다. 줄어드는 수를 321,950과 같은 숫자가 왼쪽에서 오른쪽으로 한자리씩 봤을 때, 작은 수여야 한다고 한다. 322와 859는 줄어드는 수가 아니라고 한다. 해당 문제는 아이디어를 잘 내야한다.. 주의사항 n의 입력을 명시적으로 주고 있지만 얼만큼의 줄어드는 수를 만들어야 할지 고민일 것이다. 위 문제를 보면 줄어드는 수 중 가장 큰수는 987654321이라는 것을 알 수 있다. TRY 선형적으로 1부터 987654321까지 String으로 변환하여 stack을 이용하여 줄어드는 수인지 판별 [시간초과] 백트래킹 9876543210을 배열에 위치시켜 하나씩 골라 수를 만든다. [성공] 수를 만들때 이전에 골랐던 범위는 절대 선택하지 않도록 해야한.. Algorithm/백준 2023. 4. 15.

• 

  백준 - 계란으로계란치기 문제 설명 계란에 대해 왼쪽부터 차례로 들어서 한 번씩만 다른 계란을 쳐 최대한 많은 계란을 깨는 문제 계란으로 계란을 치면서 가장 많이 깨뜨릴 수 있는 경우의 수를 구하는 문제이다. 계란을 하나를 잡고 계란을 친다. 그런데 중간에 손에든 계란이 깨졌거나 깨지지 않는 계란이 없으면 넘어간다.이후 손에 든 계란을 자리에 놓고 다음 계란을 들고 다시 다른 계란들을 깨뜨린다 주의사항 다른 계란을 깨뜨릴때 항상 오른쪽에만 있는 계란을 깨드리지 않아도 된다! 계란이 안깨져 있으면 모두 쳐보는 것이다! 풀이 public static void hit(int cnt) { if (n egg[0]) .filter(durability -> durability Algorithm/백준 2023. 4. 15.

• 

  프로그래머스 - 표 편집 문제 설명 주어진 명령을 따라 이행한 뒤 그에 맞는 표 값을 출력하는 문제이다. 완벽한 구현문제이다. 자료구조를 어떻게 사용하지도 물어보는 문제인것같다. TRY 2차원 배열과 map 이 두가지를 이용했다. 2차원 배열에는 각 칸이 가지고 있는 문자값을 저장했고 map에는 해당 칸과 연관되어 있는 각 칸들의 정보를 저장했다. 왜냐하면 병합 또는 병합제거, 정보 수정에 이전에 수행했던 연관되어 있는 칸들이 필요했기 때문이다. 병합시 - 이전에 수행된 연관정보들로 부터 추가로 병합을 이어나가야 하기 때문. 병합제거 - 이전에 수행된 연관정보들 모두 초기화 해야하기 때문. 정보수정 - r,c와 병합을 한 셀들을 기반으로 모든 값을 교체해야하기 때문. 주의사항 다른 연관관계를 이어붙이기 위한 과정에서 변경에 대한.. Algorithm/프로그래머스 2023. 4. 12.

• 

  프로그래머스 - 표현 가능한 이진트리 필요지식 이진트리 트리순회 문제 설명 해당 수를 이진트리로 표현할 수 있으면 1 없으면 0을 출력하는 문제이다. 주어진 문제 예시를 보면 주어진 이진트리에 더미노드를 추가하여 포화 이진트리를 형성한다. 즉, 이 것을 이용해 이진트리로 만들 수 있는지 없는지를 판별하면 된다. 문제에는 포화이진트리를 만들수 있는지 없는지 이렇게 물어보지 않고 있다. numbers 에 주어진 순서대로 하나의 이진트리로 해당 수를 표현할 수 있다면 1을, 표현할 수 없다면 0 이진트리에 속해있는 것이 포화이진트리이다. - 이진트리는 자식노드가 최대 2개인 트리이다. - 포화이진트리는 이진트리이면서 모든 레벨이 노드로 꽉 차 있어야 한다. 그렇기 때문에 이 문제는 해당 수를 이진수로 표현하고 포화이진트리로 형태로 만들면서 이것이.. Algorithm/프로그래머스 2023. 4. 11.

• 

  백준 - 계단 오르기 문제 설명 계단오를때 점수를 받는다. 계단을 오를때 점수를 받을 수 있는 총 점수를 구하는 문제이다. 단 ,규칙이 존재한다. 연속된 3 계단을 밟아 점수를 얻을 수 없다. 마지막 계단은 반드시 밟아야 한다. TRY 계단의 최대 입력으로 들어올 수 있는 수는 300이다. 이것은 기본적으로 완전탐색을 한다면 시간 초과가 나올 수 있다. 다이나믹으로 풀어낼 수 있다. dp[i]=MAX(dp[i-2]+ dp[i-3] + stair[i-1])+ stair[i] 위점화식을 해석하면 현재 계단에서 뒤로 두번째 칸을 밟아왔던 값 ,뒤로 세칸 밟아왔던 값 + 뒤로 한칸 밟은 값 이다. dp[i-3] + stair[i-1]은 역속된 3칸을 밟지 않아야한다는 조건때문이다. dp[i-1]만 보면 dp[i-1]이 이미 연속된 .. Algorithm/백준 2023. 4. 11.