- [ 공부/Git ][Git] Commit message 규칙2023-12-30 09:04:06개인 프로젝트 마이그레이션 과정 중 중구난방인 커밋메시지로 히스토리 확인이 어렵다.. 그래서 찾아본 커밋 메시지 작성 규칙 목적 커밋 메시지 스타일을 구조화해 일관성 있게 사용하는 이유! 코드 리뷰 시간을 단축하고 능률적으로 처리하기 위해서 변경 사항을 이해해는데 도움을 주기 위해서 코드만으론 설명이 어려운 "왜 이렇게 했을까"를 설명하기 위해서 추후 작업할 사람이 왜/어떻게 변경 사항이 만들어졌는지 이해하는데 도움을 주고 문제 해결과 디버깅을 쉽게 만들기 위해서 Commit message 규칙 ① 제목과 본문을 빈 행으로 구분 ② 제목을 50글자 내로 제한 ③ 제목 첫 글자는 대문자로 작성 ④ 제목 끝에 마침표 넣지 않기 ⑤ 제목은 명령문으로 사용하며 과거형을 사용하지 않는다 ⑥ 본문의 각 행은 72글..
- [ 공부/알고리즘 ][알고리즘] 이진탐색2023-12-29 09:12:51이진탐색 Binary search 데이터가 정렬되어 있는 상태에서 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다 O(logN) 시간 복잡도를 가진다 이진 탐색 동작 # 정렬 기준 오름차순 ① 현재 데이터셋의 중앙값을 선택 ② 중앙값 > 타깃 데이터 → 중앙값 기준으로 왼쪽 데이터셋 선택 ③ 중앙값 < 타깃 데이터 → 중앙값 기준으로 오른쪽 데이터셋 선택 ④ 1~3 과정을 반복하다가 중앙값 == 타깃 데이터일 때 탐색 종료 → 정렬 기준이 내림차순일 땐 2~3번 조건 반대로 실행 N개의 데이터에서 log(N)번의 연산으로 원하는 데이터의 위치를 찾을 수 있다 관련 문제보기 백준 1920번 수 찾기
- [ 기록/백준 ][백준 / 자바] 24313번 알고리즘 수업 - 점근적 표기 12023-12-29 07:53:43https://www.acmicpc.net/problem/24313 24313번: 알고리즘 수업 - 점근적 표기 1 f(n) = 7n + 7, g(n) = n, c = 8, n0 = 1이다. f(1) = 14, c × g(1) = 8이므로 O(n) 정의를 만족하지 못한다. www.acmicpc.net 문제 오늘도 서준이는 점근적 표기 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 알고리즘의 소요 시간을 나타내는 O-표기법(빅-오)을 다음과 같이 정의하자. O(g(n)) = {f(n) | 모든 n ≥ n0에 대하여 f(n) ≤ c × g(n)인 양의 상수 c와 n0가 존재한다} 이 정의는 실제 O-표기법(https://en.wikipedia.org/wiki..
- [ 기록/백준 ][백준 / 자바] 10773번 제로2023-12-28 09:43:12https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 문제 나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다. 재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다. 재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다. 재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알..
- [ 기록/백준 ][백준 / 자바 ] 2920번 음계2023-12-28 09:37:26https://www.acmicpc.net/problem/2920 2920번: 음계 다장조는 c d e f g a b C, 총 8개 음으로 이루어져있다. 이 문제에서 8개 음은 다음과 같이 숫자로 바꾸어 표현한다. c는 1로, d는 2로, ..., C를 8로 바꾼다. 1부터 8까지 차례대로 연주한다면 ascending, 8 www.acmicpc.net 문제 다장조는 c d e f g a b C, 총 8개 음으로 이루어져있다. 이 문제에서 8개 음은 다음과 같이 숫자로 바꾸어 표현한다. c는 1로, d는 2로, ..., C를 8로 바꾼다. 1부터 8까지 차례대로 연주한다면 ascending, 8부터 1까지 차례대로 연주한다면 descending, 둘 다 아니라면 mixed 이다. 연주한 순서가 주어졌을 때..
- [ 기록/백준 ][백준 / 자바] 1920번 수 찾기 - 이진탐색2023-12-28 04:37:49https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에..
- [ 기록/백준 ][백준 / 자바] 10250번 ACM 호텔2023-12-27 17:22:48https://www.acmicpc.net/problem/10250 10250번: ACM 호텔 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 각 테스트 데이터는 한 행으로서 H, W, N, 세 정수 www.acmicpc.net 문제 ACM 호텔 매니저 지우는 손님이 도착하는 대로 빈 방을 배정하고 있다. 고객 설문조사에 따르면 손님들은 호텔 정문으로부터 걸어서 가장 짧은 거리에 있는 방을 선호한다고 한다. 여러분은 지우를 도와줄 프로그램을 작성하고자 한다. 즉 설문조사 결과 대로 호텔 정문으로부터 걷는 거리가 가장 짧도록 방을 배정하는 프로그램을 작성하고자 한다. 문제를 단순화하기 위해서 호텔은 직사각형 모..
- [ 공부/알고리즘 ][알고리즘] BFS 너비 우선 탐색2023-12-27 16:06:28너비 우선 탐색 Breadth-First Search 그래프를 완전 탐색하는 방법 중 하나 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘 FIFO 선입선출 방식으로 탐색하므로 Queue 자료구조 이용하는 특징을 가지고 있다 O(노드 수 V + 에지 수 E)의 시간 복잡도를 가진다 탐색 시작 노드와 가까운 노드를 우선하여 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장 BFS 동작 방문했던 노드는 다시 방문하지 않으므로 방문한 노드를 체크하기 위한 배열 필요 그래프를 인접 리스트로 표현 탐색을 위해 스택이 아닌 큐를 사용 1. BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화 BFS를 위해 필요한 초기 작업 인접 리스트로 그래프 표현..