ㅇㅅㅎ

[ 소수 ] 소수는 약수가 1과 자기 자신뿐인 자연수입니다. 모든 자연수는 소수의 곱으로 나타낼 수 있다는 규칙이 있습니다. 👀 가분성(divisibility) 어떤 수 x로 y를 나눌 수 있으려면 x를 소수의 곱으로 분할하였을 때 나열되는 모든 소수는 y를 소수의 곱으로 분할하였을 때 나열되는 모든 소수들의 부분집합이어야 합니다. 즉, x/y를 만족하려면 모든 i에 대해서 j_i 2){ return false; } int sqrt = (int) Math.sqrt(n); for(int i=2; i

[ 삽입 ] 2개의 32비트 수 N과 M이 주어지고, 비트 위치 i와 j가 주어졌을 때 M을 N에 삽입하는 알고리즘 ⭐ M은 N의 j번째 비트에서 시작하여 i번째 비트에서 끝납니다. 그리고 j번째 비트에서 i번째 비트까지는 충분한 공간이 있다고 가정합니다. 예시) 입력 : N=10000000000, M=10011, i=2, j=6 출력 : N=10001001100 def updateBits(n, m, i, j): allOnes = ~0 left = allOnes = 1 else '0' d -= 1 if d >= 1 else 0 return (bin(w).lstrip("0b") if w else '0') + res 👀 소수점 아래의 부분을 2진수로 만드는 법은 소수점 아래의 값에 2를 곱한 다음 그 값이 ..

[ 손으로 비트 조작해보기 ] 비트 조작에 익숙하지 않다면 손으로 다음의 연습문제들을 풀어보는 것이 좋습니다. 비트는 1과 0만을 가지는 2진수로 +, -와 *의 경우 똑같이 연산하시면 됩니다. 연산자 기능 + 더하기 연산 - 뺴기 연산 * 곱셈 연산 & 비교하는 두 비트가 1이면 1, 그 외의 모든 경우는 0인 연산 (AND) | 비교하는 두 비트가 0이면 0, 그 외의 모든 경우는 1인 연산 (OR) ^ 비교하는 비트 같으면 0 다르면 1인 연산 (XOR) ~ 모든 비트 반전하는 연산(NOT) >> 비트 열을 오른쪽으로 이동 연산 2 1101 ^ (~1101) 1000 - 0010 1011 ^ 0101 1101 & (~0 >연산과 같습니다. ⭐ Java Code int repeatedArithmeti..

[ 대부분의 문제에 사용한 Node 클래스 ] class Node: def __init__(self, name): self.name = name self.left = None self.right = None [ 노드 사이의 경로 ] 방향 그래프가 주어졌을 때 두 노드 사이에 경로가 존재하는지 확인하는 알고리즘 이 문제에서 사용할 Node와 Graph▼ 더보기 state = ("Unvisited", "Visited", "Visiting") class Node: def __init__(self, name): self.name = name self.state = state[0] self.adjacent = [] def setAdjacent(self, node): self.adjacent.append(node)..

[ 트리의 종류 ] 👀 트리 : 노드로 이루어진 자료구조입니다. 트리를 재귀적으로 설명하면 다음과 같습니다. 하나의 루트 노드를 갖습니다. → 사실 그래프 이론에서는 하나의 루트 노드를 가질 필요는 없습니다. 루트 노드는 0개 이상의 자식 노드를 갖고 있습니다. 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고 이는 반복적으로 정의됩니다. ⭐ Node class Node{ public String name; public Node[] childern; } ⭐ Tree class Tree{ public Node root; } 👀 이진트리(binary tree) : 각 노드가 최대 2개의 자식을 갖는 트리 👀 이진 탐색 트리(binary search tree) : 모든 노드가 다음과 같은 특정 순서를 따르는..

[ 한 개로 세 개 ] 배열 한 개로 스택 세 개 구현 class threeInone: def __init__(self): self.items = [] self.stackCnt = {1: 0, 2: 0, 3: 0} self.stackNumError = 'I have only 3 stacks' def pop(self, stackNum: int): idx = -1 if stackNum not in self.stackCnt.keys(): return self.stackNumError else: if self.stackCnt[stackNum] != 0: self.stackCnt[stackNum] -= 1 for i in range(1, stackNum+1): idx += self.stackCnt[i] else:..

[ 스택 구현하기 ] 👀 스택 : 제한적으로 접근할 수 있는 나열 구조로 LIFO(Last-In-First-Out)에 따라 자료를 배열합니다. 재귀 알고리즘을 사용할 때 유용하게 사용됩니다. ⭐ LIFO : 가장 최근에 추가한 항목이 가장 먼저 제거될 항목 ⭐ 재귀 알고리즘을 사용할 때 임시 데이터를 스택에 넣어놓고 재귀 함수 완료 후 스택에 넣어 두었던 임시 데이터를 빼는 형식으로 주로 사용됩니다. 👀 Java로 구현 public class MyStack{ private static class StackNode{ private T data; private StackNode next; public StackNode(T data){ this.data = data; } } private StackNode t..

[ 연결리스트] Python으로 노드와 연결리스트를 간단하게 구현했습니다. # 노드 class Node: def __init__(self, d): self.data = d self.next = None # 연결리스트 class LinkedList: def __init__(self, data): self.head = Node(data) def appendNode(self, data): now = self.head while now.next is not None: now = now.next now.next = Node(data) def appendNode2(self, node:Node): now = self.head while now.next is not None: now = now.next now.next..

👀 연결리스트 : 차례로 연결된 노드를 표현해주는 자료구조 장점 : 리스트의 시작 지점에서 아이템을 추가하거나 삭제하는 연산을 상수 시간에 할 수 있습니다. 단점 : 배열처럼 특정 인덱스를 상수 시간에 접근할 수 없습니다. [ 연결리스트 만들기 ] 아래의 코드에선 LinkedList 자료구조를 사용하지 않았습니다. 그리고 연결리스트에 접근할 때 head 노드의 주소를 참조하는 방법을 사용했기 때문에 여러 객체들이 동시에 연결리스트를 참조하는 도중에 head가 바뀌면 오류가 발생할 수 있습니다. ⭐ Java class Node { Node next = null; int data; public Node(int d){ data = d; } void appendToTail(int d){ Node end = ne..

[ 중복이 없는가 ] 문자열이 주어졌을 때 이 문자열에 같은 문자가 중복되어 등장하는지 확인하는 알고리즘 예시) hi ⇒ True, hello ⇒ False(l이 2개) def isUniqueChars(string): char_set = set() for s in string: if s in char_set: return False else: char_set.add(s) return True 👀 set을 사용한 이유는 특정 원소를 검색하는 연산이 O(1)의 시간 복잡도를 가지기 때문입니다. dictionary도 검색 연산이 O(1)이지만 굳이 키 값을 넣을 필요는 없기 때문에 사용하지 set으로 사용했습니다. [ 순열 확인 ] 문자열 두 개가 주어졌을 때 이 둘이 서로 순열 관계에 있는지 확인하는 알고리..