티스토리

공대생 기록장

검색하기

블로그 홈

공대생 기록장

yejin72.tistory.com/m

개발 블로그

구독자: 1

방명록 방문하기

주요 글 목록

2학년 1학기 종강 기념 오랜만의 티스토리다! 요새 다른 쪽에 집중할 일이 생겨서 알고리즘과 티스토리쪽에는 신경을 못 써주고 있다.. 그래도 성적도 발표된 만큼 잠시 한 학기의 활동을 짧게 기록하려고 한다. 우선 지난 일상 글에서 원했던 대로 올A+ 받아서 기분이 좋았다! 이번 학기에는 바라는 대로 수강신청도 되고 성적도 잘 나와줘서 한 학기 잘 보냈구나라는 생각이 든다. 다음 학기 목표는 학점 잘 챙기고,, 그저 하루하루를 허투로 쓰지 않는 것이다. 이번 방학도 스스로에게 정해놓은 매일의 과제는 꼭 지키며 살아가는 사람이 되고 싶다. 공감수 0 댓글수 0 2023. 7. 17.
[백준 13904] 과제 - 골드1(그리디, 정렬) https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 사용한 자료구조: 리스트 사용한 알고리즘: 정렬, 그리디 문제를 풀다가 이번 코드는 이제껏 한 번도 사용해본 적 없는 방법으로 푼 문제라 기록해두고 싶어서 오랜만에 알고리즘 포스팅을 한다. 원래 이 문제는 우선순위 큐를 사용해서 푸는 문제지만, 나는 리스트의 정렬만으로 문제를 풀이했다. 먼저, 이 문제에서의 데이터의 우선순위는 (1) 과제의 점수가 높을 수록, (2) 마감 기한이 짧을수록 높기 때문에 입력을 받으며 lambda 식으로 정렬해.. 공감수 0 댓글수 0 2023. 5. 21.
2학년 중간고사를 마친 후 이번 학기에 수강한 과목들은 운영체제, 자료구조, 세상을 읽는 논리적 사고, 현대 사회와 리더십, 미분적분학, 실용영어 등등이다. 저번 티스토리 글을 보니 2학년에 들을 전공 과목들에 대해 꽤 기대하고 있었고, 영어하고 수학을 수강하고 싶다는 글이 있었는데 바라는 대로 되었다! 기대했던 자료구조는 역시나 재밌어서 좋았다. 교양 중에서는 바라던 영어 2과목 수학 1과목의 수강을 성공했는데 모두 마음에 든다ㅜㅜ 학교 수학 교수님께서 강의도 잘하시고 좋으셔서 계속 따라다니는 중이다. 시험들은 모두 무난하게 본 것 같다. 이번 시험에서는 처음으로 A4용지에 시험 범위들을 적으면 1페이지~3페이지 내로 정리한 후 외우는 방법과 목차를 암기해서 머릿속에서 구조화하여 기억하는 방법을 이용했다. 이 방법은 무의식적으로.. 공감수 0 댓글수 0 2023. 4. 28.
그림으로 배우는 구조와 원리 운영체제(구현회) 3장 연습문제 풀이 1. 프로세스(process)를 바르게 설명한 것끼리 나열한 것은? ㉠ 실행 가능한 PCB가 있는 프로그램 ㉡ 프로세서가 할당하는 개체로 디스패치가 가능한 단위 ㉢ 목적 또는 결과에 따라 발생하는 사건들의 과정 ㉣ 동기적 행위를 일으키는 주체 ① ㉠,㉡,㉢ ② ㉠,㉡,㉣ ③ ㉠,㉢,㉣ ④ ㉡,㉢,㉣ 더보기 정답: ①, 프로세스는 비동기적 행위를 한다. 2.프로세스 제어 블록을 가지고, 현재 실행 중이거나 곧 실행 가능하고, 프로세서(CPU)를 할당받을 수 있는 프로그램으로 정의할 수 있는 것은? ① 작업 집합 ② 세그먼테이션 ③ 모니터 ④ 프로세스 더보기 정답: ④, 프로세스(작업)에 관한 설명이다. 3. 프로세스의 정의로 적당하지 않은 것은? ① 하드웨어로 사용하는 입출력장치 ② 실행 중인 프로그램 ③.. 공감수 0 댓글수 0 2023. 4. 12.
프로세스와 스레드(프로세스의 개념, 상태 변화, 관리와 스레드의 개념, 상태 변화, 구현) 1. 프로세스의 개념과 상태 변화 프로세스는 디스크에 있는 프로그램을 메모리에 적재하여 운영체제의 제어를 받는 상태가 된, 즉 실행 중인 프로그램이다. 프로세스가 되기 위해서는 프로세서 점유 시간, 메모리, 파일, 입출력장치와 같은 자원이 필요하다. 프로세스의 분류 수행 역할에 따른 분류: 시스템 프로세스, 사용자 프로세스 병행 수행 방법에 따른 분류: 독립 프로세스, 협력 프로세스 프로세스 상태 변화 관리 작업 스케줄러: 스풀러가 디스크에 저장한 작업 중 실행할 작업을 선장하고 준비 큐에 삽입한다. 프로세스 스케줄러: 선정한 작업의 상태를 변화시키며 프로세스의 생성에서 종료까지의 과정을 수행한다. 프로세스 제어 블록 프로세스 제어 블록을 통해 프로세스를 제어할 때 필요한 프로세스 상태 정보를 저장한다... 공감수 0 댓글수 0 2023. 4. 12.
순환 알고리즘과 반복 알고리즘 순환 알고리즘 순환 알고리즘이란 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법을 말한다. 문제의 정의 자체가 순환적으로 되어 있는 경우에 적합한 방법이다. 그러나, 예로 들어 피보나치값을 계산할 때 같은 항을 중복해서 계산했던 것처럼 함수 호출의 오버헤드 문제가 발생할 수 있다. 순환 알고리즘은 순환 호출을 하는 부분과 순환 호출을 멈추는 부분으로 이루어져 있다. 반복 알고리즘 반복 알고리즘은 for나 while을 이용하여 반복한다. 수행속도가 빠르지만, 순환적인 문제에 대해서는 프로그램 작성이 어려울 수 있다. 다양한 알고리즘 1. 팩토리얼 구하기 int factorial_recur(int n) { // 순환적 방법 if (n == 1) return 1; return .. 공감수 0 댓글수 0 2023. 4. 10.
알고리즘의 성능 분석(시간 복잡도, 공간 복잡도, 빅오 표기법) 알고리즘의 성능 분석 방법 1. 수행 시간 측정 두 개의 알고리즘의 실제 수행 시간을 측정한다. 실제로 구현하여야 하며, 동일한 하드웨어를 사용해야 한다. 2. 알고리즘의 복잡도 분석 알고리즘이 수행하는 연산의 횟수를 측정하여 비교한다. 실제로 구현하지 않아도 된다. 연산의 수행 횟수는 입력의 개수 n에 대한 함수이다. 2-1) 시간 복잡도 전체 소요 시간 = 컴파일 시간 + 실행 시간 방법: 전역 변수 count의 사용, 단계수 테이블 방식 2-2) 공간 복잡도 공간 요구량 = 고정 공간 요구 + 가변 공간 요구 고정 공간: 프로그램 입출력의 횟수나 크기와 관계없는 공간 가변 공간: 해당 문제의 인스턴스(I)에 의존하는 공간 Asymptotic Notation(점근 표기법) 점근 표기법에는 빅오(함수의.. 공감수 0 댓글수 0 2023. 4. 10.
자료구조의 소개(자료구조, 알고리즘, 데이터 추상화) 프로그램 = 자료구조 + 알고리즘 프로그램의 자료구조와 알고리즘으로 만들어진다. 그러므로 개발자가 효율적인 프로그램을 작성하기 위해서는 자료구조란 무엇이고 어떤 종류가 있는지, 어떻게 하면 효율적인 알고리즘을 구현할 수 있을지를 고민해야 한다. 또한, 이 둘의 설명과 더불어 크고 복잡한 문제를 단순화시킬 수 있는 데이터 추상화 개념을 숙지해야 한다. 자료 구조란? 자료구조란 자료를 효율적으로 사용하기 위해 자료의 특성에 따라 분류하고 구성, 저장, 처리하는 모든 작업이다. 알고리즘이란? 알고리즘이란 특정한 일을 수행하기 위한 명령어의 유한 집합을 말한다. 기준 입력: (외부)원인 >= 1 출력: 결과 >= 1 명백성: 모호하지 않은 명확한 명령 유한성: 한정된 수의 단계 후에는 반드시 종료 유효성: 각 .. 공감수 1 댓글수 0 2023. 4. 10.
그림으로 배우는 구조와 원리 운영체제(구현회) 2장 연습문제 풀이 1. 운영체제의 기능으로 적당하지 않은 것은? ① 컴퓨터 시스템의 초기화 기능 ② 효율적인 자원 관리와 할당 기능 ③ 고급 언어로 작성한 프로그램을 기계어로 번역하는 기능 ④ 오류 검사 및 복구 기능 더보기 정답: ③, 고급 언어로 작성한 프로그램을 기계어로 번역하는 기능은 명령 해석기 중에서도 컴파일러의 기능이다. 2. 운영체제의 목적과 가장 거리가 먼 것은? ① 사용자 인터페이스 제공 ② 주변장치 관리 ③ 데이터 압축 및 복원 ④ 신뢰성 향상 더보기 정답: ③, 운영체제의 목적은 편리성(사용자 인터페이스 제공), 효율성(처리량 향상, 지연 및 응답 시간 단축, 신뢰성 향상, 사용 가능도 향상), 제어 서비스 향상(주변장치 관리)이다. 3. 운영체제의 성능 판단 요소로 거리가 먼 것은? ① 처리 능력 .. 공감수 1 댓글수 0 2023. 4. 6.
운영체제의 소개(개념과 발전 목적, 기능, 발전 과정과 유형, 서비스, 구조) 1. 운영체제의 개념과 발전 목적 컴퓨터 시스템의 구성 요소 컴퓨터 자원관리 면에서 운영체제의 역할 조정자: 프로그램이 작업을 할 수 있는 환경을 제공 자원 할당자나 관리자: 각 응용 프로그램에 필요한 자원을 올바른 순서로 할당 응용 프로그램과 입출력장치 제어자: 다양한 입출력장치와 응용 프로그램을 제어 운영체제의 발전 목적 2. 운영체제의 기능 ※ 운영체제는 메인 메모리와 보조기억장치를 관리한다. ※ 프로세스는 운영체제 프로세스와 사용자 프로세스로 구분된다. 3. 운영체제의 발전 과정과 유형 운영체제의 발전 과정 1940년대: 운영체제 없음, 순차 처리 시스템 1950년대: 일괄 처리 시스템, 버퍼링, 스풀링 1960년대: 다중 프로그래밍, 시분할, 다중 처리, 실시간 처리 시스템 1970년대 초반: .. 공감수 0 댓글수 0 2023. 4. 6.
그림으로 배우는 구조와 원리 운영체제(구현회) 1장 연습문제 풀이 1. 컴퓨터 내부에서 프로세서 메모리 사이의 정보 전송에 사용하는 통로는? ① 버스 ② 레지스터 ③ 블록 ④ 보조기억장치 더보기 정답: ①, 시스템 버스는 프로세서와 메모리 사이뿐만이 아니더라도 모든 컴퓨터의 하드웨어들을 물리적으로 연결하여 서로 데이터를 주고받을 수 있게 하는 통로이다. 2. 프로세서에서 사용하는 버스 형태가 아닌 것은? ① 주소 버스 ② 제어 버스 ③ 데이터 버스 ④ 시스템 버스 더보기 정답: ④, 시스템 버스는 데이터 버스, 주소 버스, 제어 버스로 이루어져 있다. 3. 목적이 특수한 값 하나를 저장하거나 연산을 처리하다가 중간 값을 저장하는 프로세서에 위치하는 고속 메모리는? ① 버스 ② 레지스터 ③ 메인 메모리 ④ 캐시 더보기 정답: ② ① 버스는 메모리가 아니다. ③ 메인 메모.. 공감수 0 댓글수 0 2023. 4. 5.
컴퓨터 시스템의 동작 과정(명령어의 구조와 실행, 인터럽트) 입력장치로 받은 명령어 혹은 데이터를 메모리에 저장함 제어장치에 의해 정보를 인출하여 연산장치에서 처리 결과를 출력장치에 표시하거나 보조기억장치에 저장함 컴퓨터에 유입되는 정보는 컴파일러 등을 이용하여 이진화된 기계 명령어로 변환된 후 처리된다. 이때, 명령어의 구조는 어떻게 되며 어떠한 수행 과정을 거치는지에 대해 알아야 컴퓨터의 동작 과정을 더욱 자세히 이해할 수 있다. 명령어의 구조 연산 부호(오피코드): 데이터 전송, 산술 및 논리 연산, 제어 흐름 변경, 입출력 제어. 연산 부호가 n비트이면 최대 2^n개 연산이 가능 피연산자(오퍼랜드): 연산할 데이터 정보가 저장되기도 하지만 주로 데이터가 저장된 위치가 저장됨, 소스 피연산자와 목적지 피연산자로 구분됨 오퍼랜.. 공감수 0 댓글수 0 2023. 4. 5.
컴퓨터 하드웨어의 구성(프로세서, 메모리, 시스템 버스, 주변장치) 컴퓨터 시스템 = 하드웨어 + 소프트웨어 우리가 흔히 사용하는 컴퓨터 시스템은 하드웨어와 소프트웨어로 구성된다. 하드웨어는 운영체제라는 특별한 소프트웨어를 통해 관리되는데, 그렇기 때문에 운영체제를 이해하기 위해서는 하드웨어가 어떻게 구성되어 있는지에 대해 우선적으로 잘 알고 있어야 한다. 컴퓨터 하드웨어는 크게 프로세서, 메모리, 주변장치로 구성되며, 시스템 버스가 이 장치들을 연결해 준다. 1. 프로세서 중앙처리장치(CPU)라고도 불리는 프로세서는 컴퓨터의 모든 장치의 동작을 제어하고 명령을 실행한다. 제어 부분인 제어장치와 데이터 부분인 연산장치, 레지스터로 구성된다. 프로세서의 수가 많을수록 처리 속도는 빠르다. 탑재된 프로세서의 개수에 따라 싱글코어, 듀얼코어, 쿼드코어 등으로 불린다. 레지스터.. 공감수 0 댓글수 0 2023. 3. 31.
[백준 1600] 말이 되고픈 원숭이 - BFS 알고리즘 문제 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 녀석은 말(Horse)이 되기를 간절히 원했다. 그래서 그는 말의 움직임을 유심히 살펴보고 그대로 따라 하기로 하였다. 말은 말이다. 말은 격자판에서 체스의 나이트와 같은 이동방식을 가진다. 다음 그림에 말의 이동방법이 나타나있다. x표시한 곳으로 말이 갈 수 있다는 뜻이다. 참고로 말은 장애물을 뛰어넘을 수 있다. x x x x 말 x x x x 근데 원숭이는 한 가지 착각하고 있는 것이 있다. 말은 저렇게 움직일 수 있지만 원숭이는 능력이 부족해서 총 K번만 위와 같이 움직일 수 있고, 그 외에는 그냥 인접한 칸으로만 움직일 수 있다. 대각선 방향은 인접한 칸에 포함되지 않는다. 이제 원숭이는 머나먼 여행길을 떠난다. 격자판의 맨.. 공감수 0 댓글수 0 2023. 2. 16.
[백준 1854] K번째 최단경로 찾기 - 다익스트라 알고리즘 https://www.acmicpc.net/problem/1854 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 문제 봄캠프를 마친 김진영 조교는 여러 도시를 돌며 여행을 다닐 계획이다. 그런데 김 조교는, '느림의 미학'을 중요시하는 사람이라 항상 최단경로로만 이동하는 것은 별로 좋아하지 않는다. 하지만 너무 시간이 오래 걸리는 경로도 그리 매력적인 것만은 아니어서, 적당한 타협안인 'k번째 최단경로'를 구하길 원한다. 그를 돕기 위한 프로그램을 작.. 공감수 0 댓글수 0 2023. 2. 13.
[백준 3109] 빵집 - DFS, 그리디 https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 문제 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 중에, 가스비가 제일 크다는 것을 알게되었다. 따라서 원웅이는 근처 빵집의 가스관에 몰래 파이프를 설치해 훔쳐서 사용하기로 했다. 빵집이 있는 곳은 R*C 격자로 표현할 수 있다. 첫째 열은 근처 빵집의 가스관이고, 마지막 열.. 공감수 0 댓글수 0 2023. 2. 10.
[백준 9376] 탈옥 - 0-1 BFS 알고리즘 https://www.acmicpc.net/problem/9376 9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net 문제 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타나 있다. 감옥은 무인 감옥으로 죄수 두 명이 감옥에 있는 유일한 사람이다. 문은 중앙 제어실에서만 열 수 있다. 상근이는 특별한 기술을 이용해 제어실을 통하지 않고 문을 열려고 한다. 하지만, 문을 열려면 시간이 매우 .. 공감수 0 댓글수 0 2023. 2. 8.
0-1 BFS(0-1 Breadth First Search) 알고리즘 0-1 BFS란, 기존 BFS 알고리즘을 응용한 것으로 가중치가 0이나 1로만 주어진 그래프에서 최단 경로를 찾는 알고리즘이다. 최단 경로를 찾는 알고리즘으로는 다익스트라 알고리즘이 대표적이다. 그러나, 다익스트라 알고리즘으로는 O(ElogV) 또는 O(ElogE)의 시간복잡도를 갖지만 0-1 BFS 알고리즘은 O(V+E)의 시간복잡도를 가진다. 0-1 BFS 알고리즘 구현을 위해서는 덱 자료구조를 사용한다. 가중치가 낮은 간선이 우선순위가 높기 때문에 아래의 두 가지 규칙을 추가한다. 간선의 가중치가 0이라면 덱의 front에 정보를 추가한다. 간선의 가중치가 1이라면 덱의 back에 정보를 추가한다. 백준에서 풀 수 있는 대표적인 0-1 BFS 알고리즘이 적용되는 문제에는 13549번이 있다. htt.. 공감수 0 댓글수 0 2023. 2. 8.
재귀 방법으로 순열과 조합 구현하기 순열과 조합의 차이는 순서에 상관이 있는지 없는지이다. 조합에서는 순서가 없기 때문에 시작점보다 작은 위치는 다시 방문하지 않는다. 그러나, 순열은 순서가 있기 때문에 시작점보다 작은 위치 또한 방문해야 한다. 라이브러리없이 구현하는 방법은 dfs 알고리즘을 이용하는 것인데, 그 중에도 재귀를 이용하여 구현할 수 있다. 순열(permutation)이란, 서로 다른 n개 중에서 순서에 상관하여 r개를 뽑는 경우의 수이다. arr = [1, 2, 3, 4] select = [False for _ in range(4)] result = [] def dfs(cnt): if cnt == 3: print(*result) return for i in range(4): if not select[i]: select[i].. 공감수 0 댓글수 0 2023. 2. 8.
[백준 10942] 팰린드롬? - 다이나믹 프로그래밍 https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 문제 명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다. 먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그다음, 명우에게 질문을 총 M번 한다. 각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다. 예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자. .. 공감수 0 댓글수 0 2023. 2. 7.
[백준 7579] 앱 - 배낭 문제, 다이나믹 프로그래밍 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 문제 우리는 스마트폰을 사용하면서 여러 가지 앱(App)을 실행하게 된다. 대개의 경우 화면에 보이는 ‘실행 중’인 앱은 하나뿐이지만 보이지 않는 상태로 많은 앱이 '활성화'되어 있다. 앱들이 활성화되어 있다는 것은 화면에 보이지 않더라도 메인 메모리에 직전의 상태가 기록되어 있는 것을 말한다. 현재 실행 중이 아니더라도 이렇게 메모리에 남겨두는 이유는 사용자가 이전에 실행하던 앱을 다시 불러올 때에 직.. 공감수 0 댓글수 0 2023. 2. 6.
[백준 9252] LCS 2 - 최장 공통 부분 수열 https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 문제 LCS(Longest Common Subsequence, 최장 공통 부분 수열) 문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 .. 공감수 0 댓글수 0 2023. 2. 6.
[백준 12865] 평범한 배낭 - 다이나믹 프로그래밍, 배낭 문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데,.. 공감수 0 댓글수 0 2023. 2. 6.
[백준 1948] 임계경로 - 위상 정렬, 역추적 https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 문제 월드 나라는 모든 도로가 일방통행인 도로이고, 싸이클이 없다. 그런데 어떤 무수히 많은 사람들이 월드 나라의 지도를 그리기 위해서, 어떤 시작 도시로부터 도착 도시까지 출발을 하여 가능한 모든 경로를 탐색한다고 한다. 이 지도를 그리는 사람들은 사이가 너무 좋아서 지도를 그리는 일을 다 마치고 도착 도시에서 모두 다 만나기로 하였다. 그렇다고 하였을 때 이들이 만나.. 공감수 0 댓글수 0 2023. 2. 6.
[백준 5719] 거의 최단 경로 - 다익스트라 알고리즘, bfs 역추적 https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 문제 요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다. 상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다.. 공감수 0 댓글수 0 2023. 2. 5.
[백준 2357] 최솟값과 최댓값 - 세그먼트 트리 https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 문제 N(1 ≤ N ≤ 100,000) 개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000) 개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자. 여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야.. 공감수 0 댓글수 0 2023. 2. 4.
세그먼트 트리(Segment Tree) 자료구조 세그먼트 트리(Segment Tree) 자료구조는 누적 합 알고리즘의 심화 버전으로 이해될 수 있다. 크기가 N인 배열이 주어졌을 때, 누적 합 알고리즘의 시간복잡도는 O(N)이다. 이도 빠르긴 하지만, N의 크기가 더 커졌을 경우에는 이 또한 시간 초과가 나올 수 있다. 세그먼트 트리라는 완전 이진 트리 형태의 자료구조를 사용하면 배열의 특정 구간의 합을 구하는 시간복잡도는 O(logN)으로 훨씬 더 시간을 단축할 수 있다. 배열의 크기가 N일 경우의 세그먼트 트리의 형태은 다음과 같다. 하나의 노드마다 인덱스 i~인덱스 j 사이인 배열 구간의 누적 합 결과값이 들어간다. 세그먼트 트리 만들기 완전 이진 트리는 배열을 통해 구현한다. 어떠한 부모 노드의 두 자식 노드들은 부모 노드의 인덱스를 idx라고.. 공감수 0 댓글수 0 2023. 2. 4.
[백준 2887] 행성 터널 - 플래티넘5 / 최소 신장 트리 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 문제 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 행성은 3차원 좌표 위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-.. 공감수 0 댓글수 0 2023. 2. 3.
[백준 1865] 웜홀 - 골드3(벨만-포드 알고리즘) https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다. 시간.. 공감수 0 댓글수 0 2023. 2. 2.
[백준 12015] 가장 긴 증가하는 부분 수열 2 - 파이썬(Python) - 골드2(이분 탐색 알고리즘) https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 이 문제에서 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)에 대해 공부하게 되었다... 공감수 0 댓글수 0 2023. 2. 1.

728x90

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.