Posts

2023년 8월 12일 알고리즘 문제풀이 문제 1 백준 18352 문제 링크 1차 시도 나의 생각 도시까지의 최단거리만 생각해야 하므로, bfs를 통해 도착한 도시에 얼마나 걸렸는지를 표시하고, 이를 방문표시로 이용하면 되겠다는 생각을 했다. 출발한 도시 와 도착지가 같을때는 0으로 표시하게 되는데, 이것 때문에 아직 방문처리하지 않은 것으로 취급되어 여러가지로 헷갈렸다. 따라서 제자리 거리를 1로 표시하여 모든 도시의 거리를 구하고 모두 1 만큼 감소시켜주었다. 결과 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 import sys from collections import deque n, m, k, x = map(int, sys.stdin.readline().split()) graph = [[]for _ in range(n+1)] for _ in range(m): a, b = map(int, sys.stdin.readline().split()) graph[a].append(b) ans = [] visited = [0 for _ in range(n+1)] def bfs(s): visited[s] = 1 arr = deque() arr.append(s) while arr: now = arr.popleft() for next in graph[now]: if not visited[next]: arr.append(next) visited[next] = visited[now]+1 bfs(x) ans = [] if k == 0: print(x) else: for i in range(1, n+1): visited[i] -= 1 if i == x: continue if visited[i] == k: print(i) ans.append(i) if not ans: print(-1) 문제 2 백준 2178 문제 링크 ...

책너두 5기 12일차 로버트 C. 마틴의 클린코드 p.103 ~ p.110 내용 정리 5. 형식 맞추기 종속 함수 한 함수가 다른 함수를 호출한다면 두 함수는 세로로 가까이 배치한다. 가능하면 호출하는 함수를 호출되는 함수보다 먼저 배치한다. 상수를 알아야 마땅한 함수에서 실제로 사용하는 함수로 상수를 넘겨주는 방법은 좋다. 개념적 유사성 개념적인 친화도가 높은 함수는 가까이 배치한다. 한 함수가 다른 함수를 호출해 생기는 직접적인 종속성, 변수와 그 변수를 사용하는 함수, 비슷한 동작을 수행하는 일군의 함수 등. ...

2023년 8월 11일 알고리즘 문제풀이 문제 1 백준 1010 문제 링크 1차 시도 나의 생각 결국 서쪽에 있는 사이트는 모두 사용 되야 하므로 첫번째 사이트부터 고를 수 있는 상황에 대해 dfs를 적용하고 모든 다리가 결정될 때마다 카운트하는 방법을 생각했다. 그런데 가만 생각해보니 다리끼리 교차될 수 없으므로 동쪽의 사이트 중 서쪽의 사이트의 갯수만큼 선택하면 다리가 연결되는 경우의 수는 한개 뿐이다. 따라서 조합(Combination)을 사용하면 되겠다고 판단했다. 모듈을 까먹어서 그냥 직접 구현했다. 결과 정답 ...

책너두 5기 11일차 로버트 C. 마틴의 클린코드 p.95 ~ p.102 내용 정리 5. 형식 맞추기 처음 코드를 봤을 때 깔끔하고 일관적이며 꼼꼼한 코드로 보여야 한다. 그러기 위해선 규칙을 따라야 한다. 형식을 맞추는 목적 분명히 코드 형식은 중요하다. 오늘 구현한 기능이 다음 버전엣 ㅓ바뀔 확률은 아주 높다. 따라서 오늘 작성한 코드의 가독성은 미래에도 영향을 끼친다. 적절한 행 길이를 유지하라 파일의 세로 길이가 조금만 차이나도 실제 파일의 크기는 크게 달라진다. 비교적 적은 줄의 파일로도 커다란 시스템을 구축할 수 있다. 반드시는 아니지만 바람직한 규칙이다. ...

책너두 5기 10일차 로버트 C. 마틴의 클린코드 p.84 ~ p.94 내용 정리 함수나 변수로 표현할 수 있다면 주석을 달지 마라 명명법을 올바르게 사용하여 주석의 필요성을 없애자. 위치를 표시하는 주석 // Actions //////////// 같은 배너 아래에 모아두는 것은 필요할 때도 있지만 극히 드물게 사용해야 한다. 닫는 괄호에 다는 주석 차라리 함수를 줄이는데 시간을 쓰자 저자를 표시하는 주석 준수가 작성함은 소스 코드 관리 시스템이 있는 한 무의미한 주석이다. 주석으로 처리한 코드 내가 주석으로 처리하면, 다른 사람은 지우기를 주저 한다. 이전의 기록은 소스 코드 관리 시스템이 한다. 지금 필요없으면 지우자. 기록은 존재한다. ...

2023년 8월 10일 알고리즘 문제풀이 문제 1 백준 14888 문제 링크 1차 시도 나의 생각 각 경우에 알맞은 연산을 처리한 후 재귀를 탔다. 정의한 dfs 재귀 함수는 몇번의 재귀를 탔는지, 각 연산이 몇번 남아있는지를 parameter로 받도록 정의하였다. 나눗셈은 음수일때는 양수로 변환한 후 결과에 음수를 다시 붙이도록 하였다. 결과 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 import sys n = int(sys.stdin.readline()) nums = list(map(int, sys.stdin.readline().split())) plus, minus, multiple, division = map(int, sys.stdin.readline().split()) arr = [] def dfs(tmp, cnt, a, b, c, d): if cnt == n: arr.append(tmp) return if a: tmp += nums[cnt] a -= 1 cnt += 1 dfs(tmp, cnt, a, b, c, d) cnt -= 1 a += 1 tmp -= nums[cnt] if b: tmp -= nums[cnt] b -= 1 cnt += 1 dfs(tmp, cnt, a, b, c, d) cnt -= 1 b += 1 tmp += nums[cnt] if c: tmp *= nums[cnt] c -= 1 cnt += 1 dfs(tmp, cnt, a, b, c, d) cnt -= 1 c += 1 tmp = tmp // nums[cnt] if d: if tmp >= 0: tmp = tmp//nums[cnt] else: r_tmp = abs(tmp)//nums[cnt] tmp = -1 * r_tmp d -= 1 cnt += 1 dfs(tmp, cnt, a, b, c, d) cnt -= 1 d += 1 if tmp >= 0: tmp = abs(tmp)*nums[cnt] else: r_tmp = abs(tmp)*nums[cnt] tmp = -1 * r_tmp dfs(nums[0], 1, plus, minus, multiple, division) print(max(arr)) print(min(arr)) 문제 2 백준 2573 문제 링크 ...

책너두 5기 9일차 로버트 C. 마틴의 클린코드 p.74 ~ p.83 내용정리 나쁜 주석 대부분은 나쁜 주석이다. 주절거리는 주석 특별한 목적이나 이유가 없는 주석. 달아야 한다면 제대로 명확하게 달자 같은 이야기를 중복하는 주석 코드 내용을 그대로 중복하는, 쓸데없는 주석 오해할 여지가 있는 주석 값이 반환되는 곳, 조건 등이 불확실하게 전달되선 안된다. 의무적으로 다는 주석 모든 코드에 주석을 달아야 한다는 등의 규칙은 불필요하다. 이력을 기록하는 주석 이젠 깃과 같은 관리 시스템이 존재하니 필요 없어졌다. ...

2023년 8월 9일 알고리즘 문제풀이 문제 1 백준 11725 문제 링크 1차 시도 나의 생각 연결된 두 점 중 누구를 부모로 할 것인가에 대해 많이 고민했다. 확실한 것은, 1번과 연결된 노드들의 부모는 모두 1번 노드일 것이라는 것이다. 그래서 모두 1번노드 쪽으로 향하니 번호가 작은 노드가 부모인 것으로 설정해야하나 고민했다. 물론 나도 지금 생각해보면 뭔 말도 안되는 소리인지 모르겠다. 결국 어떤 방법으로 풀어야 할지 감을 못잡았다 결과 오답 코드 X 2차 시도 나의 생각 지금 내가 공부하고 있는 단원이 DFS인 것을 떠올리니 쉽게 해결됐다. 실제 코딩 테스트에선 단원을 모로는 채로 풀어야 하기 때문에 문제만 보고 알아차려야 하는데.. 걱정이다 ...

책너두 5기 8일차 로버트 C. 마틴의 클린코드 p.67 ~ p.73 내용정리 4. 주석 나쁜 코드에 주석을 달지 마라. 새로 짜라. 브라이언 W. 커니핸, P. J. 플라우거 주석은 실패를 만회하기 위해 사용된다. 주석 없이는 자신을 표현할 방법을 찾지 못해 할 수 없이 사용하기 때문이다. 주석은 거짓말을 한다. 코드는 유지 보수 되지만 주석은 그렇지 않기 때문이다. 코드가 수정되고 변화하고 진화하지만 주석은 그대로면서 거짓이 되고 잘못된 정보를 퍼뜨린다. 엄격하게 관리된 주석이 필요할 수도 있지만, 결국 최선은 주석이 필요없는 코드이다. ...

2023년 8월 8일 알고리즘 문제풀이 곧 있을 크래프톤 코딩테스트를 위한 연습으로 오늘은 Codility에서 문제를 풀었다. 혹시 백준에서만 하시는 분들은 해보시길 권한다. 나는 리트코드를 한 경험이 있는데 비슷한 느낌이다. 링크 각 주제별로 문제를 푸는 Lesson의 링크 문제 1 문제 A binary gap within a positive integer N is any maximal sequence of consecutive zeros that is surrounded by ones at both ends in the binary representation of N. For example, number 9 has binary representation 1001 and contains a binary gap of length 2. The number 529 has binary representation 1000010001 and contains two binary gaps: one of length 4 and one of length 3. The number 20 has binary representation 10100 and contains one binary gap of length 1. The number 15 has binary representation 1111 and has no binary gaps. The number 32 has binary representation 100000 and has no binary gaps. ...