[Algorithm] 26. 마라톤

인트로 이전 포스팅에서 다루었던 석차 구하기 문제와 유사하다. 본 문제에서 다룰 전수조사에 관한 내용은 해당 포스팅을 참조하길 바랍니다. [Algorithm] level1 : 석차 구하기 (Brute force 브루트 포스) 인트로 브루트 포스 알고리즘이 적용될 문제를 소개하려 한다. 브루트 포스 Brute force, 브루트 포스는 완전 탐색 알고리즘이다. 완전 탐색 알고리즘이란 모든 경우의 수를 조사하는 방법이다. 자 kangworld.tistory.com 마라톤 문제 KSEA 장거리 달리기 대회가 진행되어 모든 선수가 반환점을 넘었다. 각 선수의 입장에서 자기보다 앞에 달리고 있는 선수들 중 평소 실력이 자기보다 좋은 선수를 남은 거리 동안 앞지르는 것은 불가능하다. 반대로, 평소 실력이 자기보다 ..

• format_list_bulleted Algorithm/it 취업을 위한 알고리즘 문제 풀이
• · 2021. 8. 9.
• textsms

[Algorithm] 25. 석차 구하기 (Brute force 브루트 포스)

인트로 브루트 포스 알고리즘이 적용될 문제를 소개하려 한다. 브루트 포스 Brute force, 브루트 포스는 완전 탐색 알고리즘이다. 완전 탐색 알고리즘이란 모든 경우의 수를 조사하는 방법이다. 자료구조 내의 모든 데이터를 탐색해야 하기에 자료구조에 따른 적절한 탐색 방법이 필요하다. 탐색 기법의 예시를 소개하면 선형 자료구조를 탐색하는 순차 탐색과 트리와 그래프와 같은 비선형 자료구조를 탐색하는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있다. 석차 구하기 문제 N명의 학생의 수학 점수가 입력되면 각 학생의 석차를 입력된 순서대로 출력하는 프로그램을 작성하세요. ※ 입력설명 첫 줄에 N(1 n; vector scores(n); vector ranks(n, 1); for (int i = 0;..

• format_list_bulleted Algorithm/it 취업을 위한 알고리즘 문제 풀이
• · 2021. 8. 8.
• textsms

[Algorithm] 24. Jolly Jumpers

인트로 재밌는 문제라고 생각해서 기록하려 한다. Jolly Jumper를 구하는 문제이다. Jolly Jumper의 정의는 다음과 같다. Jolly Jumper : N개의 정수로 이루어진 수열에 대해 서로 인접해 있는 두 수의 차가 1에서 N-1까지의 값을 모두 가지는 수열 Jolly Jumper 문제 N개의 정수로 이루어진 수열에 대해 서로 인접해 있는 두 수의 차가 1에서 N-1까지의 값을 모두 가지면 그 수열을 유쾌한 점퍼(jolly jumper)라고 부른다. 예를 들어 다음과 같은 수열에 서 1 4 2 3 앞 뒤에 있는 숫자 차의 절대 값이 각각 3 ,2, 1이므로 이 수열은 유쾌한 점퍼가 된다. 어떤 수열이 유쾌한 점퍼인지 판단할 수 있는 프로그램을 작성하라. ※ 입력설명 첫 번째 줄에 자연수 ..

• format_list_bulleted Algorithm/it 취업을 위한 알고리즘 문제 풀이
• · 2021. 8. 6.
• textsms

[Algorithm] 22. 온도의 최대값

인트로 수열이 주어졌을 연속된 값의 합을 계산하고 최댓값만 출력하는 문제이다. 결론부터 말하면 O(N)으로 해결 가능한 문제를 O(N^2)으로 해결하려 했다. 개인적으로 어렵다고 느껴져서 기록을 남긴다. 온도의 최댓값 문제 매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다. 예를 들어, 다음과 같이 10일간의 온도가 주어졌을 때, 3 -2 -4 -9 0 3 7 13 8 -3 모든 연속적인 이틀간의 온도의 합은 다음과 같다. 이때, 온도의 합이 가장 큰 값은 21이다. 매일 측정한 온도가 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 계산하는 프로그램을 작성하시오. ※ 입력설명 첫째 줄에..

• format_list_bulleted Algorithm/it 취업을 위한 알고리즘 문제 풀이
• · 2021. 8. 5.
• textsms

[Algorithm] 19. 분노 유발자

인트로 처음 이중 for문으로 문제를 해결했는데 단일 for문으로도 가능했다는 걸 알았다. 두 방법 모두 포스팅하려 한다. 분노 유발자 문제 오늘은 수능이 끝난 다음날로 교장선생님은 1, 2학년 재학생들에게 강당에 모여 어벤져스 영화를 보여준다고 하여 학생들이 강당에 모였습니다. 강당의 좌석은 영화관처럼 계단형이 아니라 평평한 바닥에 의자만 배치하고 학생들이 앉습니다. 그런데 만약 앞자리에 앉은키가 큰 학생이 앉으면 그 학생보다 앉은키가 작은 뒷자리 학 생은 스크린이 보이지 않습니다. 한 줄에 앉은키 정보가 주어지면 뒷사람 모두의 시야를 가려 영화 시청이 불가능하게 하는 분노 유발자가 그 줄에 몇 명이 있는지 구하는 프로그램을 작성하세요. ※ 입력설명 첫 줄에 한 줄에 앉은 학생수 N(3 n; vecto..

• format_list_bulleted Algorithm/it 취업을 위한 알고리즘 문제 풀이
• · 2021. 7. 30.
• textsms

[Algorithm] 18. 층간소음

인트로 여러 숫자들 사이에서 조건을 만족하는 연속된 숫자의 개수를 구하는 문제이다. 문제 이름은 층간소음이지만 어떠한 형태로 변형이 가능할 만큼 기본적인 문제라 알아보면 좋을 것 같다. 층간소음 문제 T편한 세상 아파트는 층간소음 발생 시 윗집의 발뺌을 방지하기 위해 애초 아파트를 지을 때 바닥에 진동센서를 설치했습니다. 이 센서는 각 세대의 층간 진동소음 측정치를 초단위로 아 파트 관리실에 실시간으로 전송합니다. 그리고 한 세대의 측정치가 M값을 넘으면 세대 호수와 작은 경보음이 관리실 모니터에서 울립니다. 한 세대의 N초 동안의 실시간 측정치가 주어지면 최대 연속으로 경보음이 울린 시간을 구하세요. 경보음이 없으면 -1를 출력합니다. ※ 입력설명 첫 줄에 자연수 N(10 n >> m; for (int..

• format_list_bulleted Algorithm/it 취업을 위한 알고리즘 문제 풀이
• · 2021. 7. 29.
• textsms