Devlog_by_0giru

처음 이 문제를 봤을 때에는 dfs를 이용해 해결하려고 했으나, 최솟값을 구해주기 위해선 백트래킹 알고리즘을 생각해줘야 했는데 이 부분이 어려워 bfs를 이용해 해결했다. bfs는 큐를 이용해 문제를 해결하는데, 기초적인 이론으로 bfs를 설명하면 보통 그래프를 이용해 설명한다.(bfs알고리즘 포스팅 링크 첨부 예정) 이 문제는 x, y좌표를 이용한 이중 배열(리스트)를 이용하여 해결하는 문제였기 때문에 bfs 알고리즘을 실제로 코드에 녹여내기가 조금 어려웠다. 이런 문제처럼 x, y좌표를 통해 이중 배열(리스트)로 나타내는 모양을 이용하는 문제 유형이 대표적이니 반드시 익숙해져야 겠다고 느꼈다. 백준 예제 2번을 이용해 설명하겠다. 처음에 주어진 그래프가 있고 빈 큐를 선언했다. 처음 시작 부분의 좌표..

N = int(input()) array = list(map(int, input().split())) dp = [1 for i in range(N)] temp_list = list() for i in range(N): for j in range(i): if array[i] > array[j]: temp_list.append(dp[j]+1) temp = max(temp_list) dp[i] = temp temp_list.clear() print(max(dp)) for i in range(N): for j in range(i): if array[i] > array[j] and dp[j] + 1 > dp[i]: dp[i] = dp[j] + 1 print(max(dp)) 두 코드 모두 맞는 코드이고 동일하게 아..

파이썬에서 리스트를 사용할 때에는 얕은 복사(Shallow Copy)와 깊은 복사(Deep Copy)를 반드시 고려하여 사용하여야 한다. 먼저 파이썬 얕은 복사의 대표적인 예를 보자. temp = list() temp.append(1) temp.append(2) temp.append(3) temp_anther = temp print(id(temp)) print(id(temp_anther)) 이 코드의 실행 결과는 아래와 같다. 1859362000832 1859362000832 대입연산자 = 를 이용해 리스트를 복사하면, 복사 된 리스트는 피 복사된 리스트와 같은 메모리 공간을 공유하게 된다. 따라서 temp 리스트의 데이터를 수정하게 되면 temp_another 리스트의 데이터도 동일하게 수정된다. te..

dfs를 통해 배추의 묶음을 판단하는 문제이다. 2667번 단지번호 붙이기와 문제의 접근법이 완전히 동일하게 dfs로 접근하면 어렵지 않게 풀 수 있다. 다른점이 있다면, 이 문제는 여러 테스트 케이스에 대해서 다르게 출력할 수 있게 따로 설정해 주어야 한다는 점이다. # 유기농 배추 import sys sys.setrecursionlimit() def dfs(par_y, par_x): if par_x >= M or par_y >= N or par_x

코딩을 하다 보면 대수 비교, 조건문 그리고 여러가지 이유 등으로 무한대의 값을 갖는 수를 이용해 대소 비교를 해야 한다. 파이썬에서는 float('inf') 키워드를 이용해 무한대 값을 사용할 수 있다. val1 = float('inf') val2 = 99999999999999999999999999999 if val1 > val2: print('val1 is bigger') elif val1 < val2: print('val2 is bigger') elif val1== val2: print('same') 위와 같은 코드를 실행하면 항상 val1 is bigger 이라는 출력을 얻게 된다. '99999999999999999999999999999보다 더 큰 수를 비교하면?' 이라는 의문이 들 수 있지만 필..

파이썬은 리스트(배열)을 처리하기 아주 좋은 언어이다. 프로그래밍을 하다 보면 리스트가 비어있음을 이용해 유용하게 루프나 조건문을 코딩할 수 있었다. temp_list = [] if not temp_list: print("this list is empty") 위 코드를 실행하면 'this list is empty' 가 출력된다. 비어있지 않은 리스트는 True로, 비어있는 리스트는 False를 "반환한다." 라는 말이 정확한 표현인지는 모르겠으나, 위 코딩을 통해 유용하게 조건문 혹은 루프를 구성할 수 있었다.

# 테스트 케이스 2 통과 / 실패 def solution(tickets): nation_num = len(tickets) graph = [] graph_new = [] result = [] for inf in tickets: graph.append([inf[0]]) for inf in tickets: for i in range(nation_num): if inf[0] == graph[i][0]: graph[i].append(inf[1]) for inf in graph: if inf not in graph_new: graph_new.append(inf) for inf_new in graph_new: temp1 = inf_new[0] inf_new.sort() temp2 = inf_new.index(tem..

그래프를 순회하는 대표적인 문제라고 생각한다. 격자(테이블) 형태의 그래프를 위 아래로 탐색해가며 같은 군집(?)을 결정하는 문제이다. 이 문제 또한 나동빈 저자의 '이것이 코딩 테스트다' 책의 예제 코드를 이용하였다. dfs 알고리즘을 통해 이어진 노드를 탐색하고 그 개수만큼을 리스트에 담아 출력하는 문제이다. 여담이지만, 효율적인 코딩테스트 공부를 위해 이렇게 책의 코드를 적극적으로 활용해 시간을 절약하는 좋은 것인지...아니면 나름대로의 고민을 하며 인고의 시간을 보내는 것이 좋은 것인지는 잘 모르겠다... # 단지번호 붙이기 N = int(input()) graph = [] list_num = [] count = 0 for _ in range(N): graph.append(list(map(int,..