최근 “객체지향의 사실과 오해”라는 책을 통해서 객체지향에 대해 다시금 공부를 하고 있습니다.지난 내용에 대한 간단한 언급을 보고 이해를 하지 못했던 순간문득 책을 읽고 있다는 사실을 “나는 지금 공부를 하고있다”라고 오해하고 있는 저의 모습이 보였습니다.쉽게 설명하자면 글을 읽고만 있었지, 이해하진 않고 있었다. 라는 말이 될 것 같습니다.그래서 책 읽는 것을 멈추고, 무엇이 잘못되었는지 생각해보았습니다.여담 : 이런 비슷한 경우가 있었는데?최근에 Youtube Short 컨텐츠에 대해 우스갯소리로 이야기를 나눈 적이 있습니다.대화 속에서 “최근에 본 쇼츠 기억나?”라는 질문이 나왔고, 순간 아무것도 떠오르지 않아서 헛웃음만 자아냈었습니다.이 경험에서 ‘쇼츠는 시각적인 요소로 이해하기 쉽고, 투자하는 ..

H사 코딩테스트를 치고나서 생각했다.“내가 뭔가 잘못하고 있구나. 이대로는 안되겠다”간단한 복기180분 동안 총 2개의 문제를 풀면됐다.늘 그렇듯, 2개의 문제를 읽었다.둘 다 풀 수 있을거라 생각했다. (뭐 이정도면 3시간까지도 안들겠네..) 첫번째 문제를 풀기 시작했다.생각보다 쉽지않다. 풀다보니 애드혹 알고리즘 같았다. (모르면 못푸는..)시간이 2시간 지났다… 이대로는 안된다. 2번으로 가자.2번을 10분정도 봤을까? 매몰비용이 생긴 1번이 눈앞에 아른아른 거린다.“조금만 더하면 풀릴 것 같은데…”다시 1번으로 향했다. 규칙 찾으려고 A4 2장을 양면으로 빡지를 썻다.시간이 끝났다. “벌써?”“이대로는 오늘 잠을 못잘 것 같다. 끝을 봐야겠어.”이 후 30분 정도 인텔리제이에서 코드를 작성했다. ..

이번 글의 목적은 피보나치같은 대표적인 예시로 다이나믹 프로그래밍에 대해 뜯어보기 위함이 아닌저만의 접근(풀이)방식에 대해서 정리한 글입니다. 도움이 되셨다면 좋겠네요.도입부알고리즘 문제를 조금 풀어본 사람의 경우, 문제를 풀다보면 “DP로 풀어야하나?” 라는 감이 올 때가 있습니다.예를 들자면, 완전 탐색을 요구하는 문제인데 입력이 굉장히 클 경우, 일반적인 DFS, BFS로 풀 수가 없다고 느꼈을 때입니다. 아마 동전, 배낭문제와 같이 잘 알려진 문제들에 대해서는 곧바로 풀이를 할 수 있겠지만, 이러한 문제들은 코딩테스트에서 잘 나오지 않죠. 심지어 “DP로 풀어야하나?”라는 생각도 들지않게 나올 때도 있습니다.“DP로 풀어야겠다!”라고 생각을 해도 좀처럼 풀리지 않을텐데, 이유는 문제마다 공식이 제..

문제https://www.acmicpc.net/problem/17485 풀이다이나믹 프로그래밍 풀이접근법처음에는 다익스트라로 최소비용 구하면 되는 것 아냐? 라는 생각을 잠깐 했지만 출발지점이 1000개가 될 수 있기에 DP로 풀었다. 문제 조건해당 문제에서 각 원소의 위치에서 할 수 있는 행동은 3가지다.왼쪽 아래중간오른쪽 아래또 다른 조건으로는 이전 행동과 같은 행동을 취하지 못한다. dp로 풀이를 하기로 했으니 각 원소의 위치의 최선의 값을 어떻게 찾을지 생각하는 것 뿐이다.간단하게 생각하면 dp[i][j]는 3가지 이전해 + 현재값 중 최소값을 선택하면 될 것으로 보인다. 그러나 다음해를 구하기 위해서 이전해가 어떤 방향에서 진행된 값인지 알 필요가 있다.이를 위해 3차원 배열로 dp배열을 구성했..

문제https://school.programmers.co.kr/learn/courses/30/lessons/42897#qna 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이다이나믹 프로그래밍 풀이접근법나는 보통 DP 문제를 풀 때 각 원소에서 선택할 수 있는 최선의 값을 고르는 점화식을 생각한다.이 문제도 동일한 방식으로 접근했고, i번째 집을 털 경우와 털지 않는 경우 두 가지 중 최대값을 선택하는 점화식을 생각했다. 처음 생각한 점화식은 다음과 같다.DP[i] = Math.max(DP[i-1], DP[i-2] + money[i]) DP[i-1]의 경우..

개요관계형 데이터베이스 관리 시스템데이터를 테이블(관계) 형태로 관리행(Row)과 열(Column)로 구성테이블 간 관계를 통해 데이터를 조작하고 검색주로 SQL을 사용SQLRDBMS에서 데이터를 관리하기 위한 표준화된 언어로, 주로 데이터 정의(DDL), 데이터 조작(DML), 데이터 제어(DCL), 트랜잭션 관리(TCL) 명령어로 구성됩니다.DDL (Data Definition Language): 데이터베이스와 테이블 구조를 정의하는 언어예시: CREATE, ALTER, DROPDML (Data Manipulation Language): 데이터를 삽입, 수정, 삭제, 조회하는 언어예시: SELECT, INSERT, UPDATE, DELETEDCL (Data Control Language): 데이터베이..

문제https://www.acmicpc.net/problem/3020 풀이누적합을 활용한 풀이접근법N이 최대 200,000, H가 최대 500,000으로 들어오는 것을 조심해야 한다.단순히 O(NH)로 풀게 될 경우 시간초과가 발생하기 때문에 완전탐색 쪽으로는 생각하지 않았다. 그러면 어떻게 각 구간에 대해 효율적으로 탐색할 수 있을까? 처음에 떠올랐던 건 각 구간 별로 입력을 받을 때마다 갱신하면 되지 않을까였다.N개의 입력에서 갱신하는 방법에 대해 생각한 결과 각 구간 별로 누적합 원리를 활용해서 종유석 | 석순 각각에 대해 카운팅 해준 다음, 누적합을 구하는 방식으로 풀이했다.결과에 대해서는 i구간에 대해 종유석[i] + 석순[i]의 합이 개똥벌레가 부숴야하는 장애물의 개수이며, 최소값을 구한 후 ..

문제https://www.acmicpc.net/problem/1339 풀이자료구조를 활용한 그리디 풀이첫번째 접근법 (오답)다음과 같은 우선순위를 통해서 알파벳에 대한 값을 메겼습니다.자리수가 높은 알파벳 우선같은 자리수라면 개수에 따라서반례2ABBB----wrong : 186ans : 188해당 접근으로는 바로 뒷자리수에 나오는 알파벳에 따라 잘못된 결과가 측정될 수 있었습니다. 두번째 접근법그렇다면 위와 같은 반례에 대해서 어떻게 풀이를 해야할까요?처음에는 단순히 바로 뒤에 나오는 각각의 자리수에 대해서 알파벳의 개수를 측정하고, 비교하려 했는데요. 이렇게 될 경우 로직이 굉장히 복잡해지고 어떻게 코드를 작성해야할지 모르겠더라구요.코드를 아예 지우고 다시 생각을 해본 결과 다음과 같은 로직을 생각할 ..