알고리즘

[C++] 하키(1358번)

문제 풀이 첫번째 예제를 예로 들면 이런 상황이라고 볼 수 있습니다. 이 문제를 푸는 알고리즘은 다음과 같습니다. 직사각형안인가? 왼쪽 반원 중심부터 거리가 r(=h/2) 이하인가? 오른쪽 반원 중심부터 거리가 r(=h/2) 이하인가? 위 셋 중에 하나라도 포함된다면 링크안에 있는것으로 판별합니다. 코드로 표현하면 다음과 같습니다. #include #include using namespace std; int main() { double w,h,x,y,p; //p는 선수의 수 cin>>w>>h>>x>>y>>p; int aws=0; for(int i=0; i>p_x>>p_y; double distance_from_left_circle=sqrt(pow((x-p_x),2)+pow(y+h/2-p_y,2)); do..

[C++] 주식가격(Lv.2)

문제 풀이 2중 for문을 사용했습니다. 처음 for문은 검사할 시점의 주식가격을 결정하고 두번째 for문에서는 첫번째 for문에서 결정된 가격에비해 하락이 있었나 여부를 판단해서 계산합니다. #include #include using namespace std; vector solution(vector prices) { vector answer; for(int i=0; i

[C++] 어린 왕자(1004번)

문제 풀이 진입/이탈을 세는 매커니즘은 다음과 같습니다. 출발점이 해당 행성계 안에 있는지 확인합니다. 도착점이 해당 행성계 안에 있는지 확인합니다. 출발,도착점 둘다 해당 행성계 안에 있거나 밖에 있는거 아니면 count를 증가시켜줍니다. (=진입/이탈횟수를 저장하는 변수) #include #include #include #include using namespace std; int main() { int t; //테스트케이스 cin>>t; for(int i=0; i>startX>>startY>>endX>>endY; pair start=make_pair(startX,startY); //출발점 pair end=make_pair(endX,endY); //도착점 int n; //행성계 갯수 cin>>n; ve..

[C++] 백준-터렛(1002번)

문제 풀이 int t; cin>>t; 먼저 테스트케이스의 갯수 T를 입력받습니다. int x1,y1,r1,x2,y2,r2; for (int i = 0; i >x1>>y1>>r1>>x2>>y2>>r2; double distance=sqrt(pow(x1-x2,2)+pow(y1-y2,2)); ... x1,y1,r1 x2,y2,r2값을 입력받고, 두 원의 중심 사이의 거리를 distance에 저장합니다. //원이 겹칠떄 if (distance == 0 && r1 == r2) cout r2 ? r2 : r1) r2 ? r1 : r2)) cout r2 ? r1 : r2)는 오른쪽 상황입니다. 이때 원이 완전히 겹치는 경우에도 distance + (r1 > r2 ? r2 :..

[C++] 올바른 괄호 (Lv.2)

문제 풀이 고려해야할 핵심 내용은 다음과 같습니다. 자신의 작업이 완료되었을때 자기 앞의 모든 일이 완료되어야만 배포 가능하다.( 아니면 대기 ) 저는 이를 다음과 같은 매커니즘으로 풀었습니다. 각 progresses에 for문을 사용해서 해당하는 speeds를 더해줍니다. (for문을 한바퀴 다 돌때마다 day가 하루씩 지난다는 생각) 만약 progresses의 어떤 작업이 100이상이 되었다면 작업이 끝났다는 것인데 이때 해당 작업의 위치의 인덱스가 0일때만 해당 날짜에 배포된 처리를 해줍니다. = 벡터에서 erase해줍니다. for문을 한번 다 돌았을때 배포된 작업의 갯수가 0이 아니라면 aws벡터(reuturn 예정인 벡터)에 push_back해줍니다. 만약 배포된 작업의 갯수가 총 작업의 갯수와..

[C++] 백준-택시 기하학(3053번)

문제 풀이 이 문제는 소수점을 고정해서 출력하는 방법을 고민해보라는 문제인 것 같습니다. #include using namespace std; int main() { double uclid,taxi; int r; cin>>r; cout

[C++] 올바른 괄호 (Lv.2)

문제 풀이 괄호 판별은 '스택'을 이용해서 하는것이 보통입니다. 컴파일러 과목을 들어보신 분들은 아마 구현해 본 적이 있을 것 입니다. 매커니즘 '('가 등장하면 스택에 1을 넣습니다. ')'가 등장하면 스택에서 pop을 해줍니다. 만일 스택이 empty상태여서 pop을 할 수가 없으면 false를 return해줍니다. 문자열의 마지막까지 읽었는데 스택이 empty가 아니라면 '('가 상대적으로 많은 상태이기 때문에 false를 return 해줍니다. 문자열의 마지막까지 읽었는데 스택이 empty가 맞다면 정상이므로 true를 return해줍니다. #include #include #include using namespace std; bool solution(string s) { stack st; if(s..

[C++] 124 나라의 숫자 (Lv.2)

문제 풀이 이 문제의 규칙?은 일단 기본적으로 n을 3으로 계속해서 나눕니다 ( 몫이 0이 될때까지 ) 그때그때 나오는 나머지가 있을텐데 나머지가 0=>4 1=>1 2=>2 에 대응됩니다. 이 나머지에 대응되는 숫자는 124나라의 숫자에서 가장 오른쪽부터 채워집니다. 여기서 이 규칙을 사용하기 위해서 유의해야 할 것이 있는데, 나머지가 0일때는 몫-1을 해줘야 한다는 것입니다. ex) n==15일때 먼저 n/3을 하면 몫:5 , 나머지:0 그럼 일단 "4"가 채워짐. 근데 이때 나머지가 0이니까 몫-1을해서 4가됨. 4/3을 하면 몫:1 , 나머지:1 그럼 "1"이 추가로 채워져서 "14"가 됨. 1/3을 하면 몫:0 , 나머지:1 그럼 "1"이 추가로 채워져서 "114"가 됨. 이떄 몫이 0이 됐으므로..