본문 바로가기

전체 글

알고리즘 문제를 풀면서, 스택 문제인지 구분하는 방법 백준에서 유명한 문제인, 오큰수를 풀어본 적이 있는가?풀어본 적이 없다면, 이번 기회에 한 번 풀어보는 것을 권장한다.만약 어렵다거나 풀지 못했다고 해도 걱정하지 말자. 당신은 혼자가 아니다.필자는 2년 전에도, 오늘도, 힌트 없이 풀어내지 못했다. 알고리즘 문제를 풀 때 가장 막막한 점이 무엇인가?대부분의 사람들은, 어떻게 푸는 지를 파악하는 것이라고들 한다. 나에게 이 오큰수는 언제나 그런 문제였고, 이 밖에도 수많은 오큰수스러운 문제들이 있었다. 그리고 최근에야, 나는 그런 문제들이 많이 포함된 유형을 발견했다.바로 '스택'이다. 가장 대표적인 자료구조이고, LIFO로 설명되면서, 일상에도 수많은 예제가 있는 그런 익숙한 녀석이다.그러나, 왜 항상 알고리즘 문제를 풀면 스택 유형이라는 것을 파악.. 더보기
유형 3개로 DP 정리하기 DP의 벽코테를 통과하기 위해서 다양한 유형을 공부해야하지만, 나에게 가장 어렵게 다가오는 유형은 그리디, DP 2개이다.둘 다 유형을 파악하는 것부터가 쉽지 않고, 유형을 파악해도 정해진 틀이 적어서 똑똑해야만(?) 풀 수 있다는 느낌이 든다. solved.ac에서 확인해보니, 현재 DP 문제를 딱히 많이 풀어본 것도 아닌 상태이다. 그래서 이번 기회에 대표적인 DP의 유형들을 정리해보고자 한다. + 대표유형을 정리한다고 해서 문제를 잘 풀 수 있을까 하는 의문이 있을 수 있다.이런 대표유형을 정리한다면, 단순히 대표유형과 유사한 유형이 나왔을 때만 도움이 되는 것이 아니라고 생각한다.대표유형을 통해서 DP에 대한 이해도가 높아질 수 있고, 문제를 분석하는 기준이 되어줄 수 있다. 따라서 이를 통해 D.. 더보기
책 <프로이트의 의자>를 읽고 느낀 점나는 줄곧 심리적인 요소에 관심이 많은 편이었다.고등학생 때 읽은 행동경제학 책을 보면서 내 흥미와 관심을 알아차리게 되었다.사람이 어떻게 생각하고 행동하는 지가 정말 재밌있었다. 컴퓨터공학을 전공하면서 "자연어처리" 수업을 들은 적이 있다.그 전까지는 AI에 대해 잘 모르는 대충만 아는 학생이었는데, 이 수업을 통해서 학부 수준의 상식을 쌓을 수 있었다.무엇보다 이 수업에서 가장 인상적이었던 것은, 재미였다.내가 이 수업을 4학년 때 들은 것이 아니라면 그동안 생각했던 진로를 틀어서 대학원을 갔겠다라는 생각까지 들었으니 말이다. 자연어 처리 수업에서 언급되는 지능, 인지와 같은 단어들이 난 너무나 흥미롭고 재밌게 느껴졌다.말하자면, 인지과학에 흥미가 있다고 할 수 있다.튜링머신과 같은 컴퓨터도.. 더보기
new ArrayList<>()와 new ArrayList()의 차이 개요알고리즘 문제를 풀다가 문득 그런 생각이 들었다.Java에서 new ArrayList()와 new ArrayList()의 차이가 무엇일까?꺽쇠의 역할이 무엇일까? 는 뭐지?아래와 같은 코드가 있다고 해보자. 이때, 제네릭 문법의 의미는 아래와 같다. 즉, new ArrayList()는 그냥 new ArrayList()인 것이다(앞에서 String으로 선언했으면 임.) Java에 var 과는 또 다른, 타입 추론 기능이 있었다는 걸 쓰면서도 모르고 있었다.컴파일러가 컴파일 타임에 안에 추론된 타입을 넣어준다고 이해하면 된다. 그러면 를 안쓰면 어떻게 되는거지?간단하다. Object 타입을 받는 ArrayList가 선언되는 것이다.물론 컴파일러는 simpleList 변수가 Integer 타입의 List.. 더보기
6월 3주차 회고 한 주가 지났다.저번주에는 멘탈이 많이 깨졌었고, 그걸 분석해보면서 좀 더 깨졌다면이번주는 조금 회복하면서 분석 내용 정리와 앞으로의 계획을 정리할 수 있었던 것 같다. 크게 아래와 같은 3가지 일이 있었다.1. 싸피 인터뷰2. 전국민 마음투자 지원사업 신청3. 취준 방향성 설정과 휴식 준비 싸피 인터뷰드디어 싸피 인터뷰를 하게되었다. 솔직히 막판에는 그냥 빨리 보고 싶다고 생각했다. 더 준비하기 귀찮아서..뭐 대외비니 뭐니 때문에 구체적인 이야기를 하기는 어렵지만..개인적으로는 잘 봤다고 생각한다. 사실 운이 좋게도 PT 면접 주제가 너무 나한테 유리한 주제였어서,면접 내용을 그쪽으로 유도하면서 잘 끌고 나갔다고 생각한다.더 떠들고 싶은데 시간이 부족하다고 느꼈다. 붙고나서 해야하는 고민이지만, 사실 .. 더보기
6월 2주차 회고 조금은 다사다난 했던 일주일이 지났다.앞으로는 가능한 매주 회고를 진행해보고자 한다. 공부와 취업의 방향성 정리군대에서 국방오픈소스 아카데미에 참여하고 공부하면서, 아 학교로 돌아가면 꼭 프로젝트 해봐야겠다 라는 생각이 강했다.그래서 복학하자마자 교내동아리에 들어갔다.나름 면접도 보고 들어갔는데, 진짜 벌벌 떨었던 기억이 난다. 뭐가 그렇게 무서웠을까? ㅋㅋ 지금 생각하면 조금 웃기다. 전역 이후에 혼자서 안드로이드 공부를 조금 했었고, 이 블로그에 정리를 했었는데(지금은 다 비공개 ㅎㅎ;)나중에 이야기해보니 그 점을 좋게 봐주셨다고 한다. 안드로이드 공부도 하고, 플젝도 해보고, 멘토도 해보고, 회장도 해보면서 많은 인연들을 얻었다고 생각한다.그 중에 교내 알바도 소개시켜주시면서 특히 큰 도움을 주셨던.. 더보기
프로그래머스 42861 : 섬 연결하기 https://school.programmers.co.kr/learn/courses/30/lessons/42861내가 풀고도 놀랐다. 풀 수 있을 줄 몰랐다. 생각의 흐름딱 읽고 감이 안 와서 문제를 분석해봤다. 예전에는 감이 안 오면 뭔가 조급해지고, 좌절감이 들었었는데이제는 문제 본문과 예제를(부족하다면 내가 추가해서) 좀 더 구체적으로 확인해보면자연스럽게 드는 생각들이 도움이 된다는 것을 알게 됐다.난 멍청이 까지는 아니니까 결국 문제에 적응하는 시간과 다양한 경험(예제)가 필요한 것이라고 생각하게 됐다. [분석 결과]1. 본문 내용 구체적으로 읽어보고 파악한 점- n이 100 밖에 안된다.2. 예제 따라 가보며 떠오르는 생각 정리하기- 음... 결국 도달만 가능하면 되는 거네- 그러면 다익스트라 .. 더보기
백준 9252 : LCS https://www.acmicpc.net/problem/9252DP 문제이다.진짜 모르겠어서, 낙담해버려 알고리즘을 4일 쉬게 만든 문제이다. 생각의 흐름우선 완전 탐색으로 하면 얼마나 걸릴까 생각을 해보았다.기본적으로 어떤 글자를 선택할 지를 결정하고, 비교하는 과정으로 진행한다고 가정했다.이때 어떤 글자를 선택하는 경우의 수가 곧 최종 시간 복잡도라고 봐도 되겠다.따라서$2^{1000} \times 2^{1000} = 2^{1001}$라는 어마어마한 수치가 나온다. 그래 우선 완전탐색은 안된다.그리고 예시를 따라가다보면, 그리디처럼 맹목적인 하나의 규칙이 있어보이는 것도 아니다.결국 완전탐색은 하면서도 효율적으로 해야하는 DP라는 감을 잡았다. 문제는 부분문제로 어떻게 쪼개야할 지 전혀 감이 오지 .. 더보기

티스토리툴바