분류 전체보기
프로그래머스 - 다음 큰 숫자
programmers.co.kr/learn/courses/30/lessons/12911 코딩테스트 연습 - 다음 큰 숫자 자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다. 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다. 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니 programmers.co.kr 단순히 이진수로 변환해서 1의 갯수를 비교하고, 같으면 나가게 하고 아니면 n 을 하나씩 늘리면서 비교하면 된다. 답이 항상 n 보다 큰 자연수이므로 초기의 answer 를 n + 1 로 잡고 시작한다. - c++ #include using namespace std; bool number_of_one(int num1, int num2) { in..
프로그래머스 - 기능 개발
programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr 큐를 사용해서 처리해야하는 문제다. 각 작업별 100% 도달할때 까지 경과되는 시간들을 전부 큐에 넣는다. 그리고 큐가 비어있게 될때 까지 수를 하나씩 빼면서 큐의 프론트 부분 이상의 값인 경우, 동시에 끝낼 수 있는 작업이므로 작업 처리 량을 나타내는 cnt 변수를 하나씩 늘리고 더이상 큐의 프론트 부분 보다 크거나 같은 값이 아니면 반복문을 종료하여, answer ..
프로그래머스 - 124 나라의 숫자
programmers.co.kr/learn/courses/30/lessons/12899?language=cpp 코딩테스트 연습 - 124 나라의 숫자 programmers.co.kr 문제 설명의 예시들을 보다 보면 1, 2, 4 이 세개의 숫자로 모두 처리하므로, 3으로 나누면서 해결할 수 있음을 알 수 있게 된다. 3으로 나눈 나머지가 0 -> 4 3으로 나눈 나머지가 1 -> 1 3으로 나눈 나머지가 2 -> 2 나머지값을 answer 앞에 하나씩 붙이면서 처리하고 n 을 줄여야하므로, 3으로 나누는데, 주의할점은 3으로 나눌때 n /= 3 만으로는 오류가 날 수 있다. 예를들어, n = 6 일때, 처리 과정을 보면 처음에 answer = arr[6 % 3] + answer 가 되어 answer = ..
프로그래머스 - 피보나치 수
programmers.co.kr/learn/courses/30/lessons/12945 코딩테스트 연습 - 피보나치 수 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 예를들어 F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) = programmers.co.kr 기본적인 dp 를 이용한 피보나치 수 문제다. - c++ #define MOD 1234567 using namespace std; int dp[100001]; int solution(int n) { in..
프로그래머스 - 최댓값과 최솟값
programmers.co.kr/learn/courses/30/lessons/12939 코딩테스트 연습 - 최댓값과 최솟값 문자열 s에는 공백으로 구분된 숫자들이 저장되어 있습니다. str에 나타나는 숫자 중 최소값과 최대값을 찾아 이를 (최소값) (최대값)형태의 문자열을 반환하는 함수, solution을 완성하세요. 예를 programmers.co.kr 단순한 최대, 최소 찾기 문제이다. s 의 최대 길이가 문제에 제시되 있지 않아서 이중 포문을 쓰면 시간 초과가 날지 안날지 알 수 가 없었는데 일단은 통과가 되었다. s 의 길이가 컸다면 통과하지는 못했을 것이다. 그때는 뭐 투포인터 쓰든가 해서 시간 초과를 피할듯하다 - c++ #include #include #define INF 987654321 ..
BOJ 17142 - 연구소 3
www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 생각보다 이해하는데 시간이 꽤 걸렸던 문제다. 백준 17141 번 연구소 2와 거의 유사하긴 하나, 선택하지 않은 바이러스(비활성 바이러스) 의 경우, 시간 처리를 +1 을 해주지 않고 그대로 bfs 값을 넘겨 받아야 한다는게 차이점이었다. 예를들어, 주어진 맵이 다음과 같다고 하면 N = 4, M = 2 0 1 1 0 2 1 1 2 2 1 1 2 0 1 1 0 이 맵에 대한 연구소 3의 코드 실행 결과는 2가 나와야 ..
BOJ 1780 - 종이의 갯수
www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. www.acmicpc.net 백준 1992 쿼드 트리 (www.acmicpc.net/problem/1992) 문제와 유사한 문제이다. 분할 정복 기법을 사용해야만 풀 수 있는 문제로, 쿼드 트리에서는 4분할을 했다면, 이 종이의 갯수 문제는 9분할을 해야한다. 시작 좌표를 처음에는 (0, 0) 으로 잡고 크기를 전체 크기(n) 으로 잡는다. 즉 (0, 0) 에서 부터 n * n 크기의 이차원 행렬을 전체 순회한뒤, 원소의 갯수가..
BOJ 17141 - 연구소 2
www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net BFS 와 조합을 써야 풀 수 있는 문제이다. 전체 바이러스의 갯수를 센뒤에 각 바이러스의 좌표를 벡터에 담아둔다 그리고 조합을 사용해서 전체 바이러스의 갯수 중 m 개를 뽑아서 bfs 를 진행한다. * 주의할점은 뽑아놓은 m 개의 바이러스가 동시에 bfs 를 수행해야 한다는 점이다. 이렇게 하기 위해서는 bfs 함수에 들어갈때 바이러스의 좌표 (y, x) 를 큐에 넣는게 아니라, m 개를 뽑으면서 bfs 함수에서 사용..