CS (26) 썸네일형 리스트형 [Baekjoon Online Judge] 1629. 곱셈 // 해설 (Java) https://www.acmicpc.net/problem/1629문제 핵심결론부터 말하면 재귀 함수를 이용한 분할 정복으로 풀었습니다.이 둘에 대해 잘 모른다면 먼저 학습한 후에 풀어보는 것도 좋을 것 같습니다. 거듭제곱을 단순 반복문으로 계산하면 O(B)의 시간복잡도를 가지게 됩니다.B는 최대 2,147,483,647이므로 시간 초과 결국 시간 복잡도를 줄이라는 문제인데 분할 정복을 사용하면 O(logB)의 시간 복잡도를 가집니다.a*a*a*a*a*a = (a*a*a) * (a*a*a) 라는 성질을 이용해서중복되는 계산을 반으로 줄이면 이렇게 log 시간 복잡도를 가지게 됩니다.구현코드 (Java)import java.io.BufferedReader;import java.io.IOException;im.. [Baekjoon Online Judge] 1043. 거짓말 // 해설 (Java) https://www.acmicpc.net/problem/1043 문제 해설파티에 진실을 아는 사람이 있다면 반드시 진실을 말해야 하고 그 파티에 함께 있는 사람도 진실을 아는 사람이 되는 아주 현실적인 상황이라 문제를 해석하는 것은 어렵지 않습니다. 다만 주의할 점은 파티에서 거짓말을 한 뒤에 참여자가 진실을 아는 사람이 되는 상황도 있어서는 안 된다는 것입니다. 따라서 핵심은 모든 파티가 끝났을 때를 기준으로 진실을 아는 사람을 골라내고, 진실을 아는 사람이 포함되지 않은 파티의 수를 세면 된다는 것 입력의 크기가 워낙 작아서 Brute-force를 포함해 아마 다양한 방법으로 풀 수 있을 것 같습니다. (귀찮아서 풀어보지는 않음) 하지만 그러면 시뮬레이션 유형에 가까워지고 구현이 더 복잡해질 것 같.. [Baekjoon Online Judge] 4195. 친구 네트워크 // 해설 (Java) https://www.acmicpc.net/problem/4195 문제해설이 문제는 Union-Find 응용 문제입니다.따라서 Union-Find에 대한 기본적인 지식이 있다고 가정하고 설명하겠습니다. 이 문제에서는 단순히 같은 집합에 속하는지를 확인하는 것뿐만 아니라, 집합의 크기도 알아야 하기 때문에 약간의 응용이 필요합니다. 구현 자체는 어렵지 않기 때문에 한 번만 익혀두면 이후에는 쉽게 구현할 수 있습니다. 기존에는 루트 노드가 부모를 자기 자신으로 설정하여 자신이 루트임을 표시했습니다.집합의 크기가 필요한 경우에는 루트의 부모 값에 집합의 크기를 음수로 저장합니다.그러면 루트 노드의 조건은 부모가 음수인 것이며, 집합의 크기는 루트 노드의 부모 값의 부호를 반대로 바꾼 값이 됩니다.여기서 음수로.. [SW Expert Academy] 10726. 이진수 표현 (Java) 문제 설명핵심대놓고 비트 연산을 다룰 수 있는지 묻는 문제예시 입력 중 하나로 "4 47"이 있다.47은 이진법으로 101111이므로 첫 4개의 비트가 1이 된다. 이를 계산식으로 확인하는 방법해당 수가 15(이진수 1111)와 AND 연산(두 수의 같은 위치의 비트가 모두 1이면 1)을 했을 때, 15가 나오면 첫 4개의 비트가 모두 1임을 알 수 있다. 앞 N개의 비트가 1인 이진수를 구하는 방법먼저 쉬프트 연산에 대해 알아야한다. 0001을 왼쪽 쉬프트 연산하면 0010이다. (자바에서) a 1. 1을 n만큼 좌측 쉬프트 연산한다. // 1 2. 1을 뺀다. // 이진수10000 - 1 = 01111 AND 연산하는 법& 연산자를 통해 각 비트에 대한 논리 연산을 수행할 수 있다.구현Code (J.. [Programmers] GROUP BY > 년, 월, 성별 별 상품 구매 회원 수 구하기 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 문제핵심JOIN이 문제에서는 필요한 정보(년, 월 / 성별)가 두 테이블에 걸쳐 나누어져있습니다.따라서 두 테이블을 합치는게 선행되어야 하고 이를 위해 JOIN을 이용합니다. GROUP BY문제의 조건에 언급된 '년, 월, 성별 별로'는 'GROUP BY 년, 월, 성별' 구문과 의미가 정확히 일치합니다.그룹으로 묶었기 때문에 그 안에 여러 레코드가 포함되어 있을 것입니다.집계 함수를 사용하면 그 정보를 가공하여 표현할 수 있습니다.여기선 COUNT를 이용해서 사용자의 수를 표현하였습니다. DISTINCT출력 조.. [Baekjoon Online Judge] 12865. 평범한 배낭 (Java) https://www.acmicpc.net/problem/12865 설명핵심용량이 제한된 배낭에 넣을 수 있는 최대 가치를 구하는 유명한 문제인 Knapsack Problem 그 중에서 0/1 Knapsack Problem과 동일한 문제이다. 가장 단순한 방법을 생각해보자. 물품의 개수는 최대 100개 이다. 따라서 물품을 넣거나 넣지 않거나 두가지 선택지를 100개 물품에 대해 모두 적용하고 가치를 확인한다면, 2^100가지 상황을 검사해야 한다. 즉, 물품의 개수 N에 대해 시간복잡도가 O(2^N)이다. 즉, 시간복잡도를 줄일 방법을 떠올리는 것이 핵심이다. 하지만 이 문제는 워낙 유명하고 떠올리기 쉽지 않기 때문에 그냥 한번 풀어보는 것이 현명한 방법이라고 생각한다.구현알려진 방법에 따라 시간복잡도.. [Baekjoon Online Judge] 2839. 설탕 배달 (C++, Java) https://www.acmicpc.net/problem/2839 설명핵심이 문제의 핵심은 5kg 봉지가 많을수록 더 적은 봉지로 채울 수 있다는 것이다.단, 주어진 용량을 꽉 채워야 한다. 그리고 N이 최대값인 5000일 때, 가장 무식한 방법으로 푼다고 생각해보자.1. 먼저 5kg 봉지만으로 채워본다.2. 그 다음 3kg 봉지를 1개 넣고 나머지를 모두 5kg 봉지로 채워본다....?. 3kg 봉지만으로 채워본다딱 봐도 너무 무식해서 이렇게 풀고싶지는 않을 것이다.위 방식의 문제는 최초에 5kg으로 채우는 과정에서 알아낸 데이터를 다 버리고 다음 단계에서 새로 시작한다는 것이다.따라서 앞서 계산한 부분 문제의 해를 기억하여 반복을 줄이는 동적 프로그래밍을 사용하면 될 것 같다.구현두 서로 다른 언어와.. [Baekjoon Online Judge] 11286. 절댓값 힙 (C++, Java) https://www.acmicpc.net/problem/11286설명 핵심대놓고 힙을 사용하라고 했기 때문에 따로 생각할 요소는 없다.힙은 라이브러리에 포함된 우선순위 큐를 사용하면 되고주어진 조건에 맞게 비교 함수를 구현하는 방법만 학습하면 된다.구현Code (Java)비교 함수를 람다로 구현했다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.PriorityQueue;public class Main { public static void main(String[] args) throws IOException { StringBuilder sb =.. 이전 1 2 3 4 다음
