비밀일기

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

4-1)소수 구하기 핵심 이론소수: 1과 자기 자신 외 약수가 존재하지 않는 수 기본 원리에라토스테네스의 체:1. 구하고자 하는 범위만큼 1차원 배열 생성2. 2부터 시작하고 현재 숫자가 지워지지 않을 때 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하며 지움.이때 처음 선택한 숫자는 지우지 않는다.3. 배열의 끝까지 반복해준 후 배열에남아 있는 모든 수 출력이중 for문을 사용하므로 시간 복잡도는 N^2최적화 정도에 따라서 실제 속도는 n(log(logn))임.배수 삭제 과정에서 바깥쪽 for문을 생략하는 경우가 빈번하게 발생하기 때문에라토스테네스의 체는 소수를 구하는 일반적 방법으로 이용된다.  4-2)오일러 피자주 등장하지는 않음오일러 피 함수 p(n)의 정의는1부터 n까지의 숫자중..

4-1)조건문 특정 조건에 따라 다른 코드를 실행하는 문장조건문을 만족하면 블럭 안 문장이 실행되고 아닌 경우 else가 실행되거나 else문이 없는 경우 다음 문장으로 넘어간다.  4-2)else-if문여러가지 케이스가 존재하는 경우 사용된다.if문의 나열을 통해서도 케이스를 검사할 수 있지만 그럴 경우 코드가 불필요하게 길어지고 앞에서 검사한 부분을 뒤에서 다시  검사하게 되는 상황이 발생하게 된다.이 상황에서 결과를 중복 확인하는 상황을 피하기 위해 else if문 사용.else문은 있어되 되고 없어도 된다.4-3)if문과 if-else문 if(조건)...if(조건) 각각의 조건을 서로에게 영향을 받지 않고 검사하는 경우 if(조건)...else(조건)각각의 조건을 검사하되 공통되는 부분의 검사는 ..