heeStory

자바에서 Integer는 자료형 중에서 참조형으로 객체의 주소를 저장한다. 고로, 같은 값이 이라도 주소값이 다르니 다른 객체라고 기대할 수 있다.따라서, 참조형 객체에서 해당 값이 같은지 확인하기 위해서는 == 이 아닌 Eqauls로 확인해야한다.   문제그렇다면 아래 값은 어떤 결과 나올까?Integer a = 1;Integer b = 1;System.out.println(a == b);다른 값 주소값으로 메모리에 저장되어 있을 테니 다른 객체라고 생각할 수 있을 것이다. 정답은 True 이다.    Integer Caching이 부분을 간과해서 알고리즘 문제에서 오랜시간을 낭비했는데,    In Java 5, a new feature was introduced to save the memory an..

https://www.acmicpc.net/problem/15666   수열들을 비교했을 때, 앞에서 부터 비교했을 때 오름차순이 되어야한다.   접근순차적으로 모든 원소를 방문한다고 생각하고 필요없는 부분을 제거하는 백트래킹 가지치기를 하면 된다.순회 원소를 선택할 때, 중복이 없도록 고려하자. 가지 치기만약 1을 선택했다면 다음 원소는 다음 자리 수에 원소부터 골라야한다.  다른 가지에서 중복된 값을 선택하지 않아야 한다. (같은 줄 == depth에서) 전체를 순회하는 재귀 탐색 코드에서 위에 해당하는 가지를 제외시키면 정답이 된다.  코드단순히 전체를 순회한다면 아래와 같은 코드if(depth == M) { for(int n : nums) sb.append(n).append(" "); ..

문제링크:  https://www.acmicpc.net/problem/1967 가중치가 제일 큰 값을 가진 지름을 찾는 문제 문제에서 주어진 조건노드 번호 순서대로 주어짐첫 번째 정수는 간선이 연결하는 두 노드 중 부모 노드의 번호 접근원은 두 점(말단 노드) 사이 길이이다그 중 제일 긴 노드 두 점을 찾으면 된다DFS를  사용하면 시작 노드에서부터 가장 큰 말단 노드를 찾을 수 있다. 현재 어떤 노드가 제일 큰 노드인지 알 수 없으니 최상위 부모 노드에서 시작하여  가장 큰 말단 노드부터 찾는다.  1번. DFS로 말단 노드 한 점을 찾는다.최상단 노드는 제일 사이즈가 큰 말단 노드가 아니다. 따라서, 최상위 노드에서 경로가 가장 긴(지름이 제일 긴) 노드를 찾자.1번 노드는 그저 처음 탐색을 위한 노..

카잉 달력 성공다국어 시간 제한메모리 제한제출정답맞힌 사람정답 비율1 초256 MB71276185881393526.726%문제최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 로 표현하고, 두 번째 해를 로 표현하였다. 의 다음 해를 표현한 것을 이라고 하자. 만일 x 은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다.예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해..

https://www.notion.so/2-say/369d82e5d2ad4bc295606646161a35cf?pvs=4 최소 공통 조상 | Notion 트리 그래프에서 임의의 두 노드를 선택했을 때 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 때 처음 공통으로 만나게 되는 부모 노드를 ‘최소 공통 조상’이라고 한 2-say.notion.site

원래 문제 코드를 블로그에 올리지 않는데 한글 에디션이라서 기록. https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.List; import java.util.Queue; import java.util.Strin..

이전 다익스트라, 벨만 포드를 공부할 때, 거리 배열을 초기화 할 때, Integer.MAX_VALUE 로 초기화했었다. 그런데, 플로이드 워샬에서 초기화하면 이렇게 터진다! 그 이유는, 다익스트라, 벨만포드에서는 처음 시작 노드 값을 0으로 초기화했기 때문에 연쇄적으로 작은 값이 들어갈 수 있었지만, 플로이드 워샬은 그런 것 없이, 모든 노드에 대해 업데이트를 진행하기 때문에, 맨 처음 Integer.MAX_VALUE + Integer.MAX_VALUE 이런 연산을 하게 되는 것이다. for (int k = 0; k < n; k++) { for (int i = 0; i < n; i++) { if (i == k) continue; for (int j = 0; j < n; j++) { if (j == i ..

다익스트라 알고리즘은 다익스트라(Dikstra) 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다. 더보기 다익스트라가 뭐지? https://www.notion.so/2-say/0f0108e63c54483991ef2f4070cf448a?pvs=4 다익스트라 알고리즘이 뭔지 모르겠다면! 아래 링크를 참고하자! 다익스트라 알고리즘에서 방문 검사 없이 작동된다. (참고로 자바를 기준으로 합니다.) if(next.cost + dis[curr.n] < dis[next.n]){ dis[next.n] = next.cost + dis[curr.n]; que.add(new Node(next.n, dis[next.n])); } 위 코드를 통해서 아래와 같은 최적의 경로로 업데이트해주는 과정은 모두 알고 있을 것이다! ..

BFS & DFS 문제를 풀다보면, 메모리 초과가 발생할 때가 있다. 대부분 메모리 초과의 이유는 Stack에 담기는 요소가 계속해서 중복값을 넣고 제대로 필터링을 하지 않아서 발생한 문제이다. Visited 의 위치가 중요하다. 다음 코드를 보자, visited 선언에 따라서 결과가 다르게 반영된다. 자세하게 보자, 첫번째의 경우 만약 , Queue에 Node 1 , 2 , 3, 4 가 들어있는 상황에서 Node 1이 꺼내져서 bfs를 한다고 해보자, 그리고, Node 1 에서 갈 수 있는 Node는 Node 2 , Node 3이라고 하자. Node1 이 bfs를 하면서 Node 2가 당연히 아직 큐에 있으니, Visited[Node2] 는 false 이므로 또 넣게 되는 불상사가 생긴다. 큐에 있는 ..