선택과 집중

목차 이 글은 Notion에서 작성 후 재편집한 포스트입니다. 서론 옛날부터 패키지 구조를 어떻게 해야 효율적으로 관리할 수 있을까? 에 대한 관심이 정말 많았다. 많은 사람들이 코딩테스트, 혹은 알고리즘 역량 강화를 위한 문제풀이를 많이 한다. 그 때 마다 메인함수를 작성하자니, 손이 많이 가고, 기존 코드는 주석 처리하고.. 이런게 굉장히 비효율적이라고 생각했다. 그래서 어떻게 관리하시는지들 개발자 톡방에 물어봤다. 테스트 코드를 활용해본다 라.. 생각지도 못한 방법이었다. 어차피 개발을 한다면 테스트코드는 많이 작성하게 되어있으니, 이런 사소한 부분도 체득시키면 테스트 코드 환경에 익숙해질 것 같아서, 바로 적용해봤다. JUnit5와 IntelliJ 환경에서 진행했다. JUnit 적용 방법은 아래 ..

목차 문제 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 설계&풀이 아이디어는 옳게 접근했으나, 구현을 못했다. 요건은 간단하다. -를 기준으로 split 해주고, 나머지 애들을 다 묶어버리면 된다. 여러가지 케이스가 있는데.. 10+20-10 맨 앞이 +로 시작해서 묶이는 경우 10-20 맨 앞이 단순 숫자인 경우 10-20+30 맨 앞은 숫자, 뒤가 +로 묶이는 경우 10 하나만 들어오는 경우 10+20 +만 들어오는 경우 10-20..

목차 문제 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 설계&풀이 백트래킹의 기본문제다. 매번 DFS/BFS를 도망만 다녔다가 각잡고 제대로 공부해보고자.. N과M 시리즈를 시작해봤다. 요건은 간단하다. 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. - 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 백트래킹이란걸 아는 상태에서 DFS를 적용해보려고 했는데, 도저히 감..

목차 이 글은 Notion에서 작성 후 재편집한 포스트입니다. 개요 다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다 다익스트라 최단 경로 알고리즘은 ‘음의 간선’이 없을 때 정상적으로 동작한다. 음의 간선이란, 0보다 작은 값을 가지는 간선을 의미하는데, 현실 세계의 길(간선)은 음의 간선으로 표현되지 않으므로 다익스트라 알고리즘은 실제로 GPS 소프트웨어의 기본 알고리즘으로 채택되곤 한다. 다익스트라 최단 경로 알고리즘은 기본적으로 그리디 알고리즘으로 분류된다. 매번 ‘가장 비용이 적은 노드’를 선택해서 임의의 과정을 반복하기 때문이다. 참고 https://www.youtube.com/watch?..

목차 문제 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 설계 및 풀이 DP 문제이다. 사실 문제 유형을 어떻게 알아내는지는 좀 더 문제를 풀어봐야 알 것 같다. 처음엔 재귀로 풀었는데, 재귀로 풀다보니 시간 초과가 되어서 뭘까 고민하다가 결국 답지를 봤는데.. DP더라... 먼저, 재귀로 푼 코드다. cntZero = 0 cntOne = 0 def fibonacci(n): global cntZero global cntOne if n == 0: cntZero += 1 return 0 elif n == 1: cntOne += 1 return..

문제 www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는다. 합이 M을 넘지 않는 카드 3장을 찾을 수 있 www.acmicpc.net 설계 브루트포스는 '모든 경우의 수'를 탐색하는 알고리즘이다. 말 그대로 '무식한 힘' 알고리즘이다. 장점으로는 정답을 100% 찾아낼 수 있다는 것이지만, 단점은 당연히 효율이 극단적으로 떨어진다는 것이다. 하지만 브루트포스가 오히려 코드가 간결한 문제들이 몇 개 있다. 이런 문제 같은 경우다. 먼저 변수들을 선언해주고 필요한 정보를 입력해줬다. n과 m은 문제에 있는 ..