본문 바로가기

728x90

TIL51

[TIL] CSAPP 9장 공부2 - 동적 메모리 할당 1. 아침 문제 풀이 1. 1764번 - 듣보잡 import sys N, M = map(int, sys.stdin.readline().split()) dic = {} #듣도 못한 사람 저장 for _ in range(N) : dic[sys.stdin.readline().strip()] = 1 count = 0 result = [] for _ in range(M) : b = sys.stdin.readline().strip() #보도 못한 사람 if b in dic : # 딕셔너리에 키값으로 존재하면 #듣도보도 못한 사람이다. count += 1 result.append(b) print(count) result.sort() for i in range(count) : print(result[i]) 전에 풀었던.. 2023. 5. 12.

[TIL] CSAPP 9장 공부 - 가상 메모리 개념 정리 1. 아침 문제 풀이 1. 2563번 - 색종이 import sys n = int(sys.stdin.readline()) array = [list(map(int, sys.stdin.readline().split())) for _ in range(n)] canvas = [[0]*100 for _ in range(100)] result = 0 for i in range(n) : for j in range(array[i][0], array[i][0]+10) : for k in range(array[i][1], array[i][1]+10) : if canvas[j][k] == 0 : canvas[j][k] = 1 result += 1 print(result) 처음에는 색종이의 개수만큼의 넓이를 구한 다음 겹치는.. 2023. 5. 11.

[TIL] RB Tree 구현 (with C) 1. RB Tree 생성하기 RB Tree 구조체를 생성 - 여러 개의 RB Tree를 생성할 수 있어야 한다. sentinel node(경계노드) 사용 - 모든 nil 노드가 가리키는 노드 //RB Tree 구조체 생성 rbtree *new_rbtree(void) { rbtree *p = (rbtree *)calloc(1, sizeof(rbtree)); //현재 트리에서 NIL노드가 될 노드 생성 //각 트리마다 NIL노드는 1개씩 가지고 있다. node_t *NIL = (node_t *)calloc(1, sizeof(node_t)); NIL->color = RBTREE_BLACK; p->root = NIL; p->nil = NIL; return p; } 2. RB Tree 메모리 해제하기 RB Tre.. 2023. 5. 10.

[TIL] 기계 수준 표현3 + RB Tree 삽입 구현(코드X) 1. 기계 수준 표현 1. 유효 주소 적재(Load Effective Address) leaq S, D = D ← &S : 메모리에서 레지스터로 읽어들이는 인스트럭션의 형태를 갖지만, 메모리를 전혀 참조하지 않는다. 첫번째 오퍼랜드(S)의 유효 주소를 목적지(D)에 복사한다. 포인터를 생성하기 위해 사용 일반적인 산술 연산을 간결하게 설명하기 위해 사용 예시 ) x in %rdi, y in %rsi leaq (%rdi, %rsi, 4), %rdi //x = x + 4*y 2. 프로시저(Procedure) procedure call 은 소프웨어에서의 주요 추상화 : 지정된 인자들과 반환 값으로 특정 기능을 구현하는 코드를 감싸주는 방법 제공 무슨 값이 계산되고, 이 프로시저가 프로그램 상태에서 무슨 효과를.. 2023. 5. 8.

[TIL] Make란? + stack 문제 풀이 1. Make 소프트웨어 개발을 위해 유닉스 계열 운영 체제에서 주로 사용되는 프로그램 빌드 도구 여러 파일들끼리의 의존성과 각 파일에 필요한 명령을 정의함으로써 프로그램을 컴파일할 수 있으며 최종 프로그램을 만들 수 있는 과정을 서술할 수 있는 표준적인 문법을 가지고 있다. Makefile : make를 실행하기 전에 프로젝트의 목록 및 컴파일 및 링크 규칙 1. Makefile 이 필요한 이유 반복된는 컴파일 작업 시간이 오래 걸린다. 수정된 파일만 컴파일할 수 있다. 대규모 프로젝트나 공동 프로젝트에서 반드시 필요하다. 2. 컴파일 과정 소스 파일(*.c) : 우리가 작성한 코드 목적파일(*.o) : gcc compiler 를 이용하여 생성 → 기계어 생성 실행파일(*.out) : gcc compi.. 2023. 5. 7.

[TIL] Red-Black Tree 개념(삽입/삭제) + 기계 수준 표현(스택)2 1. 문제 풀이 1. 1874번 - 스택 수열 import sys n = int(sys.stdin.readline()) stack = [] result = '' idx = 1 flag = True for i in range(n) : num = int(sys.stdin.readline()) for j in range(idx, num+1): stack.append(j) result += '+\n' idx += 1 if num == stack[-1] : stack.pop() result += '-\n' else : flag = False break if flag : print(result) else : print('NO') 스택 문제 풀이 풀이 1. 현재 입력 받은 수보다 작으면 그 수까지 +, stack에 .. 2023. 5. 6.

[TIL] LinkedList & AVL Tree (with C) 1. 연결리스트(Linked List) 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료구조 종류 단일 연결 리스트 각 노드에 data 공간과 한개의 포인터 공간 존재 포인터는 다음 노드를 가리킨다. 이중 연결 리스트 단일 연결 리스트와 비슷하지만 두개의 포인터 공간 존재 포인터는 현재 노드의 앞의 노드와 뒤의 노드를 가리킨다. 원형 연결 리스트 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조 ★ 단일 연결리스트 구현해보기(C언어) ★ 1. header file - linkedlist_node.h #pragma once // 연결 리스트 노드 typedef struct node { int data; // 값 저장 struct node.. 2023. 5. 5.

[TIL] C언어 공부하기 1. 코드 refactoring 1. 12891번 - DNA 비밀번호 import sys s, p = map(int, sys.stdin.readline().split()) dna = list(sys.stdin.readline().strip()) # A, C, G, T esssential = list(map(int, sys.stdin.readline().split())) def remove(st) : global a, c, g, t if dna[st] == 'A' : a -= 1 elif dna[st] == 'C' : c -= 1 elif dna[st] == 'G' : g -= 1 elif dna[st] == 'T' : t -= 1 return 0 def add(e) : global a, c, g, t i.. 2023. 5. 4.

[TIL] 문제 풀이 연습 - two point (with python) 1. 문제 풀이 연습 1. 2018번 - 수들의 합 import sys N = int(sys.stdin.readline()) start = 1 # 현재 더한 값 중 첫번째 값 end = 1 # 현재 더한 값 중 마지막 값 count = 1 # 자기 자신 포함 sum = 1 # 총 더한 값 # 최소 2개의 연속된 자연수의 합이어야 하므로 # start는 N의 절반보다 클 수 없다. while start != N // 2 + 1 : if sum < N : # 아직 누적합이 N보다 작을 경우 end += 1 sum += end elif sum == N : # N과 같을 경우 count += 1 sum -= start start += 1 else : # N보다 클 경우 sum -= start start += 1.. 2023. 5. 3.

[TIL] 동적 프로그래밍 문제 풀이3 1. 문제 풀이 연습 1. 11660번 - 구간 합 구하기 5 import sys N, M = map(int, sys.stdin.readline().split()) table = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] # 누적합을 저장할 이차원 배열 dp = [[0] * (N+1) for _ in range(N+1)] for i in range(1, N+1) : for j in range(1, N+1) : dp[i][j] = table[i-1][j-1] + dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] # 원하는 구간합 구하기 for _ in range(M) : x1,y1,x2,y2 = map(int, s.. 2023. 5. 2.

[TIL] 그리디 문제 풀이 + 기계 수준 표현1 1. 그리디 문제 풀이 1. 1931번 - 회의실 배정 import sys N = int(sys.stdin.readline()) # meeting[0] : 시작 시간 / meeting[1] : 끝나는 시간 meeting = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] meeting.sort(key= lambda x : (x[1], x[0])) count = 1 prev = meeting[0][1] # 앞 회의 끝나는 시간 for i in range(1, N) : # 만약 현재 회의 시작 시간이 앞 회의 시간보다 크거나 같으면 if prev people[i][1] : count += 1 interview = people[i][1] pr.. 2023. 5. 1.

[TIL] Algorithm - Greedy 기본 문제 풀이 1. 그리디 알고리즘 (탐욕 알고리즘) 항상 각 단계에 있어서 가장 좋을 거라 생각되는 선택을 한다. 이 선택이 전체적으로 최적해로 안내하게 될 거라는 바람을 가지고 부분적으로 최적인 선택을 한다. 언제나 최적의 해답을 구하지는 못하지만 많은 문제에 대한 해를 구해줄 수 있다. 1. 11047번 - 동전 0 import sys N, K = map(int, sys.stdin.readline().split()) # 오름차순으로 입력을 받는다. coin = [int(sys.stdin.readline()) for _ in range(N)] count = 0 # 동전의 가치가 가장 큰 동전부터 반복 시작 for i in range(N-1, -1, -1) : if K == 0 : break # 현재 K보다 작은 수.. 2023. 4. 30.

[TIL] 동적 프로그래밍 문제 풀이2 1. 11049번 - 행렬 곱셈 순서 1. 최적 괄호 묶기의 구조 : n개의 행렬을 어떻게 곱할지 애매함을 없애기 위해 괄호로 묶는다. ex) ((A1, A2), A3) or (A1, (A2, A3)) 이 문제는 n개의 행렬들의 체인 이 주어졌을 때 A1, A2, ... , An의 스칼라 곱의 개수를 최소화 하도록 괄호를 묶어라! 라고 하는 것과 같다. AiAi+1...Aj를 괄호호 최적으로 묶기 위해 Ak Ak+1의 사이에서 나눈다고 가정 AiAi+1...Ak Ak+1Ak+2...Aj 위의 두 부분문제는 각각 최적 괄호 묶는 방법이 되어야 한다. 2. 재귀해 i == j 일 경우 0 i < j 일 경우 → k, k+1로 나눈다. Ai = pi-1 * pi 라면 Ai..kAk+1..j = pi-1 *pk.. 2023. 4. 29.

[TIL] 동적 프로그래밍 문제 풀이 1. DP 문제 풀이 1. 9084번 - 동전 import sys T = int(sys.stdin.readline()) for _ in range(T) : N = int(sys.stdin.readline()) coin = list(map(int, sys.stdin.readline().split())) M = int(sys.stdin.readline()) dp = [0] * (M+1) # 각각의 금액에 대한 동전으로 만들 모든 방법의 수 저장 dp[0] = 1 # 기저 값으로 지정 for c in coin : for i in range(1, M+1) : if i >= c : dp[i] += dp[i-c] print(dp[M]) 간단하게 생각하면 간단하다고 할 수 있지만 저 방식을 생각해내는 것 자체가 힘들.. 2023. 4. 28.

[TIL] Algorithm - 동적 프로그래밍 기본 1. 그래프 문제 풀이 1. 1388번 - 바닥 장식 import sys N, M = map(int, sys.stdin.readline().split()) graph = [list(sys.stdin.readline().strip()) for _ in range(N)] visited = [[0] * M for _ in range(N)] # 같은 행에 존재하는지 확인해야하므로 열 번호 증가 def col(x, y) : visited[x][y] = 1 stack = [(x, y)] while stack : curx, cury = stack.pop() for i in range(1, M) : ny = cury + i if ny < M and graph[curx][ny] == '-' and visited[curx.. 2023. 4. 27.

[TIL] 위상 정렬 문제 풀이 + Computer System2 1. 위상 정렬 문제 풀이 1. 2637번 - 장난감 조립 import sys from collections import deque N = int(sys.stdin.readline()) M = int(sys.stdin.readline()) basic = [[] for _ in range(N)] inDegree = [0] * N for _ in range(M) : x, y, k = map(int, sys.stdin.readline().split()) basic[y-1].append((x-1, k)) inDegree[x-1] += 1 def topologicalsort() : # component[x][y] -> x를 만드는데 필요한 y의 개수 component = [[0] * N for _ in range.. 2023. 4. 26.

[TIL] Algorithm - 위상 정렬 + 플로이드-워셜 1. 그래프 문제 풀이 1. 2573번 - 빙산 ▶ BFS를 이용한 풀이 import sys from collections import deque N, M = map(int, sys.stdin.readline().split()) iceberg = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] # 빙산 녹이는 함수 def melting() : change = [] for i in range(1, N-1) : for j in range(1, M-1) : if iceberg[i][j] != 0 : sea = 0 # 현재 위치에서 0과 맞닿아 있는 개수 for k in ran.. 2023. 4. 25.

[TIL] Algorithm - 다익스트라 + 그래프 문제 풀이(BFS) 1. 다익스트라 알고리즘(Dijkstra algorithm) 모든 간선에 대한 가중치가 항상 0이상임을 가정하고 두 꼭짓점 간의 가장 짧을 경로를 찾는 알고리즘 간선 완화(Edge Relaxation) 시작 정점 s에서 다른 정점 v까지의 초기 거리 값을 부여하고 단계를 거듭하여 개선시키는 것 간선 (u, v)를 완화하는 과정 u를 통해 v까지 가는 지금까지 발견된 최단 경로를 개선할 수 있는지 검사 개선할 수 있다면, v의 최단 경로 추정값을 갱신한다. 시간복잡도 O(|E| + |V|log|V|) https://ko.wikipedia.org/wiki/데이크스트라_알고리즘 1. 다익스트라를 이용한 문제 풀이 1. 1916번 - 최소비용 구하기 import sys import heapq N =.. 2023. 4. 24.

이전 1 2 3 다음

728x90

티스토리툴바