목록알고리즘 (11)

최데브는 오늘도 프로그래밍을 한다.

프로그래머스 - 신고 결과 받기

https://programmers.co.kr/learn/courses/30/lessons/92334?language=java 코딩테스트 연습 - 신고 결과 받기 문제 설명 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다. 각 유저는 한 번에 한 명의 programmers.co.kr import java.util.*; class Solution { public int[] solution(String[] id_list, String[] report, int k) { //한 사람이 여러번 똑같은 사람을 신고하는건 의미가 없으므로 distinct로 중복을 다 제거한다. report = Arrays.stream(re..
알고리즘 2022. 3. 21. 21:30
1이 될때까지 최소 연산 횟수

n과 k 라는 자연수가 주어진다고 하면 아래 두가지 연산 중 하나씩 진행하여 n이 1이 되도록 하는데 연산 횟수를 최소화 하는 알고리즘을 작성하라. 1. n 에서 1을 빼기 2. n 에서 k를 나누기 이런 문제가 있다고 하자. 이 문제는 그리디 알고리즘의 유명한 문제다. 해설을 보기전 나의 경우는 n = 25 k = 5 count = 0 while 1 : if n%k ==0: n=n/k count+=1 else : count+=1 n= n-1 if n==1 : break print(count) 이런 식으로 풀었다. 이 방법도 틀린 방법은 아니지만 주어지는 숫자의 범위가 커지면 문제가 생길 수 있다. 그래서 사용하는 테크닉이 해설 코드에 있었다. n = 17 k = 4 count = 0 while 1 : ..
알고리즘 2021. 8. 21. 16:15
알고스팟 - 소풍

#include #include #include #include #include using namespace std; int n, m; int tcase; bool arefriends[10][10]; int dfs(bool selected[10]) { int firstfree = -1; for (int i = 0;i < n;i++) { if (!selected[i]) { firstfree = i;// 아직 골라지지 않은 사람의 인덱스를 저장하고 break break; } } if (firstfree == -1) return 1; int ret = 0; for (int j = firstfree + 1; j < n;j++) { if (!selected[j] && arefriends[firstfree][j])..
알고리즘 2020. 6. 15. 18:17
알고스팟 - 보글게임(무식하게 풀기방법만 적용)

#include #include #include #include #include using namespace std; int n, m; int dx[] = {-1,-1,-1,1,1,1,0,0}; int dy[] = {-1,0,1,-1,0,1,-1,1}; vector visit; string board[5]; bool findword(const string& s, int x, int y ) { //s.substr(1) 로 인해서 재귀를 한번 할때마다 첫번째 글자가 다음 글자로 바뀜 if (board[x][y] != s[0]) return false; if (s.size() == 1) return true;//비교할 글자가 한글자가 되면 탈출 for (int i = 0;i < 8;i++) {//상하좌우대각선..
알고리즘 2020. 6. 15. 16:13
백준 - 1로 만들기

dp 문제였다. 먼저 코드는 아래와 같다. #include #include #include #include using namespace std; int dp[1000001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; dp[1] = 0; dp[2] = 1; dp[3] = 1; for (int i = 4;i
알고리즘/DP 2020. 5. 14. 17:46
백준 - 동전2 , 제곱수의 합

dp유형중 헷갈리는 유형을 정리해보려고 급하게 쓴다. 이런 유형들의 문제는 착각하기 쉬운게 가장 적게 사용하도록 만들라고 해서 조건에 해당하는것중에서 가장 큰거부터 골라나가면 가장 적게 사용하고 구해지겠지? 라고 착각하는것이다. 말이 이상한데 풀어말하자면 동전2 같은 경우에는 동전 종류 3개 이것들을 사용해서 합 15를 만드는데 동전을 가장 적게 사용할때를 구하는건데 동전 종류중에서 12원이 가장 크므로 12를 선택해버리면 남는 3원은 1원짜리 3개로 채워야하기 때문에 동전을 4개 써야하는데 이건 최소가 아니다. 5원동전 3개를 쓰면 해결되기 때문. 이런 오류를 범해서는 안된다. 아래는 제곱수의 합 코드 #include int main(void){ int N; int Dp[100001] = {}; sca..
알고리즘/DP 2020. 4. 26. 01:16
이전 Prev 1 2 Next 다음