Number of 1 Bits (비트 1의 개수 세기)
문제 설명:
양의 정수 n이 주어졌을 때,
이 숫자의 이진수 표현에서 1로 설정된 비트(set bit)의 개수, 즉 해밍 무게(Hamming weight) 를 반환하는 함수를 작성하세요.
예제:
예시 1
•
입력: n = 11
•
이진수: 1011
•
출력: 3
•
설명: 1이 세 번 등장하므로 결과는 3.
예시 2
•
입력: n = 128
•
이진수: 10000000
•
출력: 1
예시 3
•
입력: n = 2147483645
•
이진수: 1111111111111111111111111111101
•
출력: 30
제약 조건:
•
1 <= n <= 2³¹ - 1
Hamming Distance (해밍 거리)
문제 설명:
•
*해밍 거리(Hamming Distance)**란, 두 정수의 이진수 표현에서 각 자리(bit)마다 서로 다른 위치의 수를 세는 것입니다.
즉, 같은 자리의 비트가 다르면 1씩 카운트합니다.
입력:
두 개의 정수 x와 y가 주어질 때,
이 두 수의 해밍 거리를 반환하세요.
예시:
예제 1:
•
입력: x = 1, y = 4
•
이진수:
1 → 0001
4 → 0100
↑ ↑
Plain Text
복사
•
출력: 2 (서로 다른 비트가 2개)
예제 2:
•
입력: x = 3, y = 1
•
이진수:
3 → 0011
1 → 0001
↑
Plain Text
복사
•
출력: 1 (서로 다른 비트가 1개)
제약 조건:
•
0 <= x, y <= 2^31 - 1 (32비트 정수 범위)
Reverse Bits (비트 뒤집기)
문제 설명:
32비트의 부호 없는 정수 n 이 주어졌을 때,
이 수의 비트 순서를 반대로 뒤집은 값을 반환하세요.
예를 들어:
•
n = 00000010100101000001111010011100 (이진수) →
반대로: 00111001011110000010100101000000
→ 결과: 964176192
주의사항:
•
Java처럼 부호 없는 타입이 없는 언어도 있지만,
내부적으로 2진수 표현은 동일하기 때문에 상관없습니다.
•
문제는 항상 32비트 정수라고 보장합니다.
예제:
예제 1:
입력: 00000010100101000001111010011100
출력: 00111001011110000010100101000000 (964176192)
Plain Text
복사
예제 2:
입력: 11111111111111111111111111111101
출력: 10111111111111111111111111111111 (3221225471)
Plain Text
복사
Pascal's Triangle (파스칼의 삼각형)
문제 설명:
정수 numRows가 주어졌을 때,
파스칼의 삼각형의 처음 numRows 행을 2차원 배열 형태로 반환하세요.
파스칼 삼각형이란?
삼각형의 각 숫자는 자신의 바로 윗줄에서 왼쪽과 오른쪽 값의 합입니다.
•
맨 양쪽은 항상 1
•
중간은 윗줄의 i-1번째 + i번째
입력 / 출력 예시:
예제 1:
입력: numRows = 5
출력: [[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]]
Plain Text
복사
예제 2:
입력: numRows = 1
출력: [[1]]
Plain Text
복사
제약 조건:
•
1 <= numRows <= 30
Valid Parentheses (유효한 괄호)
문제 설명:
문자열 s가 주어질 때,
문자열이 유효한 괄호 문자열인지 여부를 판별하시오.
s는 오직 '(', ')', '{', '}', '[', ']' 로만 구성되어 있습니다.
유효한 괄호의 조건:
1.
열린 괄호는 반드시 같은 종류의 닫힌 괄호로 닫혀야 한다.
2.
괄호는 올바른 순서로 닫혀야 한다.
3.
닫는 괄호마다 짝이 되는 여는 괄호가 반드시 있어야 한다.
예시:
Input: s = "()"
Output: true
Input: s = "()[]{}"
Output: true
Input: s = "(]"
Output: false
Input: s = "([])"
Output: true
Plain Text
복사
시간 및 공간 복잡도:
•
시간 복잡도: O(n)
•
공간 복잡도: O(n) (스택 사용)
Missing Number (빠진 숫자 찾기)
문제 설명:
0부터 n까지의 숫자 중 하나만 빠진 배열 nums가 주어집니다.
이 배열에서 빠진 숫자를 찾아 반환하세요.
•
nums.length == n
•
배열의 모든 값은 고유(unique) 합니다.
•
모든 값은 범위 [0, n]에 포함됩니다.
Tip : 등차수열의 합을 이용
int expectedSum = n * (n + 1) / 2;
등차수열의 합 공식 증명 ( 한번 읽어보기 )
예시:
Input: nums = [3,0,1]
Output: 2
Input: nums = [0,1]
Output: 2
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Plain Text
복사
