백준 풀이 11049 행렬 곱셈 순서 정말 어렵게 다가왔다. DP문제이다 보니 dp테이블을 만들어서 써먹으면 되겠다! 라는 틀 안에서 벗어날 수가 없었다. 풀이는 해당 블로그에서 참조했다. 마지막 Matrixstart * Matrixpivot * Matrixstart + term 부분이 이해가 어려웠는데 설명하자면 (A, B, C), (D, E) 이렇게 묶어서 연산을 수행한다고 하면 Matrixstart은 A의 행, Matrixpivot은 C의 열, Matrixstart + term은 E의 열 이된다. 즉 마지막 두 묶음의 행렬곱을 합칠때 필요한 연산임을 나타낸다. 12865 평범한 배낭 전형적인 배낭(Knapsack) 문제이다. 이 문제를 풀다가 두번째 for문에서 왜

위상 정렬 위상 정렬 문제인 백준 그래프 수정 문제을 풀면서 했던 고민을 작성합니다. 해당 문제에서의 핵심은 V1 -> V2 간선이 있을경우 V1 > V2 이다 1 ~ N 각각의 노드가 바뀐 숫자를 순차적으로 출력할 때 결과값이 사전식 순서에서 가장 앞에 와야한다. 위상정렬을 수행하고 같은 위상에서의 가장 왼쪽 노드의 번호를 부여할 수 있는 숫자 중 가장 낮은 숫자로 부여했다. 결과는 틀렸다. 반례로써 의 결과는 1342가 나와야 하지만 나의 풀이로는 1423이 나왔다. 이유를 생각해봤는데 최종적으로 내린 결론은 탐욕 알고리즘과 같이 매번 최선의 경우를 선택해도 최선의 결과가 나올 수 없다 였다. 나의 풀이는 위상정렬을 수행하고, 각 위상에서의 최선의 선택을 반복함으로서 결과를 도출해냈지만 그렇지 않은 경우가 발생했기 때문이다. 특히 아래 사진의 중앙부분에 파란선으로 그

백준 풀이 1916 최소비용 구하기 접근 최단거리 최소비용 탐색 알고리즘인 다익스트라(Dijkstra) 활용 dfs를 통해 완전탐색을 수행하고 그 과정에서 소요된 cost를 계산하는 방식으로 접근했다. 풀이 후기 다익스트라 알고리즘은 접한 기억이 꽤 많았는데 제대로 구현하지도 못하고 설명하지도 못했다. 알았다! 라고 확신하고 넘어가는 행위가 얼마나 무서운지 알게되었다. 2294 동전2 접근 처음 접근하는 방법은 백트래킹이였다. 하지만 최악의 경우 완전탐색을 수행하므로 최악의 경우 시간이 너무 오래걸릴 것이라 생각했다. 시간 복잡도를 계산하기가 어려워서 추측하기로는 O(nlogn)정도로 생각하고 있다. (모든 코인의 종류 N을 각각 logN 만큼 결정트리를 따라 내려가야 하므로) 풀이 defaultdictionary 기본값을 10001으로 지정해서 굳이 필요한 크기만큼의 list를 선언하지 않아도

백준 풀이 이분 그래프 정점들이 두 그룹으로 나뉜다는 개념을 정확히 이해하지 못했다. '두 그룹으로 나뉜다' 라는 부분에서 '두 정점이 맞닿을 때 두 정점은 항상 서로다른 그룹이다' 라고 이해하는 편이 더 낫겠다고 생각했다. 내가 현재 위치한 노드에서 다음 노드로 탐색하기 전에 서로 다른 그룹인지 확인하는 과정을 거쳤다. color를 활용해서 -1, 1 값을 두 그룹으로 설정했고, 0이면 아직 방문하지 않았다고 설정하고 진행했다.

백준 풀이 5639 이진 검색 트리 접근 전위 순회 데이터를 기반으로 이진 탐색트리를 생성한 뒤 우위 순회로 출력한다. -> 실패함 전위 순회 데이터를 즉시 후위 순회로 변경하여 출력한다. -> 굉장히 복잡함. 풀이 이진 검색 트리를 구성 한 뒤 postorder로 출력하는 코드 이 코드는 시간초과 발생 전위 순회를 바로 후위순회로 바꿔 출력하는 풀이 후기 첫 번째 풀이는 보편적으로 시간초과가 발생한다. 같은 기수 동료 중 한명이 이 방법으로 성공했지만 나는 실패했다. dictionary를 적극적으로 활용했다고 들어서 활용해봤는데 왜인지 25%에서 시간초과가 발생한다. 한쪽으로 쏠리는 경우 트리를 구성하고, 탐색하는 과정이 극단적으로 늘어날 수 있는데 이 경우 트리를 구성후 다시 탐색하며 postorder로 출력하면 시간초과가 발생하도록 문제를 설계했다는 판단하에 두번째 풀이가 정답이라 생각했다.

백준 문제 풀이 2110 공유기 설치 이진 탐색을 공부하면서 ~T / F~에 너무 집중한 나머지 범위 지정의 중요성을 놓쳤다. 이진 탐색중 사용되는 lo, hi값은 정답이 될 수 있는 값이 존재하는 범위에 해당한다. 이 문제를 풀면서 이진 탐색의 결과를 '공유기를 설치할 위치'로 지정했다. 하지만 이렇게 해서는 문제가 풀릴리 없었다. 다른 사람의 풀이를 보고 비로소 이 문제의 답인 가장 가까운 두 공유기 사이의 거리를 mid로 설정했다. 범위는 1 ~ 가장 오른쪽의 집 위치 - 가장 왼쪽의 집 위치로 지정했다.

기본 언어 변경하기 백준 페이지에서 설정 -> 언어 탭 원하는 언어를 추가하거나 삭제할 수 있습니다. 우리는 주로 python3을 사용하니까 최상단으로 끌어올립니다. 이제 제출 페이지에서 코드를 입력하기 전에 언어설정을 바꾸지 않아도 됩니다. try it online https://tio.run/#python3 온라인에서 코드를 미리

백준 tip (python) 기본 언어 변경하기 백준 페이지에서 설정 -> 언어 탭으로 넘어간다 원하는 언어를 추가하거나 삭제하고, 최상단으로 올린다 굿 map(int, input().split(' ')) split()과 split(' ')의 차이 과 split(' ')의 차이) open(0) open(0)에 관해서 배열 초기화 방법 ㅁㄴㅇㄹ

백준 알고리즘 문제를 풀이하면서 새로운 부분을 봤다. 이분 탐색을 헷갈리지 않게 구현하기에서 예시문제로 나무 자르기 를 제시한다. solution 코드중에 이렇게 분리하여 작성하는건 봤지만 클래스 참조로 더 간결하게 표현하는걸 봤다. 레퍼런스를 찾아보니 cin 클래스는 ios를 상속한 istream을 상속하며, tie 함수는 연결되어있던 stream 포인터를 반환한다. 즉 cin.tie(0) 호출로 반환된 'ios'객체를 참조하여 syncwithstdio(0)를 호출하는 것. 자세하게 보기위해 간단하게 코드를 작성해보았다. 알아두기 tie() 는 tie되어있던 ostream을 반환 tie 함수에 ostream을 넣으면 해당 ostream과 tie를 수행함 ostream은 ios_base를 상속한 ios를 상속 결과: ![](https://images.velog.io/images/c4fiber/