본문 바로가기

Algorithm/Inflearn

Algorithm/Inflearn 2022. 11. 29. [Inflearn] 자바 알고리즘 문제풀이 #02-12 12. 멘토링 문제 설명 현수네 반 선생님은 반 학생들의 수학점수를 향상시키기 위해 멘토링 시스템을 만들려고 합니다. 멘토링은 멘토(도와주는 학생)와 멘티(도움을 받는 학생)가 한 짝이 되어 멘토가 멘티의 수학공부를 도와주는 것입니다. 선생님은 M번의 수학테스트 등수를 가지고 멘토와 멘티를 정합니다. 만약 A학생이 멘토이고, B학생이 멘티가 되는 짝이 되었다면, A학생은 M번의 수학테스트에서 모두 B학생보다 등수가 앞서야 합니다. M번의 수학성적이 주어지면 멘토와 멘티가 되는 짝을 만들 수 있는 경우가 총 몇 가지 인지 출력하는 프로그램을 작성하세요. 입력 첫 번째 줄에 반 학생 수 N(1
Algorithm/Inflearn 2022. 11. 29. [Inflearn] 영리한 프로그래밍을 위한 알고리즘 - 순환 (Recursion) 의 응용 : 멱집합(powerset) 멱집합 (powerset) 문제 멱집합 : 어떤 집합 A에 대하여 A의 모든 부분 집합들로 이루어진 집합 예를 들어, A : {a, b, c}라면 A의 멱집합은 ø, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}의 8개가 되며 원소가 n개일 때 멱집합의 개수는 2^n개이다. (원소 하나가 포함되거나, 포함되지 않거나 2가지의 경우의 수를 가지기 때문) 알고리즘 멱집합을 recursion 방식으로 생각해보자. 이 알고리즘의 ✨✨✨✨ 가장 큰 포인트 ✨✨✨✨는 1) 원소 a를 포함한 부분집합들과 2) 원소 a를 포함하지 않는 부분집합들로 나뉜다는 것이다. 원소 a는 상황에 따라 여러 개가 될 수 있다. 위의 예시에서는 {a}, {a, b}, {a, c}, {a, b,..
Algorithm/Inflearn 2022. 11. 28. [Inflearn] 자바 알고리즘 문제풀이 #02-11 11. 임시반장 정하기 문제 설명 김갑동 선생님은 올해 6학년 1반 담임을 맡게 되었다. 김갑동 선생님은 우선 임시로 반장을 정하고 학생들이 서로 친숙해진 후에 정식으로 선거를 통해 반장을 선출하려고 한다. 그는 자기반 학생 중에서 1학년부터 5학년까지 지내오면서 한번이라도 같은 반이었던 사람이 가장 많은 학생을 임시 반장으로 정하려 한다. 그래서 김갑동 선생님은 각 학생들이 1학년부터 5학년까지 몇 반에 속했었는지를 나타내는 표를 만들었다. 예를 들어 학생 수가 5명일 때의 표를 살펴보자. 위 경우에 4번 학생을 보면 3번 학생과 2학년 때 같은 반이었고, 3번 학생 및 5번 학생과 3학년 때 같은 반이었으며, 2번 학생과는 4학년 때 같은 반이었음을 알 수 있다. 그러므로 이 학급에서 4번 학생과 한번이라도 같은 반이었던 ..
Algorithm/Inflearn 2022. 11. 22. [Inflearn] 영리한 프로그래밍을 위한 알고리즘 - 순환 (Recursion) 의 응용 : n queens problem n queens problem 문제 n queens problem이란 무엇인가? n*n 체스판에서 어떠한 두 말도 동일한 행이나 열, 동일한 대각선 상에 오지 않도록 n개의 말을 놓을 수 있느냐의 문제 알고리즘 하나의 말을 첫 행의 아무 위치에 일단 놓은 후, 나머지 행에 다른 말들을 모두 놓을 수 있는지 확인한다. 확인하는 과정에서 back tracking 방법이 사용된다. back tracking이란? 말을 두었다가 문제를 해결하지 못할 경우 해당 위치에 말을 둔 결정을 번복하고 다른 위치에서 문제를 해결할 방법을 찾는 것이다. 쉽게 말하면 "무르기!"다. (사람이 노가다로 문제를 풀려고 하는 방식과 원리가 같으니 4x4체스판으로 한 번 해보면 더 알기 쉬울 것 같다.) SW적 용어로는 그래프의 깊이..
Algorithm/Inflearn 2022. 11. 22. [Inflearn] 자바 알고리즘 문제풀이 #02-10 10. 봉우리 문제 설명 지도 정보가 N*N 격자판에 주어집니다. 각 격자에는 그 지역의 높이가 쓰여있습니다. 각 격자판의 숫자 중 자신의 상하좌우 숫자보다 큰 숫자는 봉우리 지역입니다. 봉우리 지역이 몇 개 있는 지 알아내는 프로그램을 작성하세요. 격자의 가장자리는 0으로 초기화 되었다고 가정한다. 만약 N=5 이고, 격자판의 숫자가 다음과 같다면 봉우리의 개수는 10개입니다. 입력 첫 줄에 자연수 N이 주어진다.(2 arr[i-1][j] 이런 식으로 네 방향 적어놓아서 IndexOutOfBoundsException 떴지만 해결할 수 없었다. (테두리에 000000을 추가하지 않는 이상 풀 수 없는 방식) 특정 좌표에서 근접 좌표들에 접근할 때 int[] dx = {-1, 0, 1, 0}; int[] dy = {0,..
Algorithm/Inflearn 2022. 11. 21. [Inflearn] 영리한 프로그래밍을 위한 알고리즘 - 순환 (Recursion) 의 응용 : Counting Cells in a Blob Blob(이어진 블록) 세기 문제 그리드에서 흰색 부분은 backgroud pixel, 파란색 부분은 image pixel이며 image pixel이 서로 이어지게 연결된 집합을 blob이라고 한다. (상하좌우, 대각방향도 이어진 것으로 간주) 해당 예제에서는 위처럼 4개의 blob이 존재하고, 한 blob 안의 image pixel의 개수가 size(크기)가 된다. 알고리즘 입력 N*N 크기의 2차원 그리드 하나의 좌표(x,y) 출력 픽셀 (x,y)가 포함된 blob의 크기 (x,y)가 어떤 blob에도 속하지 않는 경우 0 sudo code 1) 그리드를 벗어나거나 2) image pixel이 아니거나 이미 방문한 적이 있는 pixel 이라면 false를 반환해 불필요한 곳을 탐색하지 못하도록 한다...
Algorithm/Inflearn 2022. 11. 21. [Inflearn] 자바 알고리즘 문제풀이 #02-09 9. 격자판 최대합 문제 설명 5*5 격자판에 아래롸 같이 숫자가 적혀있습니다. N*N의 격자판이 주어지면 각 행의 합, 각 열의 합, 두 대각선의 합 중 가 장 큰 합을 출력합니다. 입력 첫 줄에 자연수 N이 주어진다.(2
Algorithm/Inflearn 2022. 11. 21. [Inflearn] 자바 알고리즘 문제풀이 #02-08 8. 등수구하기 문제 설명 N명의 학생의 국어점수가 입력되면 각 학생의 등수를 입력된 순서대로 출력하는 프로그램을 작성하세요. 같은 점수가 입력될 경우 높은 등수로 동일 처리한다. 즉 가장 높은 점수가 92점인데 92점이 3명 존재하면 1등이 3명이고 그 다음 학생은 4등이 된다. 입력 첫 줄에 N(3

티스토리툴바