본문 바로가기

전체 글

 (336)
백준 2073번 - 수도배관공사 (C++) https://www.acmicpc.net/problem/2073 2073번: 수도배관공사 아기염소들이 언덕에서 풀을 뜯고 놀다 보면 항상 도중에 목이 마르곤 했다. 그들은 불편함을 참지 못하고 수도관을 설치하여 거리 D(7 ≤ D ≤ 100,000)만큼 떨어진 곳의 강에서 물을 끌어오기로 www.acmicpc.net 배낭문제임은 금방알아챘으나 문제 해결은 하지 못했다. 먼저, 이 문제를 정석적인 배낭문제처럼 2차원 배열로 해결하려하면 메모리 초과가 난다. 2차원 배낭 문제를 1차원으로 바꿔야하는데, 상당히 까다로웠다. 난이도 조절이 필요할 것 같은데.. 논리적으로 언제 파이프를 갱신할 수 있을지 살펴보면, 두개의 파이프가 딱 D와 맞아떨어질 때 갱신이 가능함을 알 수 있다. 그리고 중요한 건 dp[D]..
OS - 주기억장치 개요 운영체제의 역할 운영체제의 가장 중요한 역할은 프로세스 관리와 메모리 관리이다. 이제부터 알아볼 것은 메모리 관리이다. 메모리는 언제나 부족하다. IT 기술이 발전하면서 계속해서 메모리는 늘어나고 있지만 그와 동시에 다뤄야할 데이터와 프로그램들도 함께 거대해진다. 그래서 메모리는 언제나 부족하고 효율적으로 관리해야한다. 메모리 관리의 개념과 정책 메모리 관리는 메모리 관리자가 담당하며 운영체제의 관리 모듈과 메모리 관리 장치가 협업하여 관리한다. 메모리 관리자는 여러 정책을 수립하고 관리한다. 적재 정책 배치 정책 대치 정책 메모리의 구조: 주소, 데이터 주소는 논리적 주소와 물리적 주소로 나뉜다. 논리적 주소 - 프로그래머가 사용하는 공간으로 보는 논리적 관점의 주소. 목적 코드가 저장된 공간과 프로그..
백준 1238번 - 파티 (C++) https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 이 문제는 "맞았습니다" 를 받는 것 자체는 다익스트라 알고리즘을 알고있으면 어렵지 않은 문제이다. 왜냐하면 문제 조건이 그렇게 까다롭지 않다. 1, 2, 3, 4 중 X = 2 라면 1~4까지 모두 다익스트라 알고리즘으로 2까지의 최단거리를 저장하고, 2에서 다른 곳으로 가는 방법들을 다익스트라로 저장하면 된다. 그러므로 노드가 4개이면, X 지점에서 다익스트라 한..
백준 2493번 - 탑 (C++) https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 단순히 답만 구하려면 쉬운 문제이다. 그러나 그렇게 풀면 시간복잡도가 O(N^2) 이 되어버린다. 처음에는 큐를 사용하여 6 9 5 7 4 라면 맨 뒤부터 시작해서 큐에 4를 넣고 뒤에서부터 비교하며 7을 만났을 때 => 큐의 모든 값과 비교 4 제거, 7을 큐에 삽입 현재 큐 : ( 7 ) 5를 만났을 때 => 큐의 모든 값과 비교 7 을 놔두고 5를 삽입 현재 큐 : ( 7 , 5 ) 9를 ..
프로그래머스 - 경주로 건설 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/67259# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 다익스트라를 응용하면 될 것이라 생각했다. DP배열을 만들고 계속 갱신해나가며 최적의 길을 찾으면 된다고 생각했다. 그러나 다익스트라가 가능하려면 한가지 강력한 전제 조건이 필요하다. 지금 dp값 보다 큰 값은 절대로 다시 체크하지 않아도 된다. 무슨말이냐면 지금 dp[2][2] = 30 이라하였을 때, 순회하다가 다시 dp[2][2]를 만났을 때 현재 값이 31이라면 가지 않겠다는 의미이다. ..
백준 20006번 - 랭킹전 대기열 (C++) https://www.acmicpc.net/problem/20006 20006번: 랭킹전 대기열 모든 생성된 방에 대해서 게임의 시작 유무와 방에 들어있는 플레이어들의 레벨과 아이디를 출력한다. 시작 유무와 플레이어의 정보들은 줄 바꿈으로 구분되며 레벨과 아이디는 한 줄에서 공백 www.acmicpc.net 처음에는 정렬을 해두고 풀어도 되는 줄 알았는데 순서대로 게임을 진행해야하는 조건이 있었다. (진짜 문제좀 잘 읽자) 그리디 , 구현 문제였다. 처음에는 우선순위큐 문제인가 생각했는데 기준이 달라지는 것이 아니기 때문에 우선순위큐는 필요없다. 나는 게임방의 기준을 rooms 벡터에 담아두고 어차피 순서가 바뀌지 않기 때문에 그 순서대로 다음 레벨을 비교해서 문제를 풀었다. 구현을 연습하는데 좋은 문제..
백준 10159번 - 저울 (C++) https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 이전에 푼 키 순서 문제와 거의 같다. 이렇게 "순서"에 관련된 문제들은 위상정렬도 생각하게 된다. 위상정렬은 inorder와 outorder를 새면서 bfs돌며 순서를 정하는 방식이다. 아무튼, 이 문제에서 플로이드-워셜로 관계 찾는 기법을 복습해보았다. 초기화를 하고 dp를 사용해 각 정점이 경유하여 갔을 때 더 빠르게 갈 수있으면 갱신하는 것이 플로이드 워셜이다. 그..
백준 2458번 - 키 순서 (C++) https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 두 가지 방식으로 풀어낼 수 있다. 1. dfs 2. 플로이드-워셜 1. 먼저 1번 방법을 알아보자. 내 키의 순서를 알 수 있다는 의미는 모든 노드와 연관되어 있다는 뜻이다. 더 풀어보자면 n번 노드에서 출발했을 때 모든 노드를 방문한다는 의미이다. 하지만 이 그래프는 단방향 그래프이다. 그리고 작은 키 -> 큰 키 로 이루어져 있다. 그러므로 두가지 dfs를 진행하는 것이 정 해이다. 작은키 -..

티스토리툴바