본문 바로가기

전체 글215

백준 1647: 도시 분할 계획(python) 문제풀이 MST를 구하고, MST 중 가중치가 가장 큰 간선을 절단해 마을을 2개로 분리하면 된다.MST를 구하기 위해 Kruskal 알고리즘과 Prim 알고리즘을 사용할 수 있는데, 2가지 방법으로 모두 구현해 보았다.1. Kruskal 알고리즘N, M = map(int, input().split())edges = [] #간선 리스트에 저장for _ in range(M): u, v, w = map(int, input().split()) edges.append((u, v, w))edges 배열에 출발 노드, 도착 노드(무향 그래프지만 편의상 출발-도착으로 지칭), 가중치를 저장한다. Kruskal 알고리즘을 사용하기 위해 이와 같이 저장하였고, 추후 Prim 알고리즘으로 풀이할 때는 연결 리.. 2025. 1. 8.
정규식(Regular Expression) 정규식- 문자들의 특정 패턴을 나타내기 위한 expression- 주로 검색을 목적으로 vi, grep, ex, sed 등에서 사용 정규식의 메타 문자(특수 문자)- 정규식의 행동을 제어하는 특수 문자- . * \ [ ] ^ $. any single character- '.'가 위치한 자리에 어떤 문자든 들어갈 수 있음- a.c는 aac, abc, acc, ... 등과 동일 ** 앞의 문자가 0번 이상 반복- a*c는 ac, aac, aaac, ... 등과 동일 \ Character escape- 메타 문자 의미 상실- '\' 뒤의 문자는 메타 문자로 사용되지 않음- a\.c의 '.'은 메타 문자로서의 '.'이 아닌 일반 문자 '.' ^'^' 뒤에 나오는 문자로 시작하는 문자열- ^x이면 x로 시작하는 .. 2024. 12. 8.
Linux 환경에서의 프로그램 실행 gcc: C 컴파일러$ gcc [options] FILE ...$ gcc file.c //a.out 파일 생성$ gcc -o file file.c //file 파일 생성- FILE은 무조건 C 파일(.c)- FILE을 컴파일한 실행 파일(.out) 생성- 파일명 옵션을 지정하지 않으면 컴파일 결과 a.out의 디폴트 파일명으로 생성* C++ 컴파일러는 g++library 만들기 및 사용$ ar [options] library.a file1.o file2.o file3.o- static library 파일은 (.a)r: include this(replace is exist)c: silently(if not exist)s: maintain table(symbol: file)x: extractt: print .. 2024. 12. 6.
Linux Commands Command vs. Instruction command:shell이 처리하는 cat, ls, cp, bash, vi, gcc 등(단, cd 등 내부 명령어는 bash가 직접 처리)의 독립적인 프로그램(실행 파일) instruction:CPU가 수행하는 add, sub, jump, branch, load, store 등의 기계어more$ more FILE- FILE 파일의 내용을 화면에 출력- 내용이 길 경우 한 화면씩 끊어서 보여준다는 점이 cat과의 차이- pipe("|")를 이용해 다른 프로그램과 동시에 사용되기도 less$ less FILE- 텍스트의 내용을 한 화면씩 끊어서 보여줌(more과 유사)- 앞의 내용으로 돌아갈 수 있음 date: 날짜 및 시간$ date$ date mmddhhmm- .. 2024. 12. 6.
vi editor vi는 텍스트 에디터의 한 종류로, 명령 모드와 입력 모드가 존재한다.$ vi //파일 이름 없이 vi 실행$ vi test //test라는 이름의 파일을 편집(혹은 생성) 파일의 저장과 종료키기능:w 파일명을 filename으로 하여 저장하고 수행을 계속:w현재 이름으로 저장하고 수행을 계속:w!경고 메시지 없이 무조건 저장:q편집한 내용이 없을 경우 수행 종료:wq현재 이름으로 저장하고 수행 종료:q!편집한 내용을 저장하지 않고 수행 종료:sh일시적으로 쉘 프롬프트 상태로 전환w가 포함된 명령어는 저장, q가 포함된 명령어는 종료와 연관이 있는 것을 확인할 수 있다. 텍스트 입력 모드키기능i텍스트가 커서 앞에서 삽입a텍스트가 커서 뒤에서 삽입o텍스트가 현재 줄 다음부터 삽입O텍스트가 현재 줄 앞에서.. 2024. 12. 6.
스레드 동기화(Thread Synchronization) 스레드 동기화 필요성 멀티스레드는 여러 작업을 동시에 실행하는 응용프로그램 작성 기법이다. 이때 다수의 스레드가 공유 자원이나 공유 데이터에 동시에 접근하는 경우 여러 스레드의 출력값들이 뒤섞여 표시되는 등 예상치 못한 문제가 발생할 수 있다. 따라서 멀티스레드 프로그램을 작성할 때는 다수의 스레드가 공유 데이터에 접근하는 경우에 대한 처리를 해 주어야 하며, 이것이 스레드 동기화(Thread Synchronization)이다. 스레드 동기화는 공유 데이터에 접근하려는 다수의 스레드가 순서대로 충돌 없이 배타적으로 공유 데이터에 접근하기 위해 상호 협력(cooperate)하는 것이다. 공유 데이터에 대한 접근은 배타적이고 독점적으로 이루어져야 하며, 공유 데이터를 독점적으로 다루는 프로그램 코드를 임계 .. 2024. 11. 28.
스레드 종료 스레드는 스스로 종료하거나 다른 스레드에 의해 강제 종료될 수 있으며, 종료된 스레드를 다시 살릴 수 없다. 스스로 종료메소드가 실행 중 또는 완전히 실행한 후 return하면 스레드가 종료된다.void run(){ ... return; //스스로 종료 ...} 강제 종료 - interrupt()종료하고자 하는 스레드의 interrupt() 메소드를 호출하면 스레드가 종료된다. 스레드 A가 스레드 B를 강제 종료시키고자 하는 경우, 스레드 A가 스레드 B의 interrupt()를 호출해야 한다.B.interrupt();스레드 B의 interrupt()가 호출되면 B 스레드에 InterruptedException 예외가 발생하는데, 이때 try-catch문에서 catch 루틴이 실행되어 retu.. 2024. 11. 28.
스레드 생명 주기와 스케줄링 스레드 상태 스레드는 생명 주기(life cycle)동안 여러 상태의 변이(NEW, RUNNABLE, TIMED_WAITING, BLOCK, WAITING, TERMINATED)를 거친다.1. NEW(생성): 스레드가 생성되었으나 아직 실행할 준비가 되지 않은 상태new Thread()에 의해 NEW 상태의 스레드가 생성됐을 때 이 스레드는 스케줄링되지 않아 실행될 수 없는 상태이다. 이때 스케줄링이란 JVM이 RUNNABLE 상태의 스레드 중 하나를 선택하여 실행시키는 것이며, start() 메소드가 호출되면 스레드는 RUNNABLE 상태로 전환된다. 2. RUNNABLE(준비): 스레드가 현재 실행되고 있거나 실행 준비되어 스케줄링을 기다리는 상태start() 메소드가 호출되어 NEW에서 RUNNAB.. 2024. 11. 28.
파이프라이닝 pipelining(2) - hazard Pipelining and ISA DesignRISC-V는 파이프라이닝에 유리한 ISA인데, 모든 명령어들이 32bit 길이이므로 한 사이클 내에 fetch 및 decode하기가 용이하다. 파이프라이닝(1)의 빨래 예시에서 확인할 수 있듯, 파이프라이닝 기법을 사용하면 명령어 처리 시간을 줄이지 않고 같은 시간 안에 더 많은 데이터를 처리할 수 있다. 하지만 빨래 예시와는 다르게 매 clock cycle마다 명령어를 처리할 수 없는 경우가 존재한다. 양말 한 켤레를 실수로 빨래 더미 A와 B에 나누어 넣었을 때, A에서 짝을 맞춰 양말을 개고 넣기 위해서는 아래 그림과 같이 B 더미의 건조 과정이 끝날 때까지 한 사이클만큼의 공백이 생긴다.이때 명령어를 처리하지 않고 대기하도록 하는 것을 bubble이라.. 2024. 11. 20.
스레드 만들기 자바 스레드를 만들기 위해서 개발자가 해야 하는 작업은 아래와 같다.스레드 코드 작성JVM에세 스레드를 생성하고 스레드 코드를 실행할 것을 요청스레드 코드를 작성하기 위해서 Thread 클래스를 이용하거나 Runnable 인터페이스를 사용할 수 있다.Thread 클래스를 상속받아 스레드 만들기 ※ Thread 생성자  ※ Thread 주요 메소드void run()스레드 코드, 반드시 Overriding하여 스레드 코드 작성void start()JVM에게 스레드 실행 시작 요청void interrupt()스레드 강제 종료static void yield()다른 스레드에게 실행을 양보, 이때 JVM은 다른 스레드를 선택하여 스케줄링void join()스레드 종료까지 대기long getId()스레드의 ID 값 .. 2024. 11. 19.