알고리즘 문제풀이
-
[프로그래머스/Level 2] k진수에서 소수 개수 구하기알고리즘 문제풀이/프로그래머스 2022. 10. 10. 17:13
https://school.programmers.co.kr/learn/courses/30/lessons/92335 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 카카오 기출 입력받은 숫자 n을 k진수로 변환하는 것은 어렵지 않다. 그러나 주의해야 할 점이 두 가지 존재한다. 1. k진수로 변환된 수가 int의 범위를 벗어날 수 있다. 2. 단순히 2부터 k진수로 변환된 수 - 1 값을 하나씩 체크하며 소수 여부를 판단하면 TLE 발생할 수 있다. (아마 1번 TC에서 TLE이 발생할 것이다.) 1번은 long long 타입을 사용함으로써 해결할 수 있고,..
-
[프로그래머스/Level 1] 신고 결과 받기알고리즘 문제풀이/프로그래머스 2022. 10. 3. 18:54
https://school.programmers.co.kr/learn/courses/30/lessons/92334 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 카카오 기출 (다시 풀기, 작년 공채 때 풀었는데 왜 못풀지? ㅋ) 신고 내역을 담을 map과 신고 결과를 기록할 map을 각각 선언하여 문제를 해결할 수 있다. 다음과 같이 입력 값이 주어졌다고 가정해보자. ["muzi frodo","apeach frodo","frodo neo","muzi neo","apeach muzi"], k = 2 신고 내역(key=신고자, value=피신고자 집합) mu..
-
[프로그래머스/Level 3] 등산코스 정하기알고리즘 문제풀이/프로그래머스 2022. 9. 29. 23:39
https://school.programmers.co.kr/learn/courses/30/lessons/118669 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 카카오 기출 (다시 풀기) 다익스트라 알고리즘이란 한 정점에서 다른 정점까지의 최단 거리를 구하는 알고리즘이다. 이를 해당 문제에 적용해본다면 다음과 같이 된다. "한 출입구에서 다른 지점까지의 최소 intensity를 구하기" 이때 주의해야할 점은 결국 다익스트라 알고리즘은 최악의 경우 모든 정점을 방문하게 되는데, TLE 발생할 수 있다. 주목해야할 것은 '각 지점은 양방향 통행이 가능한 등..
-
[프로그래머스/Level 2] 두 큐 합 같게 만들기알고리즘 문제풀이/프로그래머스 2022. 9. 24. 23:09
https://school.programmers.co.kr/learn/courses/30/lessons/118667 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 카카오 기출, 그리디 유형 sum1과 sum2를 구한 후 다음과 같이 그리디를 적용한다. sum1 > sum2인 경우, q1 pop후 q2로 insert sum1 < sum2인 경우, q2 pop 후 q1으로 insert 해당 방법이 왜 유요한지 검증해보자면, sum1과 sum2의 합이 같아야하므로 합이 큰 쪽에서 원소를 pop하여 작은 쪽으로 insert를 해줘야 최소 횟수로 두 합을 같게 만..
-
[프로그래머스/Level 1] 성격 유형 검사하기알고리즘 문제풀이/프로그래머스 2022. 9. 24. 17:18
https://school.programmers.co.kr/learn/courses/30/lessons/118666 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 카카오 기출 #include #include #include #include #include using namespace std; string table[4] = {"RT", "CF", "JM", "AN"}; int score[8] = {0, 3, 2, 1, 0, 1, 2, 3}; map m; string solution(vector survey, vector choices) { string a..
-
[백준/BOJ] N과 M (1), (2), (3), (4), (5), (6), (7), (8), (9), (10), (11)알고리즘 문제풀이/백준 2022. 9. 22. 21:50
N과 M (1) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define lp1(i, x, n) for(int i = x; i
-
[백준/BOJ] 14620번 꽃길알고리즘 문제풀이/백준 2022. 6. 21. 00:35
https://www.acmicpc.net/problem/14620 14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net 쉬운 DFS 문제였다. 씨앗을 3개 심을 수 있는 모든 경우의 수를 구한 후, 해당 케이스가 꽃이 피어날 수 있는지를 확인하면 된다. 배열을 여러 개 두면 쉽게 구현할 수 있다. (코드 참고) #include #define f first #define s second #define lp1(i, x, n) for(int i = x; i = answer) return false; } sum = tm..
-
[백준/BOJ] 9934번 완전 이진 트리알고리즘 문제풀이/백준 2022. 6. 9. 17:18
https://www.acmicpc.net/problem/9934 9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net 중위 탐색의 결과를 완전 이진 트리로 바꿔야 하는 문제다. 특정 depth까지 left와 right을 설정해 루트 노드를 탐색하는 방법을 반복하면서 문제를 해결하는데, 이분 탐색을 재귀로 구현하는 것과 비슷하다. #include #define f first #define s second #define lp1(i, x, n) for(int i = x; i = n) retur..