본문 바로가기

728x90

전체 글148

[BOJ] 15657번 - N과M(8) (Python) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 백트래킹 연습하기 편한 문제라고 생각한다. 오늘 풀면서 틀렸던 이유에 대해 간단하게 남겨놓으려고 한다. 내가 잘못 생각했던 부분은 타입을 생각하지 않고 정렬한 것이다. 처음에는 결과를 쉽게 저장하기 위해 문자형 그대로 사용하여 주어진 예제는 전부 통과해 제출했지만 틀렸다. 다른 동작의 오류가 있나 고민해보았지만 없었고 다른 사람의 풀이를 참고해봐도 동작은 완벽했다. 단 하나 다른 점이 입력받은 데이터 타입이었는데 생각해보니 [입력으로 주어지는 수는 10,000보다 작거나 같은 자연수]이므로 이는 정수로 정렬해야 올바르게 정렬된다는 것을 깨달았다. 🍀 풀이 🍀 import sys n, m = map(int, sys.stdin.readline().split()) nums = .. 2023. 10. 5.

[BOJ] 1911번 - 흙길 보수하기 (Python) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 이 문제는 [물웅덩이들을 모두 덮으려고 한다.] 라는 조건이 있으므로 물웅덩이가 보이면 일단 덮으면 된다. 그러나 널빤지의 길이는 정해져 있으므로 덮다보면 입력받은 물웅덩이의 위치가 이미 덮여져 있을 수 있다. 어차피 모든 웅덩이는 덮어야하니 웅덩이의 [끝 위치 - 시작 위치]를 통해 웅덩이의 길이를 구하여 필요한 널빤지의 개수를 구했다. 단, 위에서 설명했듯이 이미 덮여져 있는 위치가 존재할 수 있으므로 이에 대한 처리로 current라는 변수를 두어 시작 위치를 덮여져 있지 않은 위치로 변경할 수 있도록 했다. 🍀 풀이 🍀 import sys n, l = map(int, sys.stdin.readline().split()) water = [list(map(int, sy.. 2023. 9. 7.

[BOJ] 13549번 - 숨바꼭질3 (Python) 🛠️ 문제 🛠️ 🗒️ 설명 🗒️ 어제 공부한 다익스트라 알고리즘을 연습해보았다. 다익스트라 알고리즘과 BFS 2가지 방식으로 풀어보았다. (코드는 아래에) 1. 다익스트라 알고리즘을 이용한 풀이 1. 수빈이의 위치를 시작 정점으로 둔다. 2. 현재 위치 i에 +1, -1 *2 한 위치에 대해 저장되어 있는 시간 times[k]와 도달한 시간(times[i] + 1 또는 times[i])을 비교하여 도달한 시간이 더 작으면 times[k]를 갱신한다. 3. heap이 빌 때까지 2번 과정을 반복한다. 이때, 주의할 점은 가중치가 없지만 가중치로 생각한 값은 도달한 시간으로 times의 값이다. 만약 이를 times를 도착 정점의 개수만큼만 만들면 올바른 값을 도출하지 못할 것이다. 위의 문제에서 주어진 예.. 2023. 9. 5.

[BOJ] 1753번 - 최단경로(Python) + Dijkstra Algorithm 🗒️ 다익스트라 알고리즘 (Dijkstra Algorithm) 모서리 또는 정점에 가중치가 부여된 그래프에서 두 정점 사이의 최단 경로를 찾는 알고리즘 가중치가 없는 그래프에서의 최단경로는 BFS를 사용! 어떤 시작점 s가 주어졌을 때, 그 정점에서 시작하여 다른 모든 정점으로 가는 최단 경로를 찾는다. 단, 음수인 가중치가 없는 경우에만 쓸 수 있다. 실제 최단 경로는 우리집에서 옆집으로 이동하는 것이지만, 우리집에서 은행을 거쳐 가는 것이 비용상 이득이 되는 경우가 발생한다. 즉, 값이 음수인 모서리가 있으면 경로를 만들어가는 도중에 아주 작은 음수 값을 가지는 모서리가 있어서 이미 트리에 들어있는 최단 경로와 전혀 다른 경로를 만들어야 할 수 있다. 동작 과정(간선 완화 과정) 1. 모든 꼭짓점을 .. 2023. 9. 4.

[NestJS] MongoDB와 연결하기 ※ 기록용 ※ 1. mongoose 설치 npm install --save @nestjs/mongoose mongoose 2. app.module.ts : nestjs 애플리케이션에서 MongoDB와의 연결을 설정 import { Module } from '@nestjs/common'; import { AppController } from './app.controller'; import { AppService } from './app.service'; import { MongooseModule } from '@nestjs/mongoose'; //mongoDB 연결 import { VideoModule } from './video/video.module'; @Module({ imports: [Mongoos.. 2023. 7. 12.

[TIL] Pintos Project1 - Threads 정리 ※ git book 기준으로 이해한 내용 정리 ※ 0. 개념 및 코드 정리 1. thread CPU 이용의 기본 단위, 동일 프로세스의 스레드들은 코드 영역, 데이터 영역, 운영체제 자원들을 공유 핀토스에서는 단일 스레드 프로세스(Single thread process)를 구현! 그러므로 프로세스의 상태변화가 스레드의 상태변화와 동일하다고 생각하고 구현함 이러한 멀티 프로그래밍의 목적은 CPU 사용률을 최대화하기 위함이며, 어떤 프로세스든 항상 실행 중이게 한다. time sharing(시분할 시스템) : 여러 프로세스 사이에서 CPU를 자주 전환함으로써 여러 사용자 프로그램이 수행되는 동안 각 프로그램과 상호작용할 수 있도록 한다. Process scheduler : CPU에서 프로그램 실행을 위해 실.. 2023. 6. 28.

[WIL] Pintos 4주차 - VM(2) (주간공유) 1. 일정 ✅ 06.19 ~ 06.20 Git book 기준 lazy loading 구현 완료 Git book 기준 stack growth 구현 완료 ✅ 06.21 ~ 06.23 Git book 기준 Memory mapping 구현 완료 ✅ 06.24 ~ 06.25 Git book 기준 Swap In/Out 구현 완료 2. 주요 학습 1. Stack growth 사용 이유 프로세스가 실행 중인 동안에 함수 호출 깊이가 깊어지거나 큰 지역 변수 등으로 인해 스택의 공간이 부족해질 수 있다. 이 때 필요한 만큼 스택 영역을 '성장'시키는 메커니즘이 필요합니다. 이를 "스택 성장(stack growth)"이라고 합니다. 2. Pintos 에서 구현된 방식 1. 초기 스택 상태 static bool setup_.. 2023. 6. 25.

[WIL] Pintos 3주차 - VM(1) (주간공유) 1. 일정 ✅ 06.12 ~ 06.15 가상 메모리 개념 공부 git book 읽기 및 강의 학습 운영체제 책 읽기 ✅ 06.16 Git book 기준 Memory Management 구현 ✅ 06.17 ~ 06.18 Git book 기준 Anonymous Page 구현 2. 진행 상황 1. SPT 구조 pml4가 페이지 테이블을 의미한다는 것을 알게 되었습니다. git book 기준으로 Memory Management 구현 완료 2. Anonymous Page 구현은 해본 상태 Project 2 - userprog (....All fail....) 123 of 141 tests failed 2023. 6. 18.

[TIL] Pintos - 가상 메모리 관련 개념 공부2 1. 아침 문제 풀이 1. 10026번 - 적록색약 import sys from collections import deque N = int(sys.stdin.readline()) pic = [list(sys.stdin.readline().strip()) for _ in range(N)] dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def bfs(x, y) : queue = deque() queue.append((x, y)) visited[x][y] = True while queue : cx, cy = queue.popleft() for i in range(4) : nx, ny = cx + dx[i], cy + dy[i] if nx >= 0 and nx = 0 .. 2023. 6. 15.

[TIL] Pintos - 가상 메모리 관련 개념 공부1 1. 아침 문제 풀이 1. 2023번 - 신기한 소수 import sys N = int(sys.stdin.readline()) result = [] #소수인지 판별하는 함수 def isPrime(n) : for i in range(2, int(n**(1/2))+1) : if n % i == 0 : return False return True #백트래킹 방식을 사용한 탐색 def dfs(depth, n) : if depth == N : if isPrime(n) : result.append(n) return for i in range(10) : nn = n*10 + i if isPrime(nn) : dfs(depth+1, n*10+i) prime = [2, 3, 5, 7] for p in prime : df.. 2023. 6. 14.

[WIL] Pintos 2주차 - Userprog (주간공유) 1. 일정 계획 ✅ 06.01 대략적인 일정 조율 개인 이론 공부 ✅ 06.02 gitbook 및 강의 학습 ✅ 06.03 ~ 06.05 passing argument 구현 ✅ 06.06 ~ 06.11 system call 구현 2. 주요 학습 user mode vs kernel mode 1. user mode User 모드에서는 제한된 시스템 자원에만 접근 가능 파일 시스템, 네트워크 연결, 입출력 장치등과 같은 일반적인 작업을 수행할 수 있지만, 직접적으로 시스템 리소스에 접근하거나 시스템 제어 명령을 실행할 수 없다. 2. kernel mode 유저 모드에서 요청 → syscall_entry를 통해 어셈블리어로 진입 → rsp = 커널 스택 포인터 syscall_handler : 시스템 호출의 요구.. 2023. 6. 12.

[TIL] 1377번 - 버블 정렬 1. 1377번 - 버블 정렬 import sys N = int(sys.stdin.readline()) array = [[int(sys.stdin.readline()), i] for i in range(N)] array.sort() max = -sys.maxsize for i in range(N) : t = array[i][1] - i if max < t : max = t print(max+1) 이 문제는 버블 정렬시 완료되는 반복 횟수를 구하는 문제이다. 주어진 c++ 코드로도 답은 구할 수 있지만 시간초과가 발생했다. 즉, 이중 반복문을 제거할 수 있어야 한다. 위의 그림은 버블 정렬 과정을 써본 것이다. 버블 정렬은 맨 뒤에서 부터 큰 값이 먼저 정렬된다. 그러므로 정렬되지 않은 값 중 가장 큰 값.. 2023. 6. 7.

[TIL] OS - System Call 1. 운영체제 서비스(Operating System Service) 사용자에게 도움을 주기 위한 기능 사용자 인터페이스(User Interface) GUI(그래픽 사용자 인터페이스) CLI(명령어 라인 인터페이스) Batch Interface(일괄처리 인터페이스) https://ko.wikipedia.org/wiki/사용자_인터페이스 프로그램 수행(Program Execution) 프로그램을 메모리에 적재(load)해 구동(Run)하고 실행(Execute)할 수 있어야 한다. 정상적이든 비정상적이든 실행을 끝낼 수 있어야 한다. 입출력 연산(I/O Operation) 수행 중인 프로그램은 입출력을 요구할 수 있다. 효율과 보호를 위해 사용자들이 직접 제어를 할 수 없으므로 운영체제가 수단 제공 통신(Co.. 2023. 6. 7.

[WIL] Pintos 1주차 - Threads (주간공유) 1. 일정 계획 ✅ 05.25 개인 노트북에 우분투 환경 설정 대략적인 일정 조율 개인 이론 공부 ✅ 05.26 git book 읽기 os (thread, processor 등) 관련 개념 공부 및 공유 ✅ 05.27 Alarm 구현 1일차 thread.c timer.c 코드 분석 ✅ 05.28 Alarm 구현 2일차 ✅ 05.29 Priority 구현 1일차 synch.c 코드 분석 ✅ 05.30 Priority 구현 2일차 ✅ 05.31 Priority 구현 3일차 2. 주요 학습 synch.c - lock_acquire() : donation list 저장방식의 차이 1. donate 가능한 모든 후보자들 저장 void lock_acquire (struct lock *lock) { ASSERT (l.. 2023. 6. 1.

[TIL] OS 용어 정리 1. 아침 문제 풀이 1. 1049번 - 기타줄 import sys N, M = map(int, sys.stdin.readline().split()) min_six = sys.maxsize min_one = sys.maxsize # 가장 작은 가격 구하기 for _ in range(M) : six, one = map(int, sys.stdin.readline().split()) if min_six > six : min_six = six if min_one > one : min_one = one count = N // 6 + 1 #6의 배수가 되도록하면서 적어도 N보다 큰 몫 구하기 a = min_six * count # 묶음으로만 구매할 경우 b = min_one * N #낱개로만 구매할 경우 c = m.. 2023. 5. 26.

[TIL] Thread 개념 정리 1. 아침 문제 풀이 1. 26069번 - 붙임성 좋은 총총이 import sys N = int(sys.stdin.readline()) dance = {'ChongChong' : 1} for _ in range(N) : a, b = sys.stdin.readline().split() # 두 사람 중 한 사람만 춤을 추고 있는 경우를 나눠 dance 목록에 저장 if a in dance and b not in dance: dance[b] = 1 elif a not in dance and b in dance : dance[a] = 1 print(len(dance)) 가볍게 Dictionary를 이용해 푼 문제 2. Thread 어떠한 프로그램 내에서, 특히 프로세스 내에서 실행되는 흐름의 단위 프로세스의 c.. 2023. 5. 25.

[TIL] 7주차 - 넘겼던 부분 동료학습 정리 1. 아침 문제 풀이 1. 2559번 - 수열 - 2023.05.24 import sys N, K = map(int, sys.stdin.readline().split()) nums = list(map(int, sys.stdin.readline().split())) result = sum(nums[:K]) # 구해야할 값 curr = result # 현재 0부터 K-1까지 연속된 값의 합 for i in range(K, N) : curr = curr - nums[i-K] + nums[i] # 맨앞의 값은 빼고 뒤에 값 추가(슬라이딩 윈도우) if curr > result : result = curr print(result) 전에 공부했던 슬라이딩 윈도우를 사용하여 푼 문제 요즘 점점 풀수록 어떤 알고리즘을.. 2023. 5. 24.

[TIL] Proxy 개념 정리 1. 아침 문제 풀이 1. 2108번 - 통계학 import sys import math N = int(sys.stdin.readline().strip()) nums = {} # 입력받은 수들의 등장 횟수 lst = [0] * N # 입력받은 수들 sum = 0 for i in range(N) : num = int(sys.stdin.readline().strip()) if num in nums : nums[num] += 1 else : nums[num] = 1 lst[i] = num sum += num lst.sort() nums = dict(sorted(nums.items())) nums = sorted(nums.items(), key= lambda x : -x[1]) print(round(sum/N).. 2023. 5. 24.

이전 1 2 3 4 5 6 7 ··· 9 다음

728x90

티스토리툴바