Tech for good

알고리즘:주어진 문자열을 파싱하여 문자 -> 빈도 형태로 해시맵에 저장해시맵의 키(문자)를 알파벳 순으로 정렬최종 결과 문자열을 생성from collections import defaultdictclass Solution: def betterCompression(self, compressed: str) -> str: freq_map = defaultdict(int) i = 0 n = len(compressed) # 문자열을 순회하면서 문자와 숫자 파싱 while i  🔹 시간 복잡도:문자열을 한 번 순회하면서 파싱 (O(N))해시맵을 정렬 (O(K log K), K는 문자 종류의 개수, 최대 26)결과 생성 (O(K))총..

이 문제를 한 번의 순회(One-pass)로 해결하는 방법은 두 개의 포인터(first, second)를 사용하는 것이다.first 포인터를 먼저 n칸 이동시킨 후, second 포인터를 first와 함께 이동하면 first가 끝에 도달했을 때 second는 삭제할 노드의 직전 노드를 가리키게 된다.✅ 알고리즘 풀이 (Two Pointer)더미 노드 추가: 삭제할 노드가 head일 수도 있으므로 더미 노드를 추가.first 포인터 선행 이동: first를 n칸 먼저 이동.두 포인터 이동: first가 리스트의 끝에 도달할 때까지 second와 함께 이동.노드 삭제: second.next를 second.next.next로 변경하여 노드 삭제.새로운 head 반환: dummy.next를 반환.# Defini..

해시셋(Hash Set) 활용 -중복을 방지하면서 각 노드를 탐색할 때 (k - 현재 노드 값)이 존재하는지 확인하는 방법. 설명dfs 함수를 사용하여 트리를 깊이 우선 탐색(DFS) 한다.각 노드를 방문할 때 k - node.val이 seen 집합에 존재하는지 확인한다.존재하면 True를 반환하고, 없으면 현재 노드 값을 seen에 추가한 후 왼쪽과 오른쪽 서브트리를 탐색한다.전체 탐색이 끝날 때까지 조건을 만족하는 쌍이 없으면 False를 반환한다.시간 복잡도각 노드를 한 번씩 방문하므로 O(N) (N은 트리의 노드 개수).공간 복잡도최악의 경우 모든 노드 값을 seen에 저장해야 하므로 O(N). # Definition for a binary tree node.class TreeNode: de..

Two Pointer 방식으로 해결하는 방법Two Pointer 방식을 사용하려면, BST(Binary Search Tree)의 중위 순회(in-order traversal)를 수행하여 오름차순으로 정렬된 리스트를 만든 후, 투 포인터를 사용하여 두 숫자의 합이 k가 되는지 확인하면 된다.Two Pointer 알고리즘BST를 중위 순회하여 정렬된 리스트를 생성중위 순회(In-order Traversal)를 수행하면 BST의 값이 오름차순으로 정렬됨.Two Pointer 기법을 활용하여 합이 k가 되는 두 수 찾기리스트의 left(처음)과 right(끝) 포인터를 설정.두 값의 합이 k보다 작으면 left를 증가.두 값의 합이 k보다 크면 right를 감소.두 값의 합이 k이면 True 반환.# Defin..

6085 : [기초-종합] 그림 파일 저장용량 계산하기이미지가 컴퓨터에 저장될 때에도 디지털 데이터화 되어 저장된다.가장 기본적인 방법으로는 그림을 구성하는 한 점(pixel, 픽셀)의 색상을빨강(r), 초록(g), 파랑(b)의 3가지의 빛의 세기 값으로 따로 변환하여 저장하는 것인데,예를 들어 r, g, b 각 색에 대해서 8비트(0~255, 256가지 가능)씩을 사용한다고 하면,한 점의 색상은 3가지 r, g, b의 8비트+8비트+8비트로 총 24비트로 표현해서총 2^24 가지의 서로 다른 빛의 색깔을 사용할 수 있는 것이다.그렇게 저장하는 점을 모아 하나의 큰 이미지를 저장할 수 있게 되는데,1024 * 768 사이즈에 각 점에 대해 24비트로 저장하면 그 이미지를 저장하기 위한저장 용량을 계산할 ..

6077 : [기초-종합] 짝수 합 구하기 정수(1 ~ 100) 1개를 입력받아 1부터 그 수까지 짝수의 합을 구해보자. 예시 #다음 코드는 홀 수만 더해 출력한다. n = int(input()) s = 0 for i in range(1, n+1) : if i%2==1 : s += i print(s) 참고 while 이나 for 반복실행구조를 이용할 수 있다. 다른 방법이나 while 반복실행구조를 이용해서도 성공시켜 보자. 입력 정수 1개가 입력된다. (0 ~ 100) 출력 1부터 그 수까지 짝수만 합해 출력한다. 입력 예시 5 출력 예시 6 n = int(input()) s = 0 for i in range(1, n+1): if i%2==0: s +=i print(s) 6078 : [기초-종합] 원하..

while문의 기본 구조 반복해서 문장을 수행해야 할 경우 while문을 사용한다. 그래서 while문을 반복문이라고도 부른다. 다음은 while문의 기본 구조이다. while : ... while문은 조건문이 참인 동안에 while문 아래의 문장이 반복해서 수행된다. https://wikidocs.net/21 03-2 while문 [TOC] ## while문의 기본 구조 반복해서 문장을 수행해야 할 경우 while문을 사용한다. 그래서 while문을 반복문이라고도 부른다. 다음은 while문의 ... wikidocs.net 6071 : [기초-반복실행구조] 0 입력될 때까지 무한 출력하기 임의의 정수가 줄을 바꿔 계속 입력된다. -2147483648 ~ +2147483647, 단 개수는 알 수 없다. ..

6065 : [기초-조건/선택실행구조] 정수 3개 입력받아 짝수만 출력하기 3개의 정수(a, b, c)가 입력되었을 때, 짝수만 출력해보자. 예시 a, b, c = input().split() a = int(a) b = int(b) c = int(c) if a%2==0 : #논리적으로 한 단위로 처리해야하는 경우 콜론(:)을 찍고, 들여쓰기로 작성 한다. print(a) if b%2==0 : print(b) if c%2==0 : print(c) 참고 if 조건식 : 실행1 #조건식의 평가값이 True 인 경우 실행시킬 명령을 들여쓰기를 이용해 순서대로 작성한다. 실행2 실행3 #들여쓰기를 하지 않은 부분은 조건식에 상관이 없음 python 에서는 논리적 실행단위인 코드블록(code block)을 표현하기..

6059 : [기초-비트단위논리연산] 비트단위로 NOT 하여 출력하기 입력 된 정수를 비트단위로 참/거짓을 바꾼 후 정수로 출력해보자. 비트단위(bitwise)연산자 ~ 를 붙이면 된다.(~ : tilde, 틸드라고 읽는다.) ** 비트단위(bitwise) 연산자는 ~(bitwise not), &(bitwise and), |(bitwise or), ^(bitwise xor), (bitwise right shift)가 있다. 예를 들어 1이 입력되었을 때 저장되는 1을 32비트 2진수로 표현하면 00000000 00000000 00000000 00000001 이고, ~1은 11111111 11111111 11111111 11111110 가 되는데 이는 -2를 의미한다. 예시 a = 1 print(~a) #..

6046 : [기초-비트시프트연산] 정수 1개 입력받아 2배 곱해 출력하기 정수 1개를 입력받아 2배 곱해 출력해보자. 참고 *2 를 계산한 값을 출력해도 되지만, 정수를 2배로 곱하거나 나누어 계산해 주는 비트단위시프트연산자 를 이용할 수 있다. 컴퓨터 내부에는 2진수 형태로 값들이 저장되기 때문에, 2진수 형태로 저장되어 있는 값들을 왼쪽()으로 지정한 비트 수만큼 밀어주면 2배씩 늘어나거나 1/2로 줄어드는데, 왼쪽 비트시프트()가 될 때에는 왼쪽에 0(0 또는 양의 정수인 경우)이나 1(음의 정수인 경우)이 개수만큼 추가되고, 가장 오른쪽에 있는 1비트는 사라진다. 예시 n = 10 print(n1) #10을 반으로 나눈 값인 5 가 출력된다. print(n2) #10을 반으로 나눈 후 다시 반으..