전체 글

https://www.acmicpc.net/problem/13460 어떤 상태에서 나아갈 수 있는 상태가 여럿이 있고, 이를 모두 탐색을 해야하는 경우는(* 반드시 그래프가 아니더라도)너비 우선 탐색으로 풀 수 있다.(* 아니면 A* 알고리즘도 생각해볼 수 있다.) 시간복잡도와 공간복잡도 너비 우산 탐색을 사용할 때는 시간복잡도와 공간복잡도가 중요하다. 최대 10번의 탐색이 이루어져야 하고,현재 상태에 대해서 최대 두 방향의 가능성이 존재하기 때문에(* 이전에 선택했던 방향과 그 반대 방향은 제외한다. 예를 들어 왼쪽으로 기울였었는데 다시 왼쪽으로 기울이거나 오른쪽으로 기울이는건 의미없는 반복이다.)최대 4(* 처음은 네 방향 모두 가능하기 때문에) * 2 * 2 * 2 * ... * 2 ≒ 2^11 =..

https://www.acmicpc.net/problem/17143그냥 구현문제이다.근데 시간복잡도 이슈가 있는... 처음 생각 그냥 행과 열의 크기가 최대 100이므로 시간복잡도를 생각하지 않고 구현을 해봤다.상어들이 낚시꾼에 의해 잡히기도 하고 서로 잡아 먹히기도 하니, 삭제가 잦을 거라고 판단 하고,LinkedList로 상어들을 저장해주었다. 그 후 상어들이 이동하고,LinkedList안에 있는 상어들 중 같은 위치에 있는 상어들을 찾아서(* 물론 선형으로)잡아 먹는 것 까지 구현을 했다. 하지만, LinkedList의 최대길이는 100 x 100 으로 10,000 이고, List안에 있는 상어들끼리의 관계를 파악하기 위해두 번 for문을 돌리면 10,000 x 10,000 으로 반드시 시간초과가 ..

https://www.acmicpc.net/problem/140032024.07.03 - [자바[JAVA]/자바[JAVA] 백준] - BOJ(백준 온라인 저지) 2568번 with 자바[JAVA] BOJ(백준 온라인 저지) 2568번 with 자바[JAVA]https://www.acmicpc.net/problem/2568전깃줄이 교차? 전깃줄이 교차한다는 것은 무엇일까?두 개의 전깃줄이 교차하려면 A의 위치와 B의 위치가 꼬여있어야한다. 예를 들어 임의의 두 전깃줄 a, b가 있다고hw-hk.tistory.com에서 사용했던 LIS 알고리즘을 이용하면 쉽게 풀 수 있다. 코드import java.io.BufferedReader;import java.io.IOException;import java.io.I..

https://www.acmicpc.net/problem/2568전깃줄이 교차? 전깃줄이 교차한다는 것은 무엇일까?두 개의 전깃줄이 교차하려면 A의 위치와 B의 위치가 꼬여있어야한다. 예를 들어 임의의 두 전깃줄 a, b가 있다고 할때, a의 전봇대 A에서의 위치를 a1, B에서의 위치를 a2 라고 하고,마찬가지로 b1, b2 라고 했을 때, a1 > b1 이면 a2 a1 b2 일때,전깃줄이 꼬인다고 할 수 있다. 그렇다면 한 전봇대에 대해 오름차순으로 정렬한 다음,반대편 전봇대에 연결되어있는 위치가 "꼬여있는"지를 확인하면 된다. 예를 들어,주어진 예제 입력의 경우에서,전봇대 B의 위치에 대해서 오름차순으로 정렬을 한 후 전봇대 A의 위치를 살펴보자. index01234567B124678910A426..

https://www.acmicpc.net/problem/28872024.06.09 - [자료구조 및 알고리즘] - 자료구조 및 알고리즘 #14 - Union-Find (Disjoint Set) and an Application 자료구조 및 알고리즘 #14 - Union-Find (Disjoint Set) and an Application1. an Application Union-Find 를 알아보기 전에 이것을 언제 사용하는지를 먼저 파악하는 것이 좋아보입니다. MST(* Minimum Spanning Tree), 최소신장트리는 Spanning Tree 중에서 사용된 간선들의 가중치 합이 최hw-hk.tistory.com문제를 처음 보자마자 최소 신장 트리 문제임을 알았다.하지만 기존의 최소 신장 트리..

https://www.acmicpc.net/problem/16566문제는 단순해 보였다.처음 문제를 읽자 마자 생각한 것은 다음과 같다.리스트에 민수가 뽑은 숫자들을 담는다.리스트를 정렬하고 철수가 보여주는 카드보다 큰 수의 숫자를 뽑는다.뽑은 숫자는 삭제하고 2번으로 돌아간다. 왜 리스트를 정렬하는가? 리스트를 정렬하지 않으면 철수가 보여주는 카드보다 큰 수들 중 가장 작은 수를 찾기 위해서는 선형탐색밖에 답이 없기 때문이다. 선형탐색의 시간 복잡도는 O(N) 이므로, 최대 4,000,000 x 10,000 = 40,000,000,000 의 연산이 필요하다. 대충 100,000,000 에 1초 이므로, 이는 반드시 시간초과가 발생한다. 하지만 정렬을 한다면 다르다. 정렬이 되어있는 자료구조에 대해서는 ..

1. Path Path는 한 정점에서 다른 정점가지 연속되는 간선들을 통해서 도달할 수 있는 방법입니다. 예를 들어 아래와 같은 그래프가 있을 때:1번 정점에서 3번 정점까지 도달할 수 있는 Path 는 다음과 같이 나타낼 수 있습니다:1-e1 → 2-e1 →  1-e3 →  3-e4 →  2-e6 →  2-e5 →  2-e4 →  3 이때 간선의 이름과 같이 정점의 이름도 같이 적어주는데, 그냥 간선 이름들만 적어줘도 Path 를 설명할 수 있지 않을까?그렇지 않습니다. 만약 e1 → e1 → e3 → e4 → e6 → e5 → e4 라고만 적어놨다면,처음 시작하는 노드는 어디였고, 어느 정점에서 어느 정점으로 향하는 간선인지 명확하지 않습니다. 다시한번 Path 에 대해 정의하자면 다음과 같습니다: ..