상어코딩

[LeetCode] 85. Maximal Rectangle (Java)문제 링크: https://leetcode.com/problems/maximal-rectangle/들어가며이 문제는 처음 보면 2차원 배열에서 가장 큰 직사각형을 찾아야 해서 꽤 복잡해 보인다.처음에는 모든 위치를 기준으로 직사각형을 확장해보는 식으로 풀고 싶었지만,그렇게 하면 경우의 수가 너무 많아진다.핵심은 이 문제를 행 단위로 잘라서 생각하는 것이다.각 행을 바닥이라고 보고 위로 연속된 1의 개수를 쌓아 올리면,매 행마다 하나의 히스토그램이 만들어진다.그러면 문제는 결국"각 행에서 만들어지는 히스토그램의 최대 직사각형 넓이 중 가장 큰 값을 구하라"로 바뀐다.즉, 2차원 문제를 1차원 문제인Largest Rectangle in H..

[LeetCode] 63. Unique Paths II (Java)문제 링크: https://leetcode.com/problems/unique-paths-ii/들어가며이번 문제는 Unique Paths 문제의 확장 버전이다.기본 문제에서는 로봇이 오른쪽 또는 아래쪽으로만 이동할 수 있었고, 시작점에서 도착점까지 가는 모든 경우의 수를 구하면 됐다.하지만 이번 문제는 중간에 장애물(obstacle)이 추가된다.즉, 단순히 이동 경로를 누적하는 것이 아니라 장애물이 있는 칸은 지나갈 수 없다는 조건까지 함께 고려해야 한다.문제를 보자마자 떠오른 건 결국 각 칸까지 오는 방법의 수를 저장해두는 방식이었다.그래서 2차원 배열을 이용한 DP로 접근했다.문제 설명m x n 크기의 격자가 주어지고,로봇은 왼쪽 위 ..

[LeetCode] 62. Unique Paths 풀이 회고백트래킹으로 시작해서 메모이제이션 DFS를 거쳐 1차원 DP로 정리한 과정 (Java)문제 링크: https://leetcode.com/problems/unique-paths/유형: 백트래킹으로 접근 가능, 하지만 정답 풀이는 다이나믹 프로그래밍체감 난이도: 처음에는 쉬워 보이는데, "경로를 다 가볼 것인가"와 "상태의 답을 저장할 것인가"를 구분하는 지점이 핵심인 문제1. 문제를 처음 마주했을 때문제를 처음 보면 가장 먼저 드는 생각은 단순하다.로봇은 오른쪽 아니면 아래쪽으로만 이동할 수 있으니,현재 위치에서 두 방향으로 계속 가 보면 결국 모든 경로를 셀 수 있지 않을까?실제로 이 생각 자체는 틀리지 않았다.정답을 빠뜨리지 않는다는 점에서는 ..

[LeetCode] 29. Divide Two Integers 풀이 회고반복 뺄셈으로 시작해서 비트 시프트로 넘어간 과정 (Java)문제 링크: https://leetcode.com/problems/divide-two-integers/유형: 구현(Implementation) + 비트 연산(Bit Manipulation)체감 난이도: 아이디어 자체보다, 금지된 연산 없이 나눗셈을 구현하는 과정이 더 까다로운 문제1. 문제를 처음 마주했을 때처음에는 정말 단순하게 생각했다.나눗셈은 결국 같은 수를 몇 번 뺄 수 있는지 세는 과정이니까,dividend에서 divisor를 계속 빼면서 몫을 세면 된다고 봤다.이 접근 자체는 틀리지 않았다.실제로 작은 입력에서는 잘 동작한다.문제는 이 방식이 너무 느리다는 점이었..

[프로그래머스] 이모티콘 할인행사(Java)완전탐색으로 접근은 맞았는데, 테스트 3개에서 시간초과가 발생했다.이번 글은 "어디서 시간이 터졌는지"와 "어떻게 구조를 바꿨는지"를 중심으로 정리한다.문제 링크https://school.programmers.co.kr/learn/courses/30/lessons/1503681) 처음 접근처음에는 visit[]를 방문 체크 + 할인율 저장 배열로 같이 사용했다.visit[i] == 0이면 아직 미결정visit[i] == 10/20/30/40이면 i번 이모티콘 할인율 결정아이디어 자체는 나쁘지 않았다. 방문 관리와 할인율 상태를 한 배열로 표현할 수 있기 때문이다.2) 시간초과가 났던 중간 코드아래 코드는 실제로 많은 케이스는 통과했지만, 3개에서 시간초과가 발생..

[LeetCode] 1481. Least Number of Unique Integers after K Removals 풀이 회고빈도 정렬이 보이기 시작한 순간 (Java)문제 링크: https://leetcode.com/problems/least-number-of-unique-integers-after-k-removals/유형: 구현(Implementation) + 그리디(Greedy)체감 난이도: 아이디어는 짧지만 구현 실수가 쉽게 나오는 문제1. 문제를 처음 마주했을 때처음에는 k번 삭제를 직접 시뮬레이션하면서 매번 "가장 적게 나온 값"을 찾으려고 했다.하지만 이 방식은 반복할수록 코드가 복잡해지고, 최소 빈도 탐색을 계속 해야 해서 비효율적이었다.이 문제에서 중요한 건 원소 하나를 지우는 과정이 ..

[LeetCode] 1424. Diagonal Traverse II 풀이 회고 — r+c 규칙이 보이기 시작한 순간 (Java)url : https://leetcode.com/problems/diagonal-traverse-ii/유형: 구현(Implementation) + 완전탐색 관점의 순회 설계난이도 체감: 아이디어는 짧고, 인덱스 실수는 쉽게 나오는 문제1. 문제를 처음 마주했을 때처음에는 이렇게 보였다.2차원 배열에서 대각선 순서로 꺼내면 된다.대각선은 위에서 아래로 내려가며 모으면 된다.그런데 이 문제의 입력은 int[][]가 아니라 List>라서,행마다 길이가 다를 수 있다.즉 "직사각형 배열"처럼 생각하면 바로 인덱스 에러로 이어진다.2. 내가 처음 막혔던 지점1) 합(sum)과 순서(ord..

[LeetCode 1347] Map으로 시작해서 Array로 최적화한 회고 (Java)문제 링크: https://leetcode.com/problems/minimum-number-of-steps-to-make-two-strings-anagram/description/유형: 문자열 + 빈도수 카운팅핵심 개념: 자료구조 선택(Map vs int[])과 제약 기반 최적화난이도 체감: 로직은 쉬움, "왜 이 구조를 고르는가"가 중요한 문제1. 문제 인식문제 요약은 간단하다.길이가 같은 두 문자열 s, t가 주어진다.t의 문자를 바꿔서 s의 아나그램으로 만들고 싶다.필요한 최소 변경 횟수를 구한다.처음 보자마자 든 생각은 이거였다."문자 개수 맞추기 문제네. 빈도수 세면 끝."문제의 본질은 결국 하나다.s에 비해..

[알고스팟] BOARDCOVER 풀이 회고 (Java)유형: 완전탐색(Brute Force) + 백트래킹(Backtracking)난이도 체감: 구현은 단순, 개념은 깊음1. 문제를 처음 마주했을 때BOARDCOVER는 겉보기에는 단순한 문제였다.보드는 #(막힌 칸)과 .(흰 칸)으로 구성된다.L자 모양의 3칸 블록을 사용한다.모든 흰 칸을 정확히 덮는 경우의 수를 구한다.처음 느낌은 이랬다.“블록 4가지 정의하고, 하나씩 놓아보면 되는 거 아닌가?”실제로 접근 방향 자체는 틀리지 않았다.하지만 “경우의 수를 세는 구조”를 제대로 만들지 못하면서 막히게 되었다.2. 나의 첫 접근 방식1) 흰 칸이 3의 배수인지 확인블록이 3칸이기 때문에 흰 칸 수가 3의 배수가 아니면 애초에 불가능하다고 생각했다.이 판단..