비밀일기

트리 그래프의 특수한 형태로 노드와 엣지로 연결된다. 순환 구조가 없고 1개의 루트노드가 존재한다.  트리에서 임의의 두 노드를 이어주는 경로는 유일하다. 노드: 데이터의 인덱스와 값을 표현엣지:노드사이의 연결루트: 최상위 노드리프노드:최하위에 존재하는 노드자식노드: 두 노드 사이에서 하위노드에 해당하는 노드 tree 문제:1) 그래프 풀이   dfs, bfs 문제2) tree만을 위한 문제   이진트리, 세그먼트 트리,lca (최소 공통 조상)      1차원 배열로 트리를 표현      (자식으로 이동할 때는 index*2 or index*2+1 부모로 이동할 때는 index/2...) [백준 11725] 인접리스트 자료구조 사용일반적으로 dfs, bfs사용dfs를 사용해 쉽게 해결 가능 깊이우선 탐..

섹션 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의 차이점은 줄바꿈 문자의 삽입 여부임.    실수와 정수의 입력 예제)만약 자료형을 다르게 입려받는다면 오류가 발생한다. 사용자로부터 입력..

어린 왕자 딱 봤을 때는 어려워 보였는데 조금 생각해보니까 풀 수 있었다. 시작 좌표와 끝 좌표가 속한 원의 개수를 세주었다.만약 한 원에 시작 좌표와 끝 좌표가 둘 다 속해 있다면 그 원은 세지 않음. 이를 위해 집합을 사용해 주었다.또한 집합에 행성의 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..

섹션 6) 다익스트라에서 최소 신장 트리까지1.다익스트라 알고리즘시작 노드와 그 외 노드들 간의 최단 거리를 구하는 알고리즘. 엣지는 항상 양수여야 한다.  1. 인접리스트로 그래프 구현하기 (각 노드에서 갈 수 있는 노드와 가중치를 리스트 원소로)(인접행렬로도 구현 가능하지만 시간복잡도 측면에서 인접리스트로 구현해주도록 한다.)2. 최단거리 배열을 초기화한다. (시작노드는 0 나머지는 무한대)3. 값이 가장 작은 노드 고르기(처음은 시작노드가 된다)4. 최단거리 배열 업데이트하기5.모든 노드가 처리될때까지 3, 4 반복. 방문 배열을 만들어 재방문이 일어나지 않도록 한다. 2.벨만포드그래프에서 최단거리를 구하는 알고리즘.출발 노드에서 다른 노든까지의 최단 경로 탐색.엣지는 음수여도 된다.(음수 사이클 ..

1.지역변수와 스코프지역변수: 특정 지역(변수가 선언된 특정 지역)을 벗어나면 사용될 수 없음.   x 변수는 if블럭 안에서 정의 되었기 때문에 밖에서 출력을 시도할 경우 java: cannot find symbol 오류가 남 블럭 내부에서 블럭 외부에서 선언된 변수 접근 가능블럭 외부에서 블럭 내부에서 선언된 변수 접근 불가능 변수의 접근 가능한 범위를 스코프(scope)라고 한다 for문의 조건식 내부에서 선언된 변수의 경우도 지역변수로 해당 범위를 벗어나면 사용할 수 없다. 2. 스코프의 존재 이유임시적으로 m변수의 값을 변경해주기 위해 temp변수를 사용해주고 있다. 즉 불필요한 메모리를 사용하고 있어 코드블럭 밖에서 temp의 메모리를 제거하면 메모리를 더 효율적으로 쓸 수 있게 된다. 또한 ..

4주차-3)잃어버린 괄호 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.expression에 식을 한줄로 입력받는다. 2+3-4-5 =>  2+3-4-52+3-4+5 =>  2+3-(4+5)2-3+4+5 =>  2-(3+4+5)2-3+4-5 =>  2-(3+4)-(5) -가 올 경우 뒤에 다른 - 가 나올 때까지 나오는 숫자를 괄호로 묶어준다.즉 -가 나온다면 뒤에 나오는 숫자는 모두 뺴주는 식이 결과가 최소가 되는 식이된다. 따라서 minus 변수를 부울형 변수로 선언해주고 ' - ' 연산자가 등장했다면 그 bool값을 true로 변경해준 뒤 그 뒤 모든 숫자를 뺴주는..

4주차-4)회의실 배정한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 벡터 컨테이너를 이용하여 풀이함.벡터 컨테이너 meeting에 각 회의의 끝나는 시간과 시작 시간을 pair로 묶어서 넣어줌.sort함수를 이용하며 저장된 회의 시간을 정렬함.끝나는 시간을 첫 요소로 넣어주어기 떄문에 끝나는 시간이 짧은 회의들이 앞쪽에 오게되고 같은ㄹ 경우 시작 시간이 작은 회의 순서로 정렬된다. 회의가 끝나는 시간을 변수에 저장해 주고 meeting 에 저장된 순서로 꺼내 시작 시간이 저번 회의의 끝나는 시간보다 이후라면 ..

4주차-5)행렬0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.연산을 위한 flip 함수 정의.배열에 저장된 값이 0이라면 1로 1이라면 0으로 바꿔주는 함수.a배열과 b배열을 입력 가능한 최대인  50×50배열로 선언해 주었고 둘의 i행 j열의 값이 같으면 0 다르면 1을 저장해주는 행렬 result도 선언해줌.공백없이 숫자가 입력되기 때문에 스트링 num을 이용해 행을 받고 이를 for문을 이용해 a배열과 b배열에 값을 삽입해 줌.for 문 이중 루프를 이용함여 a와 b에 저장된 모든 원소를 비교해 result에 삽입해줌다음 이중 루프에서는 result의 값을 확인해 1행 1열, 1행 2열,,,,1행 n..

5-1) 그래프노드와 엣지의 집합 유니온 파인드그래프의 사이클이 생성되는지 판별하는 알고리즘위상 정렬사이클이 없는 방향 그래프에서 사용가능.그래프의 노드들을 선형으로 정렬. 정렬 결과가 꼭 한개는 아님 ex)수강신청다익스트라시작점이 존재하고 그 노드에서 다른 모든 노드로 가는 최단 거리를 구하는 알고리즘.단 음수 간선은 있으면 안됨  =>최단거리 알고리즘 벨만-포드다익스트라 알고리즘인데 음수 간선이 가능함.  음수 사이클이 존재하는가=>최단거리 알고리즘 플로이드-워셜벨만 -포드 알고리즘 인데 시작 노드가 없음. 즉 모든 노드 사이의 최단거리 측정. (시간복잡도가 안좋음)=>최단거리 알고리즘 최소 신장 트리 mst. 그래프에서 최소의 가중치 합으로 모든 노드를 연결할 수 있게 해주는 알고리즘. 사이클이 없..

5-1) 반복반복문이 사용되는 이유: 반복적인 수행을 간결하게 작성하기 위해. 특정 코드를 반복해서 실행할 때 사용된다. 반복문에는 while 과 for 문이 존재함 5-2) while문 1while(조건){문장} 조건을 확인하고 조건이 충족될 경우 블럭 속 문장이 시행된다.조건이 만족되지 않을 경우 루프가 계속 실행된다. 5-3) while문 2문제) 숫자가 1씩 증가할때 1,2,3, 덧셈   식을 바꾸고 싶을 때 변경해줄 변수가 적다는 것이 장점 문제)i 부터 end까지 num 개 더하는 식   10 부터 1씩 증가하는 숫자를 3개 더해주는 루프10+11+12=33임 확인 가능 5-3)do while문while문과는 다르게 조건을 만족하지 않아도 한번은 문장을 수행함. do{      문장}while..