JS 코딩테스트에서 상황별로 유리한 반복문과 함수에 대한 내용을 다룹니다. 시간복잡도 O(n)으로 동일하다. for for (let i = 0; i < 배열.length; i++) { /* ... */ } 반복 시작점, 끝점, 증분 커스텀 가능 return제어 O for ... of for (const item of 배열) { /* ... */ } 배열에서 값만 취할 때 사용 return제어 O forEach와 다르게 iterable 객체면 다 순회가능 cf. for...in 은 객체를 순회 or 인덱스값이 필요할 때 용이 (배열도 객체이긴 하지만, key인 index값만 가져올 수 있기 때문에 배열에서는 for...of가 유리하다) map const arr = ['1', '2', '3']; const ..
0. 왜 자동화를 시작하게 되었나 이전 프로젝트에서는 PR 하나마다 스크린샷과 영상을 첨부했으나, GUI와 기능만을, 그것도 수동으로 확인할 수 있었다. 각자의 개발환경이 다르다 보니 빌드 에러를 제대로 확인하지 않고 PR이 병합되는 상황이 발생했다,, ➡️ CI와 CI 자동화의 필요성 사실 vercel에서는 commit과 PR을 기준으로 한 CD 자동화를 코드 없이도 제공한다. 하지만 문제는 난 거지이고... 팀 플랜을 이용하기엔 돈이 아깝다는 것이다. (즉 organization으로 판 레포를 직접 배포할 수 없었다.) 그래서 다들 많이 사용하는 방법인, 팀 레포를 개인 레포로 fork해온 다음 개인레포를 배포하는 방법을 선택했는데, 이게 차아아암 귀찮다. 왜냐하면 포크한 내 레포는 당연하게도 항상 ..
해왔던(할) 활동들 전국 연합 IT 동아리 피로그래밍 17기 (2022.6.28 ~ 2022.8.23) 신촌 연합 IT 동아리 CEOS 16기 • FE (2022.9.7 ~ 2023.2.10) 외주연계형 IT 동아리 CMC 13기 • Web (2023.5.27 ~) 여기어때 QA팀 인턴 (2023.7.3 ~) 오픈소스 컨트리뷰션 아카데미 Backend.AI 멘티 • FE (2023.7.8 ~) 배포한(할) 프로젝트들 그룹핑 (2022.8.2 ~ 2022.8.23) Welcome to the DMZ (2022.11.4 ~ 2022.12.18) 1인가구를 위한 숏폼 레시피 서비스 Recipeasy • FE (2022.10.07 ~ 2023.1.28) 동아리를 위한 그룹웨어 Waldreg • FE (2023...
1️⃣ 매개변수로는 그래프와 시작점 받기 def bfs(graph, start): 2️⃣ deque() 활용하여 queue 생성 queue = deque() 3️⃣ 시작점 방문하고 큐에 시작 인덱스 추가 visited[start] = True queue.append(start) 4️⃣ queue가 빌때까지 반복 큐에서 가장 먼저 들어갔던 인덱스 꺼내서, 해당 인덱스와 연결된 노드 순회 while queue: cur = queue.popleft() for node in graph[cur]: 5️⃣ 만약 노드를 방문하지 않았다면, 방문하고 큐에 해당 노드 인덱스 추가 if not visited[node]: visited[node] = True queue.append(node)
1️⃣ left right 설정하기 2️⃣ while True 반복, mid 설정 while True: mid = (left+right)//2 3️⃣ mid 값을 이용하여 주어진 조건에 만족하는지 체크하기 위한 값 구하기 count = 0 for line in lines: count += line//mid 4️⃣ left > right 면 반복 끝내고 값 출력 if left > right: print(mid) break 5️⃣ 주어진 조건 만족에 따라 left와 right 값을 조절한다 if count < n: right = mid - 1 else: left = mid + 1 예시 문제 BOJ 1654
0. 이항계수란 - n개 중 k개를 뽑는 조합의 수 - 이항계수의 성질 1. n개 중에 k개를 뽑는 것과 n개 중에 n-k개를 뽑는 경우의 수는 같다 (뽑지 않을 것을 정하는 것과 뽑을 것을 정하는 것은 같다) 2. n-1개 중에 k개를 뽑는 경우의 수와(1개 포함X) n-1개 중에 k-1개를 뽑는 경우의 수(1개 포함O)를 더하면 n개 중에 k개를 뽑는 경우의 수이다 3. nC0부터 nCn까지의 합은 2^n 이다 1. 분할정복을 이용한 이항계수 구하기 1.1 알고리즘 진행과정 0️⃣ nC0 혹은 nCn 은 항상 1이다 1️⃣ 나머지 경우는 이항계수의 2번 성질을 활용하여 구현 시간복잡도가 O(n!)이라서 엄청나게 비효율적.. 1.2 코드 def bino(n, k): if k == 0 or n == k:..
0. 플로이드 워셜 알고리즘이란? - 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용 - 매 단계마다 현재 노드를 거쳐 가는 노드를 기준으로 알고리즘을 수행 - DP - 최단 거리 정보 저장 1. 알고리즘 진행과정 0️⃣ 초기 거리 테이블 설정 - 연결되지 않은 간선에는 무한대 - 자기 자신은 0 - 이외 간선들은 주어지는 거리 1️⃣ N번 돌면서 현재 노드 선택 >> 현재 노드를 거쳐서 지나가는 모든 경우를 고려 2️⃣ N^2번 돌면서 현재 노드를 거쳐 가는 모든 경로 순회 3️⃣ 원래 기록된 거리보다 현재 노드를 거쳐서 지나가는 거리가 더 짧다면 갱신 (직접 연결된 간선은 업데이트 X) -> O(N^3)의 시간복잡도를 가진다 2. 점화식 D[i][j] = min(D[i]..
0. 행렬 곱셈 방법 아이패드 있을때 추가하기.. n * m 행렬과 m* k 행렬의 곱! 1. General Solution 1.1 브루트포스 # 일반적인 3중 반복문 행렬 곱셈 answer = [[0 for _ in range(k)] for _ in range(n)] for f in range(n): for s in range(k): for j in range(m): answer[f][s] += a[f][j] * b[j][s] 1️⃣ n번 반복하면서 첫번째 행렬의 행을 순회한다 2️⃣ k번 반복하면서 두번째 행렬의 열을 순회한다 3️⃣ m번 반복하면서 곱셈을 진행한다 ➡️ Θ(n^3)의 시간복잡도를 가진다 1.2 분할정복 8번의 곱셈이 필요하다 8번의 덧셈이 필요하다 ➡️ Θ(n^3)의 시간복잡도를 가..
