본문 바로가기

분류 전체보기69

자료구조 여름방학 1주차 트리 그래프의 특수한 형태로 노드와 엣지로 연결된다. 순환 구조가 없고 1개의 루트노드가 존재한다.  트리에서 임의의 두 노드를 이어주는 경로는 유일하다. 노드: 데이터의 인덱스와 값을 표현엣지:노드사이의 연결루트: 최상위 노드리프노드:최하위에 존재하는 노드자식노드: 두 노드 사이에서 하위노드에 해당하는 노드 tree 문제:1) 그래프 풀이   dfs, bfs 문제2) tree만을 위한 문제   이진트리, 세그먼트 트리,lca (최소 공통 조상)      1차원 배열로 트리를 표현      (자식으로 이동할 때는 index*2 or index*2+1 부모로 이동할 때는 index/2...) [백준 11725] 인접리스트 자료구조 사용일반적으로 dfs, bfs사용dfs를 사용해 쉽게 해결 가능 깊이우선 탐.. 2024. 7. 7.
java여름방학 1주차 섹션 7-1 scanner system.out 을 통해 출력하였듯이 system.in을 통해서 입력을 받을 수 있음.하지만 매우 복잡하고 어렵기 때문에 자바에서 제공하는 scanner를 사용한다.  자바 라이브러리에서 제공하는 스캐너를 사용한다.Scanner scanner=new Scanner(System.in);  Snanner 스캐너 이름=new Scanner(System.in);String str=scanner.nextLine();nextLine 에서 L이 대문자임에 유의 sout에서  System.out.print("문자열을 입력");print와 println의 차이점은 줄바꿈 문자의 삽입 여부임.    실수와 정수의 입력 예제)만약 자료형을 다르게 입려받는다면 오류가 발생한다. 사용자로부터 입력.. 2024. 7. 6.
1004 어린 왕자 딱 봤을 때는 어려워 보였는데 조금 생각해보니까 풀 수 있었다. 시작 좌표와 끝 좌표가 속한 원의 개수를 세주었다.만약 한 원에 시작 좌표와 끝 좌표가 둘 다 속해 있다면 그 원은 세지 않음. 이를 위해 집합을 사용해 주었다.또한 집합에 행성의 x,y,r 좌표를 묶어서 저장해주려고 튜플을 이용주었다.pair로는 두개까지만 묶인다더라.. 좌표가 원 내부에 있는지 판단해야하는데 처음에 사각형의 내부로 판단해 틀렸었음.#include#include#include#includeusing namespace std;set>P;set>via;void planet(int a, int b, int r) { P.insert(make_tuple(a, b, r));}void search(int a, int b ,i.. 2024. 7. 2.
자료구조 스터디 6주차 섹션 6) 다익스트라에서 최소 신장 트리까지1.다익스트라 알고리즘시작 노드와 그 외 노드들 간의 최단 거리를 구하는 알고리즘. 엣지는 항상 양수여야 한다.  1. 인접리스트로 그래프 구현하기 (각 노드에서 갈 수 있는 노드와 가중치를 리스트 원소로)(인접행렬로도 구현 가능하지만 시간복잡도 측면에서 인접리스트로 구현해주도록 한다.)2. 최단거리 배열을 초기화한다. (시작노드는 0 나머지는 무한대)3. 값이 가장 작은 노드 고르기(처음은 시작노드가 된다)4. 최단거리 배열 업데이트하기5.모든 노드가 처리될때까지 3, 4 반복. 방문 배열을 만들어 재방문이 일어나지 않도록 한다. 2.벨만포드그래프에서 최단거리를 구하는 알고리즘.출발 노드에서 다른 노든까지의 최단 경로 탐색.엣지는 음수여도 된다.(음수 사이클 .. 2024. 5. 25.

티스토리툴바