1주차 주제는 '숫자야구' 였습니다. 주제가 생각보다 간단하다고 생각해 기능 구현에 목표를 두기 보다는 올바른 구현 과정, 클린 코드들을 고려하며 코드를 작성하고자 했습니다. 따라서 구현 과정과 그 안에서의 고민들을 나누고자 합니다. 기능 요구 사항 ‘기능 요구 사항’을 먼저 작성하고 구현해 본 적이 없어, 기능들을 어떻게 나눠야 할지 오랜 시간 고민했습니다. 하지만 나눈 기능들에 따라 순서대로 개발하고 리팩토링을 진행하면서 보다 꼼꼼하고 계획적으로 진행할 수 있었습니다. 또한 더 좋은 구조나 방법이 떠올랐을 경우 ‘기능 요구 사항’을 업데이트하여 프로젝트의 방향성을 다시 세울 수 있었습니다. TDD 또한 TDD 방법론을 처음으로 도입해 보았습니다. 테스트로 제약사항을 설정하고 그것에 맞추어 코드를 작성..

문제를 풀다 보면 최단 경로와 관련한 문제들이 종종 출제된다. 물론 bfs나 dfs와 같은 완전탐색이 필요한 경우도 있지만, 대부분 다익스트라 알고리즘으로 해결이 가능하다. Dijstra 알고리즘은 기본적으로 최단 경로를 찾는 알고리즘이다. 즉 출발 노드로 부터 각 노드들의 최단 거리를 구할 수 있고, 경로 또한 계산이 가능하다. 주의할 점은 다익스트라는 양의 weight를 가지는 edge들이 있다는 가정이 필요하다. 기본적인 로직은 다음과 같다. 1. 출발 노드를 방문. 2. 해당 노드로 부터 연결된 노드들을 통해 각 노드들 마다 거리를 계산 후 저장. 3. 방문하지 않은 노드들 중 출발 노드랑 거리가 가장 작은 노드에 방문. 4. 새로 방문한 경로를 통해 계산된 새로운 거리와 기존에 저장된 최단 거리..

문제 출처 https://www.acmicpc.net/problem/1464 1464번: 뒤집기 3 세준이는 어떤 문자열 S를 뒤집으려고 한다. 문자열을 뒤집는 방법은 문자열의 길이를 N이라고 하자. i만큼을 뒤집는다는 소리는 그 문자열의 처음부터 정확하게 i개의 문자를 역순으로 뒤집는 www.acmicpc.net 문제 풀이 및 코드 해당 문제는 뒤집기 정렬에 관한 문제이다. 0~i번째까지만 뒤집기가 가능하다. 필자는 재귀를 이용하여 접근했다. 만약 가장 작은 알파벳이 뒤에 존재한다면, 앞에서 뒤집기를 하는 과정들이 무의미하다고 생각했고 가장 앞으로 오는 알파벳을 먼저 탐색했다. 따라서 가장 작은 알파벳을 찾되, 중복이라면 가장 뒤에 있는 값을 찾고자 했다. 해당 값을 m, index를 i라고 한다면 다..

예전에 정리를 하고 넘어갔었는 데, 오랜만에 알고리즘을 공부하다 보니 개념에 구멍이 생겨서 정리해보고자 한다! 해당 내용을 알기 전에 먼저 mutable, immutable에 대해 알아야한다. mutable : 변할 수 있다. immutable : 변할 수 없다. 즉 mutable인 변수는 수정이 가능하고, immutable인 변수는 수정이 불가능 하다는 소리. 예시를 들어 살펴보자 a = 1 b = a print(id(a), id(b)) b = 2 print(id(a), id(b)) print(a, b) 4301252912 4301252912 4301252912 4301252944 1 2 해당 예시를 살펴보면 처음 a, b는 id가 같다. 즉 같은 객체를 가르키고 있었다. 하지만 b = 2를 대입하면 ..

문제 출처 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제 풀이 및 코드 해당 문제는 dfs, bfs 문제로 경로마다 알파벳 종류를 파악해야 하는 문제였다. 필자는 bit연산을 이용해 알파벳을 저장했다. 알파벳이 26종류이니 a = 1, b= 2, c= 4이런식으로 사용했다. 따라서 dfs를 통해 경로가 진행될 때마다 해당 좌표의 알파벳을 지나왔는 지 체크하도록 visited라는 변수를 만들었다. 즉 visited에는 해당 경로를 ..

문제 출처 https://school.programmers.co.kr/learn/courses/30/lessons/178870 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 이제 "부분 합"이라는 단어가 나오면 자동적으로 'right까지의 합 - left까지의 합'을 떠올린다. 확실히 매번 합을 구하는 것보다, 먼저 i까지의 합을 계산하고 뺄셈을 이용하는 방식이 효율적이다. 해당 문제는 부분 합이 k가 되는 부분을 찾는 문제이다. 풀이는 간단하다. left, right를 0,0으로 두고 앞서말한 'right까지의 합 - left까지의 합'를 계..