본문 바로가기

Algorithm/it 취업을 위한 알고리즘 문제 풀이20

[Algorithm] 50. 영지(territory) 선택 인트로 피보나치 수열로 동적 프로그래밍을 이해했다면 그다음 단계로 풀어볼 적당한 문제인 것 같다. 영지(territory)선택 문제 세종대왕은 현수에게 현수가 다스릴 수 있는 영지를 하사하기로 했다. 전체 땅은 사각형으로 표시된다. 그 사각형의 땅 중에서 세종대왕이 현수가 다스릴 수 있는 땅의 크기(세로의 길이와 가로의 길이)를 정해주면 전체 땅 중에서 그 크기의 땅의 위치를 현수가 정하면 되는 것이다. 전체 땅은 사각형의 모양의 격자로 되어 있으며, 그 사각형 땅 안에는 많은 오렌지 나무가 심겨 있다. 현수는 오렌지를 무척 좋아하여 오렌지 나무가 가장 많이 포함되는 지역을 선택하고 싶어 한다. 현수가 얻을 수 있는 영지의 오렌지 나무 최대 개수를 출력하는 프로그램을 작성하세요. 다음과 같은 땅의 정보가.. 2021. 8. 25.
[Algorithm] 38. 반전 수열(Inversion Sequence) 인트로 수열을 응용한 문제이다. 반전 수열(Inversion Sequence) 문제 1부터 n까지의 수를 한 번씩만 사용하여 이루어진 수열이 있을 때, 1부터 n까지 각각의 수 앞에 놓여 있는 자신보다 큰 수들의 개수를 수열로 표현한 것을 Inversion Sequence라 한다. 예를 들어 다음과 같은 수열의 경우 [4, 8, 6, 2, 5, 1, 3, 7] 1 앞에 놓인 1보다 큰 수는 4, 8, 6, 2, 5. 이렇게 5개이고, 2 앞에 놓인 2보다 큰 수는 4, 8, 6. 이렇게 3개, 3 앞에 놓인 3보다 큰 수는 4, 8, 6, 5 이렇게 4개...... 따라서 4 8 6 2 5 1 3 7의 inversion sequence는 5 3 4 0 2 1 1 0 이 된다. n과 1부터 n까지의 수를 .. 2021. 8. 21.
[Algorithm] 37. Least Recently Used(카카오 캐시 문제 변형) 인트로 LRU 페이지 교체 알고리즘을 간단하게 구현하는 문제이다. 문제에서도 설명하겠지만 LRU란 가장 오랜 시간 사용되지 않은 페이지를 교체하는 운영체제의 페이지 교체 정책 중 하나이다. LRU(Least Recently Used) 문제 캐시 메모리는 CPU와 주기억장치(DRAM) 사이의 고속의 임시 메모리로서 CPU가 처리할 작업을 저장해 놓았다가 필요할 바로 사용해서 처리속도를 높이는 장치이다. 워낙 비싸고 용량이 적어 효율적으로 사용해야 한다. 철수의 컴퓨터는 캐시 메모리 사용 규칙이 LRU 알고리즘을 따른다. LRU 알고리즘은 Least Recently Used의 약자로 직역하자면 가장 최근에 사용되지 않은 것 정도의 의미를 가지고 있습니다. 캐시에서 작업을 제거할 때 가장 오랫동안 사용하지 않.. 2021. 8. 20.
[Algorithm] 35. Special Sort(구글 인터뷰) 인트로 정렬을 알고리즘을 적용하는 문제이다. 어떤 정렬을 사용할진 문제를 읽어보고 고민하길 바란다. Special Sort(구글 인터뷰) 문제 N개의 정수가 입력되면 당신은 입력된 값을 정렬해야 한다. 음의 정수는 앞쪽에 양의 정수는 뒤쪽에 있어야 한다. 또한 양의 정수와 음의 정수의 순서에는 변함이 없어야 한다. ※ 입력 설명 첫 번째 줄에 정수 N(5 n; vector v(n); for (int i = 0; i > v[i]; /*Bubble Sort Begin*/ for (int i = 0; i 0 && v[j+1] < 0) { int temp = v[j]; v.. 2021. 8. 19.
[Algorithm] 33. 3등의 성적은? 인트로 정렬을 사용하는 기초적인 문제이다. 3등의 성적은? 문제 N명의 수학 성적이 주어지면 그중 3등을 한 수학 성적을 출력하는 프로그램을 작성하세요. 만약 학생의 점수가 100점이 3명, 99점이 2명, 98점이 5명, 97점이 3명 이런 식으로 점수가 분포되면 1등은 3명이며, 2등은 2명이며 3등은 5명이 되어 98점이 3등을 한 점수가 됩니다. ※ 입력 설명 첫 번째 줄에 자연수 N(1 n; vector v(n); for (i = 0; i > v[i]; /*Selection Sort Begin*/ for (i = 0; i < n - 1; i++) { minIdx = i; for (j = i + 1; j < n; j++) { if (v[minIdx] < v[j]) min.. 2021. 8. 18.
[Algorithm] 31. 탄화수소 질량 인트로 문제 자체는 심플하지만 결과를 도출하기 위해 여러 조건을 검사해야 하는 문제를 소개하려 한다. 탄화수소 질량 구하기 문제 탄소(C)와 수소(H)로만 이루어진 화합물을 탄화수소라고 합니다. 탄소(C) 한 개의 질량은 12g, 수소(H) 한 개의 질량은 1g입니다. 에틸렌(C2H4)의 질량은 12*2+1*4=28g입니다. 메탄(CH4)의 질량은 12*1+1*4=16g입니다. 탄화수소 식이 주어지면 해당 화합물의 질량을 구하는 프로그램을 작성하세요. ※ 입력설명 첫 줄에 탄화수소식이 주어집니다. 식의 형태는 CaHb 형태이며 (1 str; if (str[1] == 'H') { cCount = 1; pos = 1; } else { int i; for (i = 1; str[i] != 'H'; i++) { .. 2021. 8. 13.
[Algorithm] 29. 3의 개수는?(small) 인트로 1부터 N까지 숫자에서 3이 몇 개 있는지 구하는 문제이다. N의 범위가 작은 만큼 시간제한이 없는 문제이다. 시간제한이 없다면 코딩 기초 문제에 포함되는 문제이지만 시간제한이 있다면 난이도가 엄청나게 올라가니 본 문제를 풀어보고 시간제한이 있다면 어떤 방식으로 풀어야 할지 고민해보자 나중에 시간이 된다면 시간제한이 버전을 포스팅하려 한다. (링크 추가 예정) 3의 개수는? (시간제한 없음) 문제 자연수 N이 입력되면 1부터 N까지의 자연수를 종이에 적을 때 각 숫자 중 3의 개수가 몇 개 있는지 구하려고 합니다. 예를 들어 1부터 15까지는 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 1, 5으로 3의 개수는 2개입니다. 자연수 N이 입력.. 2021. 8. 12.
[Algorithm] 28. N!에서 0의 개수 인트로 본 문제는 수학적인 사고를 요구합니다. 본 문제를 해결하기 어렵다면 이전 포스팅 N!의 표현법을 풀어보시길 권장합니다. [Algorithm] level1 : N!의 표현법 인트로 꽤나 수학적인 문제이다. 문제를 풀기 전 알아야 할 한 가지 개념이 있다. 2 이상의 모든 자연수는 소수의 곱으로 표현할 수 있다. 예를 들어 12는 2 x 2 x 3으로 표현할 수 있다. 이처럼 2 이 kangworld.tistory.com N!에서 0의 개수 문제 자연수 N이 입력되면 N! 값에서 일의 자리부터 연속적으로 ‘0’이 몇 개 있는지 구하는 프로그램을 작성하세요. [예시] 5! = 5 X 4 X 3 X 2 X 1 = 120으로 일의 자리부터 연속된 ‘0’의 개수는 1입니다. 12! = 479001600으로 .. 2021. 8. 11.
[Algorithm] 27. N!의 표현법 인트로 꽤나 수학적인 문제이다. 문제를 풀기 전 알아야 할 한 가지 개념이 있다. 2 이상의 모든 자연수는 소수의 곱으로 표현할 수 있다. 예를 들어 12는 2 x 2 x 3으로 표현할 수 있다. 이처럼 2 이상의 자연수는 소수의 곱으로 쪼개질 수 있다. N!의 표현법 문제 임의의 N에 대하여 N!은 1부터 N까지의 곱을 의미한다. 이는 N이 커짐에 따라 급격하게 커진다. 이러한 큰 수를 표현하는 방법으로 소수들의 곱으로 표현하는 방법이 있다. 먼저 소수는 2, 3, 5, 7, 11, 13... 순으로 증가함을 알아야 한다. 예를 들면 825는 (0 1 2 0 1)로 표현이 가능한데, 이는 2는 없고 3은 1번, 5는 2번, 7은 없고, 11은 1번의 곱이라는 의미이다. 101보다 작은 임의의 N에 대하.. 2021. 8. 10.
반응형