이름 잘 짓는 규칙 의도 분명히 밝히기 따로 주석이 필요 없을 정도로 변수의 존재 이유 수행 기능 사용 방법 그릇된 정보 피하기 널리 쓰이는 의미가 있는 단어를 다른 의미로 사용하면 안됨 - hp, aix, sco (유닉스 플랫폼이나 변종 가리키는 이름이라 사용하면 안됨) 실제 List가 아니면 accountList라고 명명하지 않음 - 계정 담는 컨테이너가 실제 List가 아니면 안됨 - accountGroup, bunchOfAccounts, Accounts 라 명명할 것 - 실제 컨테이너가 List라도 컨테이너 유형을 이름에 안 넣는게 좋음 서로 흡사한 이름 사용하면 안됨 유사한 개념은 유사한 표기법 사용할 것 일관성 떨어지는 표기법은 그릇된 정보임 의미 있게 구분하기 컴파일러나 인터프리터만 통과하려..
나쁜 코드를 짜면 계속해서 나쁜 코드를 짜게 되고 결국 효율성이 극도로 떨어져서 0에 수렴하게 됨 코드 읽는 시간과 짜는 시간 비율이 10 대 1을 훌쩍 넘겨서 처음부터 코드를 잘 짜야 함 체크아웃할 때보다 좀 더 깨끗한 코드를 체크인한다면 코드는 절대 나빠지지 않음 -> 변수 이름 하나 개선, 조금 긴 함수 하나 분할, 약간의 중복 제거, 복잡한 if문 하나 정리하는 것으로 충분함 이 책은 Agile Software Development: Principles, Patterns, and Practices (PPP)의 프리퀄임 PPP에서 설명하는 다섯 가지 원칙 SRP (The Single Responsibility Principle) : 클래스에는 단 한가지 변경 이유만 존재해야 함 OCP (The Op..
문제 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 사이에 'X' 혹은 '+'를 넣어 만들 수 있는 가장 큰 수 구하기 모든 연산은 왼쪽부터 이뤄진다고 가정 입력 조건 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어짐 (1
문제 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 함 만들 수 있는 모험가 그룹의 최대 개수 구하기 입력 조건 첫째 줄에 모험가의 수 N이 주어짐 (1 값 갱신해주기 (count는 0으로, answer ++) #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; int n[100001]; int main() { int N; int i; int answer = 0; int count = 0; scanf("%d", &N); for (i = 0; i < N; i++) { scanf("%d", &n[i]); } sort(n, n + N); for (i = 0; i < N; i++) { coun..
다익스트라 알고리즘 최소 비용을 구해야 할 때 사용 가능 한 지점에서 다른 특정 지점까지의 최단 경로 구해야 할 경우에 사용 가능 음의 간선이 없을 때 정상 동작함 (현실에는 음의 간선의 길이 없어서 GPS의 기본 알고리즘으로 사용됨) 그리디 알고리즘 -> 매번 가장 비용이 적은 노드를 선택해 과정을 반복함 동작 원리 dist[] 에 비용 저장, INF로 초기화 되어 있음 출발 노드 설정, 최단 거리 초기화 (dist[] INF로 초기화) 출발 노드를 방문한 노드로 체크하기 출발 노드와 연결되어 있고 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택, 방문했다고 체크 이 노드에서 다른 노드로 가는 비용을 계산해 dist[] 갱신 3,4 과정을 반복 구현 방법 동작 원리대로 구현하기 - 시간 복잡..
dp[i] = dp[i - 1] +1; dp[i] = dp[i - 1]++; dp[i] = ++dp[i - 1]; 위의 세 연산 값이 전부 다르게 나옴 ++,--는 간단한 변수 값 변화에만 사용하기!! 첫 번째 값 : 제대로 나옴 두 번째 값: dp[i]에 dp[i-1] 값만 계속 넣고 dp[i-1]++ (의미 없음) 을 해서 값이 0만 저장됨 세 번째 값: dp[i]에 ++dp[i] 값을 넣은 후 dp[i-1](의미 없음)을 해서 값이 더 저장됨
동적 계획법 (Dynamic Programming) 하나의 문제는 한번만 풀게 하는 알고리즘 메모리 공간을 약간 더 써서 연산 속도를 비약적으로 증가 시킬 수 있음 메모이제이션 - DP를 구현하는 방법 중 하나 - 메모리(배열)에 한 번 구한 결과를 메모해두고 같은 식을 호출하면 그대로 가져옴 (캐싱) 분할 정복과 다른점 : DP는 분할한 문제들이 서로 영향을 미침 DP 구현 방법 탑다운(하향식) 방식 : 재귀를 이용해 DP 푸는 방법 (큰 문제 해결 위해 작은 문제 호출) 보텀업(상향식) 방식 : 반복문 이용해 DP 푸는 방법 (작은 문제부터 답을 도출함) 1. 점화식 찾기 2. dp 값이 정해져 있다면 넣고 시작하기, dp 초깃값은 큰 값 혹은 작은 값 넣기 3. 모든 dp의 값을 (점화식으로 구한 ..
이분 탐색 배열이 정렬되어 있어야 사용 가능 반으로 쪼개면서 탐색함 시간 복잡도 O(logN) (순차 탐색은 O(N)) 시작점, 중간점, 끝점을 가리키는 변수를 가짐 재귀, 반복문으로 구현 가능 1. 시작점, 중간점, 끝점 (left, mid, right) 정하기 2. 중간점과 찾는 값 비교 후 작으면 right를 mid-1로, 크면 left를 mid+1로 한 후 mid 값 다시 정하기 3. 2번을 반복 Parametric Search 최적화 문제를 결정 문제로 바꿔 푸는 것 이분 탐색으로 결정 문제를 해결하면서 범위를 줄여 최솟값, 최댓값을 찾음 결정 문제인지 아닌지의 차이 (이분탐색과) 1. left, mid, right를 정한 후 mid가 조건을 만족하는지 확인 2. 만족하지 않으면 mid 이전의 ..
