인생자취

1. 들어가기지난 글에 이어 그래프 탐색 알고리즘에 대해서 다뤄볼 것이다. 이번 글에서는 너비 우선 탐색(BFS;Breadth First Search)을 다뤄보겠다. 너비 우선 탐색은 시작 점으로부터 트리와 가까운 꼭짓점을 모두 탐색한 뒤, 먼 꼭짓점까지 확장하는 규칙을 가지고 있다. 이와 관련해서 좀 더 자세하게 알아보자. 2. 너비 우선 탐색너비 우선 탐색은 시작점으로부터 인접한 꼭짓점을 모두 탐색하고, 인접한 꼭짓점을 시작으로 다시 인접한 꼭짓점들을 탐색하는 탐색이다. 다시 말하면, 깊이가 1씩 증가함에 따라 시작점과 가장 가까운 노드들을 모두 탐색하는 기법이라고 볼 수 있다. 깊이 우선 탐색의 시작점을 기준으로 최대 깊이를 우선으로 탐색하는 기법과는 대조적이다. 너비 우선 탐색도 예시를 통해 알아..

1. 들어가기 지난 글에서는, 그래프에 표시된 모든 노드를 탐색하는 방법으로 시작점을 기준으로 가장 먼 곳을 탐색하는 방법인 DFS를 살펴봤다. 필자는 이번 글에서 DFS를 베이스로 하여, N-Queen 문제를 통해 백트래킹을 적용하는 방식을 살펴볼 것이다. DFS로 완전탐색을 하지만, 백트래킹을 통해 탐색의 필요 여부를 따져볼 수 있다. 탐색의 필요 여부는 다음 예에서 확인해 볼 경우로 계산만 해봐도 뚜렷하게 알 수 있다. 5X5 체스판에 퀸이 놓일 수 있는 경우를 계산한다면, 모든 경우의 수는 5^5 가지가 되는데, 백트래킹으로 조건을 둔다면, 필요하지 않은 경우에 대해서는 더 따져볼 필요가 없게 된다. 그래서 경우의 수가 위의 값 보다는 확연하게 줄어들게 된다. 이와 관련해서 더 자세하게 살펴보도록..

1. 들어가기 그래프에 표시된 모든 노드를 탐색하는 방법으로는 시작점을 기준으로 일정한 방향으로 탐색하는 것이 효율적이다. 이때, 효율적인 탐색 방법으로는 깊이 우선 탐색(DFS;Depth First Search)과 너비 우선 탐색(BFS;Breadth First Search)이 대표적이다. 필자는 이번 글에서 깊이 우선 탐색 알고리즘을 중심으로 다뤄볼 것이다. 2. 깊이 우선 탐색 그래프 정점(꼭짓점)이 1, 2, 3, 4, ... , N 개가 있다고 하자. 깊이 우선 탐색은 시작점을 1 이라고 할 때, 1 에서 인접한 꼭짓점 중 아직 탐색하지 않은 꼭짓점 2에 방문하고, 꼭짓점 2에 인접한 꼭짓점 중 아직 탐색하지 않은 꼭짓점 3를 반복한다. 이때 인접한 모든 꼭짓점을 방문한 경우, 이전에 마지막으로..

좋은 개발자가 되는 길은 멀고도 험하다. 매일 치르는 코딩테스트도 그렇고, 평생을 공부해야하는 개발직군에서 일하면서 최근 한달동안 공부한 만큼을 공부했을까 싶다. 짬을 내서 심도 있게 공부한 적은 있었으나, 지금 생각해보면 부족했다. 낮/밤이 바뀌는지도 모를만큼 몰두한 날들을 돌아보니, 지난달을 회고하는 글을 꼭 남겨놔야겠다는 생각이 들었다. 좋은 개발자가 되는 본 과정을 수료하기까지 남은 5개월도 지금의 마음을 잃지 말라는 바람을 더해서 말이다. 1. 언어적응을 위한 문제풀이 언어를 이것저것 사용하면서 언어에 대한 이해도의 깊이는 얕았다. 게다가 언어 전환이 빠르게 이뤄지지 못해서 엄청나게 고생을 해왔다. 개발 언어 학습에서 임계점까지는 빨리 도달하지만 중급의 시작인 임계점을 넘지 못한 언어들만 알고 ..

1. 들어가며 백엔드 신입 개발자가 쌓아야 하는 역량은 자료구조와 알고리즘을 이해하고 있고, 이를 코드에 적용하는 것이다. 게다가 시간복잡도는 낮고, 코드는 잘 읽히게 코드 컨벤션을 고려해서 코드를 작성해낼 줄 안다면 기본은 갖추고 있다고 할 수 있을 것이다. 그래서 정해진 시간 내에 알고리즘과 자료구조를 잘 녹여낸 코드를 작성해내는 역량이 중요하다보니, 실무 전에 개발 역량을 코딩테스트로 체크하기도 한다.(기업 by 기업이지만, 필자는 코딩테스트를 요구하는 기업에 지원하여 코딩테스트를 여러번 본 경험이 있다. 애석하게도 통과된 적은 아직 없다.) 코딩테스트는 앞서 언급한 자료구조, 알고리즘을 잘 이해하고 있는지를 정량적으로 평가할 수 있다보니, 채용 시스템에서 인터뷰 전에 코딩테스트를 응시하도록 하고 ..

지난시간에 스택 오버 플로우를 제공한 백엔드 로드맵을 근거로 백엔드 개발자로써 준비할 것들에 대해 몇 자 남기고자 합니다. - 1. 백엔드의 기본은 알고리즘이자.. 자료구조이자.. 알고리즘이자.. 자료구조이자... 개발자의 핵심기술인 논리력을 제대로 갖추기 위해서 알고리즘, 자료구조 공부를 해야 할 것입니다. 공부 방법으로는 관련 문제풀이를 매일 하는 것입니다. 로직을 구현할 때 문제를 읽고 어떤 알고리즘을 적용해야 하는지에 대해서도 반복적으로 패턴화된 학습을 진행할 계획입니다. 그래서 문제를 읽고 어떤 자료구조와 알고리즘을 적용해야 하는지를 바로 기억해낼 수 있는 연습을 할 것입니다. 2. 운영체제 학습 소프트웨어가 동작하기 위해서는 동작 환경이 필요합니다. 그런 이유에서 소프트웨어를 관리하는 운영체제..

https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr이진 탐색 개념을 이해하기 위해 본 문제를 풀이하였다. 1. 문제 요약이 문제를 요약해보면 다음과 같다.1) 주차장의 요금표와 차량이 들어오고 나간 기록이 input 데이터로 주어짐(단, 차량 출입 기록에 들어온 기록만 있는 경우에는 23:59에 출차한 것으로 간주.)2) 차량별로 주차 요금을 계산(단, 주차요금 계산 시 단위요금을 계산하는데, 단위 요금 계산에서 발생하는 소수 계산은 올림으로 처리.)..

독자님은 코딩테스트 문제를 풀면서 밤을 새본 적이 있나요? 저는 있습니다. :)... 독자님은 밤을 새시지 마시라는 의도로 본 글을 쓰게 되었습니다. 사실 구글링만 해보면 되는 결과를 안보고 풀겠다고 고집을 부리다가 또 밤을 새버렸네요. 지난 6월에 주에 한번 꼴로는 밤을 새본 것 같습니다. 이 문제도 그러한 문제 중 한 문제라고 보시면 되겠습니다. 정말 간단하게 풀어지는 풀이법은 dp로 이차원 배열로 정의해서 메모이제이션 방식으로 푸는겁니다. 그런데 저는 1차원 배열인 dp로 풀기 위해서 많은 시간을 사용했습니다. 고집을 포기하는 순간 행복해지는 거더라구요!_! 어쨌든. https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ ..

https://school.programmers.co.kr/learn/courses/30/lessons/92341 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr주차요금 계산 문제를 풀고 나서 생각해보면 너무 간단한 건데, 자꾸 실수하는 내용이 있어서 이를 기록하기 위해서 글로 남긴다. 1. 문제 요약이 문제를 요약해보면 다음과 같다. 1) 주차장의 요금표와 차량이 들어오고 나간 기록이 input 데이터로 주어짐(단, 차량 출입 기록에 들어온 기록만 있는 경우에는 23:59에 출차한 것으로 간주.) 2) 차량별로 주차 요금을 계산(단, 주차요금 계산 시 단위요..

# 6 Heap 자료구조에 관하여 다음 그림과 같이 간단하게 표현하였습니다. 더 보기 https://www.acmicpc.net/problem/24174 24174번: 알고리즘 수업 - 힙 정렬 2 2 5 1 4 3(heapify(A, 2, 5)) -> 2 3 1 4 5(heapify(A, 1, 5)) -> 1 3 2 4 5(A[1] A[5]) -> 5 3 2 4 1(heapify(A, 1, 4)) -> 2 3 5 4 1(A[1] A[4]) -> 4 3 5 2 1(heapify(A, 1, 3)) -> 3 4 5 2 1(A[1] A[3]) -> 5 4 3 2 1(heapify(A, www.acmicpc.net 내용과 관련한 오류는 댓글에 남겨주시면 수정하겠습니다. :) 끝까지 읽어주셔서 감사합니다.