본문 바로가기

모두보기

[코딩인터뷰] 백준 15684번 def is_completed(): global n global h global ladder for b in range(n): s = b for a in range(h): if 0 < s and ladder[a][s-1]: s -= 1 continue if ladder[a][s]: s += 1 continue if s != b: return False return True def dfs(count, a, b): global n global h global ladder global answer if is_completed(): if count < answer: answer = count return if count == 3: return # 현재 b = 세로선부터 마지막 바로 전 세로선까지만 # i = 세..
[코딩인터뷰] 백트래킹 Back tracking 백트래킹 Back tracking 백트래킹 (Back tracking)은 문제 해결 전략 중 하나로, 가능한 모든 경우의 수를 탐색하는 전략인 브루트 포스(Brute force) 전략에서 특정 조건을 만족하지 못하는 경우의 수들을 탐색 범위에서 제외시키며 탐색하는 전략입니다. 브루트 포스 전략은 모든 경우의 수를 전부 탐색하지만 백트래킹 전략은 특정 조건을 만족하지 못하는 경우의 수를 탐색에서 제외하기 때문에 브루트 포스 전략보다 탐색 효율이 좋습니다. 백트래킹 전략은 재귀적으로 조건을 만족하는지 검토하면서 정답을 완성합니다. 정답을 완성하는 과정 중 조건을 만족하지 못하는 경우의 수와 관련된 경우의 수들을 탐색 범위에서 제외시킵니다. 첫 정답이 완성되면 전 상태로 되돌리고 다른 가능한 경우의 수를 탐색..
[코딩인터뷰] 백준 14888번 Python3 는 시간초과 가 발생합니다. itertools.permutations 함수가 시간이 오래 걸리기 때문입니다. PyPy3 로 변경하면 통과됩니다. 저는 개인적으로 알고리즘 효율성에 큰 의미를 두지는 않습니다. 효율성이 중요하지 않다는건 아닌데, 실무를 하다보니 주어진 개발 기간을 코드의 효율을 개선하는데 투자하기 보다는 전체 설계를 개선할 수 있는 코드 또는 가독성이 좋아지는 코드를 짜는데 시간을 투자하는게 생산성이 더 높다고 생각합니다. 기간 내에 정확하게 개발해서 출시한 뒤에 효율이 크게 뒤떨어지는 부분부터 제품을 개선해 나가는 재미도 있으니까요. 당연히 효율 높은 코드를 바로바로 구현할 수 있도록 훈련을 지속적으로 하면 생산성과 효율 모두 달성할 수 있으니, 코딩 테스트로 연습할 때는 ..
[코딩인터뷰] 백준 14889번 import itertools n = int(input()) score_board = [] for _ in range(n): score_board.append(list(map(lambda i:int(i), input().split()))) team = range(n) min_dist = 10**8 for selected in itertools.combinations(team, n//2): start_team = selected link_team = [] for k in range(n): if k not in selected: link_team.append(k) start_team_score = 0 link_team_score = 0 for m in itertools.combinations(start_te..
[코딩인터뷰] 백준 9663번 def solve(n, location, column): c = 0 if column == n: return 1 for row in range(n): if is_possible(n, location, column, row): location.append((column, row)) c += solve(n, location, column + 1) location.pop() return c def is_possible(n, location, column, row): for loc in location: if loc[0] == column: return False if loc[1] == row: return False for k in range(1, min(n - loc[0], n - loc[1])): if c..
[코딩인터뷰] 백준 2661번 def is_possible(l): for d in range(1, len(l) // 2 + 1): for s in range(len(l) - (d*2) + 1): a_start = s a_end = s + d a = l[a_start:a_end] b_start = a_end b_end = a_end + d if b_end > len(l): break b = l[b_start:b_end] if a == b: return False return True n = int(input()) l = [] value = (1, 2, 3) pos = [[True, True, True] for _ in range(n)] while len(l) < n: i = len(l) is_appended = False for v i..
[코딩인터뷰] 트라이 자료 구조 Trie data structure 트라이 자료 구조 Trie data structure 문자열 검색에 특화된 트리 자료 구조 트라이 자료 구조는 기본적으로 트리 형태로 구성되는데, 언어의 문자가 제한되어 있다는 특징을 활용한 자료 구조입니다. 트라이 자료 구조는 아래 그림과 같이, 단어를 문자의 형태와 순서를 기준으로 트리를 구성하는 자료구조입니다. 예를 들어, tea 라는 단어를 트라이 자료 구조에 추가하게 되면 root 노드부터 시작해서 t, e, a 순서로 트리에 추가합니다. 이렇게 여러 단어가 추가된 트라이 자료 구조에서 tea 로 시작하는 단어를 찾는다면, 모든 단어를 하나 하나 첫 문자부터 비교하며 검색할 필요없이 트라이 자료 구조의 tea 노드의 자식 노드만 탐색하면 됩니다. 특히 영어의 알파벳은 한글과 달리 문자가 나열되는..
[React] 조건부 렌더링 패턴 Conditional Rendering Pattern 조건부 렌더링 패턴 Conditional Rendering Pattern 리액트의 조건부 렌더링 문서에서 조건에 따라 랜더링할 컴포넌트를 선택하는 방법을 소개하고 있지만 추가적으로 알아두면 유용한 best practices 패턴이 몇 가지 더 있어서, 하나씩 소개드리도록 하겠습니다. 소개드릴 패턴 목록입니다. if else 패턴 : ? 패턴 && 패턴 switch case 패턴 enum 패턴 HOC 패턴 if else 패턴 리액트 공식 문서에서 소개하는 가장 기본적인 패턴입니다. function Greeting(props) { const isLoggedIn = props.isLoggedIn; if (isLoggedIn) { return ; } else { return ; } } if 문 조건에 따라 Us..