서론지난번 재귀 포스팅에 이어 이번에는 그리디 알고리즘에 대해 알아보고자 한다. 이번 포스팅은 이 강의를 참고했다. 가능하다면 이번 포스팅에서 문제도 다룰 예정이고 만약 안된다면 다음 포스팅에서 마저 문제를 다뤄보겠다. 적을 내용이 얼마 없다면 바로 문제 풀것임.그리디 알고리즘이란?  현재 최적인 답을 근시안적으로 택하는 알고리즘 = 관찰을 통해 탐색 범위를 줄이는 알고리즘이다. 일반적으로는 관찰을 통해 탐색 범위를 어떻게 줄일지(=시간 복잡도를 낮출 지) 생각하는데, 이 때 탐색범위를 줄여도 올바른 결과를 낳는다는 사실이 증명이 되어야 한다. 증명이 안된다면 베팅하는거라 단순 노가다 코딩 보다 못한 결과를 초래할 수 있다. 하지만 코딩 테스트에서 빠르게 고안하고, 올바르게 증명할 확률은 극히 드물다. ..

목차서론지난번 포스팅에 이어 이번에는 난이도가 있는 재귀 문제를 풀어보고자 한다. 삼각달팽이라는 문제로 프로그래머스에 있다. 문제 제목과는 다르게 예시부터 난이도가 있어보이는 생김새다. 아무튼 이번 포스팅에서는 해당 문제를 풀어보고 그 과정에 대해서 얘기하고자 한다. 설령 못풀어도 다른 사람 풀이 참고하는 한이 있어도 어떻게서든지 풀어볼 예정이다. 재귀 문제 다른 사람 풀이 분석풀이 방법을 엄청 생각해봤으나 도저히 재귀로 풀리지가 않아 다른 사람 풀이를 검색해봤다. 아니나 다를까 재귀로 푼사람은 거의 없었고, 재귀로 풀었다는 사람 보면 되게.. 복잡했다. 재귀 강의에서 for문과 재귀는 서로 왔다갔다할 수 있지만, 코드 복잡도와 돌아가면서 생기는 불필요한 메모리의 등가교환이라고 말했는데(내가 의역함ㅋㅋ...

서론지난번엔 BFS에 대해서 알아보았다. DFS도 알아보아야 하지만.. 다음주에 문제 풀고 DFS할 예정임. 아무튼 오늘은 재귀에 대해서 알아본 뒤, 직접 문제를 몇개 더 풀어보고자 한다. 사실 재귀보단, DP가 더 자주 출제된다. 하지만 DP를 하기 위해서는 재귀를 충분히 알아야 된다고 한다. 그래서 재귀를 몇문제 더 풀어보고 다음주에 DP로 넘어갈것임.간단한 재귀 이론영상에서 본 재귀 이론을 간단하게 언급하고자 한다. 재귀와 반복문은 서로 왔다갔다할 수 있다고 한다. 다만 재귀는 보긴 좋지만 소모하는 시간이 많으므로 애지간하면 반복문에서 해결하라고 한다. 자신을 여러번 호출하는데 이게 굉장히 비효율적이기 때문이다. 이후 DP에서 해소할 수 있는 무언가를 하는데 이건 재귀에 익숙해진 뒤 들어가는게 맞다..

서론지난 포스팅에서는 BFS를 이용한 개념과 문제를 풀어보았다. 이번 포스팅에서도 백준 BFS 문제인 BOJ2178을 풀어보겠다. 이전과 같이 처음에는 내가 어떻게 풀었는지 적을 것이고, 이후에는 답지를 참고해서 내 것과 비교할 예정이다. BOJ 2178 내가 푼 풀이과정 및 코드 문제를 보니 최단거리를 찾는 것이다. BFS를 택했다.(사실 BFS 영상에 나온거라 뇌빼고 BFS로 바로 들어가도 되지만 이렇게 접근하는 연습을 하는게 맞다고 판단함.) 최단 경로를 어떻게 접근할까 했다. BFS를 돌며 내가 지나는 칸이 1이면 -> 이전칸 +1을 하고 0이면 안지나 가는 가장 기본적인 툴을 생각했다. 그런데 1도 0도 아닌 값을 만났을 때를 고려해야됐다. 때문에 1이 아닌 칸을 만나면 -> 해당 값과 +1한 ..

서론지난번엔 BFS 개념에 대해 포스팅을 했다. 이번에는 BFS를 이용해 문제를 풀어보고자 한다. 원래 이 포스팅에서 여러가지 풀이를 남길 생각이었으나, BFS는 하나도 벅차다. 때문에, 이 포스팅에서는 백준 BOJ1926만 풀어보도록 하겠다.백준 BOJ 1926 문제 풀이 (내풀이)내가 1926 문제를  푼 과정은 다음과 같다. 1) 너비를 알아야 됨 -> 주변부 탐색 BFS 사용. 2) 총 drawing의 개수 -> 시작점이 하나가 아니기에 모든 그래프를 훑는 for문을 만들고 + 새로운 시작점이 나올때마다 체크하는 변수 필요 3) 새로운 시작점이 생기면 그 때 while queue: 문을 도는것이니 for문 안에 while문 넣기. 4) 마지막에 max값과 현재 너비 비교 후 갱신. 해서 풀은 코드..

서론코딩테스트 계획 포스팅에서 BFS 강의에 해당하는 내용이다. 지난번엔 배열에 대해 다루고, 풀어보았다면 오늘은 BFS에 대해 풀어보고자 한다. 내가 참고한 강의는 C++로 되어 있기 때문에 개념을 이해하는데만 참고하고 실제로 쓰이는 코드는 파이썬 코드로 작성하였다. 기본적인 개념을 숙지하고, BFS 코드가 돌아가는 과정을 알아보도록 한다. 다음 포스팅에서는 문제로 넘어갈것임. BFS 개념BFS는 Breadth First Search의 약자로, 너비를 우선으로 탐색(방문)하는 알고리즘이다. 흔히 DFS와 비교가 되는데 DFS는 깊이(Depth)우선 탐색임. BFS는 이해를 돕기 위해 다양하게 묘사가 된다. 내가 본 유튜브 강의에서는 그림판에서 flood fill을 묘사로 했다. 하지만 내가 가장 와닿았..

서론코딩테스트 계획 포스팅에서 이어지는 포스팅이다. 오늘은 배열에 대해서 문제를 풀어보았다. 배열은 너도 알고 나도 아는것이라 딱히 개념에 대해 적을게 없어보인다. 그러니 바로 문제로 넘어갈것임. 문제는 백준 10808 https://www.acmicpc.net/problem/10808를 풀었다. 내가 보는 강의에 나오기 때문. 배열 문제 - 백준 10808 내가 푼 과정나는 우선 l에다가 input을 받았다. 그리고 문제에서 소문자만 해당한다고 했다. 영어의 소문자는 26개라는...것을 외우지 않았다.. 그 언저리인건 알지만 아무튼 몰랐어서 백준에 있는 답 보고 하나하나셌다 허허. 아무튼 26개가 있으니 result에 0으로 구성된 26개의 열을 만들었다. 그리고 ord()를 사용해서 알파벳을 숫자로 ..