공부해볼라는 스토리

9.1 백트래킹!!!!! 퇴각 검색, 이라고도 불린다. 한정 조건을 가진 문제를 풀려는 전략이다. 종종 사용하는 브루트 포스 방법은 모든 조건을 탐색해야하기때문에 무조건 정답에 도달할 수 있지만 시간과 메모리가 많이 든다,, 하지만 백트래킹은 한정 조건이 있기때문에 그 제한 내의 모든 경우의 수를 시도하기 때문에 상당한 경우의 수가 배제되어 시간과 메모리를 단축할 수 있다! 9.2 백트래킹은 어떻게 구현하는데? 보통 BFS / DFS 와 함께 구현된다. 모든 경우의 수에서 한정 조건을 만족하는 경우를 탐색하는 것이기 때문에 완전탐색기법인 bfs / dfs가 모두 구현이 가능하다. 하지만 조건을 만족 못하면 돌아와야 하기 때문에 dfs가 구현이 더 편할 수 밖에 없다. 결론! 여기서 제일 많이 언급된 단어..

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net [1] 풀이 및 생각 이 문제 진짜 단순한데 풀면서 너무너무너무너무 암걸릴뻔했다. 왜냐? 유방향 그래프인데 무방향인줄 앎,, 그래서 답이 계속 틀려서 너무 ,,,, 지쳤다,,,,, 문제 자체는 다익스트라만 구현하면 돼서 단순하고 최단거리 입문용인데 진짜 하,, 저거때매 넘 힘들었다. 난 내가 뭘 틀렸는지 진짜 진지하게 겁나 고민했다. 분명 알고리즘 구현자체는 똑같..

프로그래머스 Lv.2 - 타겟넘버 https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [1] 풀이 및 생각 1-1) 처음 접할때 생각 문제가 분명 dfs/bfs인데 사실 어떤 방식으로 bfs/dfs를 적용해야 할지 파악을 못함. 트리로 생각을 해보자니 그럼 또 결국 더하기/빼기를 정해야하고... 만약 리스트 안에 [원래 값들, -붙인 값들] 이렇게 해서 뭐 그래프 내에서 탐색을 하자니 그것도 이상한거 같고ㅠ 생각하기가 너무 어려웠다. 1-2) 스터..

지름길 - 🥈1 https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net [1] 풀이 및 생각 이거도 처음에는 어떻게 생각해될지 몰랐는데, 스터디에서 아이디어를 얻었다. 딕셔너리를 구현하는데, {현재위치: 1~현재까지 걸리는 거리} 이런식으로 구현을 한다. 그리고 이제 지름길을 만나는 순간 시작 지점과 끝지점이 있으면 끝지점의 딕셔너리에서 현재 거리보다 짧으면 업데이트를 한다. 그러면 지름길 시작지점 ~ 지름길 끝지점 - 1 까지는 변화가 없..

https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 도시 분할 계획 - 🥇4 [1] 풀이 및 생각 처음엔 진짜 그냥 자료구조 없이!! 풀어보고 싶어서 초초 무식한 방법을 썼다. 그래서 생각해보면 가능은 한 코드인데 저어얼대 시간내 못풀코드 ㅋㅋ 하나씩 받는데, 큰 weight의 간선부터 처리하는데 하나씩 지우면서 마을이 2개이상으로 갈라지는지 확인하고, 최초로 순환이 없어지는 순간까지 찾아가는 방식으로 푼 것같..

그리디,, 욕망이라는 뜻이죠? 욕망하면 맨날 저친구만 생각나네요,, ㅋㅋㅋㅋㅋㅋㅋ 오랜만 6.1 탐욕 알고리즘, 그리디 알고리즘!! 얼마나 탐욕적이길래 ㄷㄷ 탐욕적인게 뭘까요, 말그대로 욕심많은거죠? 이 알고리즘은 항상 모든 순간에 최적의 경우만 선택합니다. 그래서 최적의 해로 근사적으로 접근하려는 방식이다. 하지만 항상 좋은 선택만 하는게 최적의 해일까? 그리디 알고리즘의 방식이라면 내가 지금 당장 만원을 받기 vs 10분 후에 100만웜 받기에서 현재의 경우에는 만원 vs 0원 이기 때문에 무조건 전자를 고릅니다. 이후의 상황까지 생각하면 무조건 후자를 골라야 되는데 말이지.. 그래서 그리디 알고리즘을 적용한다면 그리디 알고리즘의 최적의 해를 보장해주는 상황이라는걸 파악하고 사용해야 합니다. 6.2 ..

4. Graph (그래프) 그래프는 연결되어있는 원소 간의 관계를 표현하는 자료구조다! - 연결할 객체인 정점(Vertex)와 객체를 연결하는 간선(Edge)의 집합으로 구성 - 그래프를 나타내는 G = (V, E)로 정의 4. 1 그래프의 종류에는 무엇이 있을까? (1) 무방향 그래프 (Undirected Graph): 두 정점을 연걸하는 간선에 방향이 없는 그래프 - 무방향 그래프는 방향이 없어서 정점 $ V_I $와 $V_j$를 연결하는 간선을 ($ V_I $, $V_j$)으로 표현하는데, 둘이 같은 간선임 - G = {존재하는 모든 노드}, E(G) = {(정점1, 정점2), ... 등 존재하는 모든 간선} (2) 방향 그래프 (Directed Graph): 간선에 방향이 있는 그래프 - 방향이 ..

https://www.acmicpc.net/problem/2606 문제 - 실3 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 ..

문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. 예제 입력 1 복사 7 1 6 6 3 3 5 4 1 2 4 4 7 예제 출력 1 복사 4 6 1 3 1 4 예제 입력 2 복사 12 1 2 1 3 2 4 3 5 3 6 4 7 4 8 5 9 5 10 6 11 6 12 예제 출력 2 복사 1 1 2 3 3 4 4 5 5 6 6 일단,, 내가 트리로 문제를 제대로 풀어보려는게 처음이라 구현이랑 접..

절댓값 힙 - 실버1 문제 절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다. 배열에 정수 x (x ≠ 0)를 넣는다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다. 출력 입력..