분류 전체보기

[백준 20165] 인내의 도미노 장인 호석 C++

20165번: 인내의 도미노 장인 호석 사람을 화나게 하는 법은 다양하다. 그 중에서도 악질은 바로 열심히 세워놓은 도미노를 넘어뜨리는 것이다. 이번에 출시된 보드 게임인 "너 죽고 나 살자 게임"은 바로 이 점을 이용해서 2명이 www.acmicpc.net 구현, 시뮬레이션 도미노 넘어뜨리는 구현 : crash_domino() 참고 현재 넘어지고 있는 도미노 : last 곧 넘어질 수도 있는 도미노 : Map[nr][nc] 현재 넘어지는 도미노의 최대길이를 구한다. last = max(last, Map[nr][nc]) 만약 도미노가 있다면 넘어뜨린다. Map[nr][nc] = 0 nr과 nc를 현재 방향에 맞춰서 이동시킨다. 하나 넘어뜨렸으므로 현재 넘어지고 있는 도미노의 길이를 1 감소시킨다. 1 2..

[OS] Virtual Memory #1

Virtual Memory 각각 가상화된 OS들이 자신만의 물리 메모리가 있다고 믿게 해주기 위해 메모리 가상화를 사용한다. 메모리 가상화의 목표 투명성 프로세스는 메모리가 가상화 된 사실을 몰라야 한다. 효율성 메모리 공간의 파편화를 최소화 한다. (공간 효율) 하드웨어의 도움을 받아 오버헤드를 줄인다. (시간 효율) 보안 OS와 프로세스를 다른 프로세스로부터 보호해야 한다. 프로세스 각각은 독립적이어야 한다. 오른쪽이 실제 물리 메모리 공간이고 왼쪽이 가상 메모리 공간이다. 하드웨어의 도움을 받아 가상메모리 주소를 실제 물리 메모리 주소로 변환해 사용할 수 있다. 주소 변환 OS는 물리 메모리 공간의 어디가 비어있는지, 어디가 사용중인지를 추적할 수 있어야 한다. 메모리 공간의 주소는 물리 메모리에 ..

[백준 16681] 등산 C++

16681번: 등산 첫 번째 줄에 지도에 표시된 지점의 개수, 지점을 잇는 경로의 개수, 주환이의 거리 비례 체력 소모량, 높이 비례 성취감 획득량을 나타내는 정수 N, M, D, E가 공백을 사이에 두고 주어진다. (2 ≤ www.acmicpc.net 다익스트라 시작점은 항상 1이고 도착점은 항상 N이다. 시작점에서 도착점으로 가면서 높이가 점점 높아지는 최단거리 다익스트라를 수행한다. 도착점에서 시작점으로 가면서 높이가 점점 높아지는 최단거리 다익스트라를 수행한다. 임의의 가운데 정점을 잡고 해당 정점이 시작점과 도착점 모두와 연결되어있다면 위 2개의 다익스트라를 통해서 시작점과 연결된 최단거리는 자연스럽게 높이가 증가하는 최단거리가 구해지고, 임의의 정점에서 도착점으로 가는 최단거리는 높이가 감소하..

[백준 1890] 점프 C++

1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 다이나믹 프로그래밍 dfs top-down방식으로 2차원 cache를 적용한 풀이. Cache[r][c] = r, c에서 점프해서 N-1, N-1에 도달할 수 있는 경우의 수. long long 주의. N-1, N-1에 도달하면 1을 리턴. Map의 원소가 0이면 0을 바로 리턴. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 ..

[백준 2573] 빙산 C++

2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net BFS 현재 맵의 빙산의 개수가 0이 될 때까지 반복문을 수행한다. 물과 접촉한 빙산의 높이를 줄여주는 BFS를 수행한다. 높이가 달라진 빙산들은 임시 맵과 큐에 따로 저장한다. 임시 맵의 정보를 기존 맵으로 복사한다. 임시 큐의 빙산 정보를 기존 큐의 빙산정보로 옮김과 동시에 높이가 달라진 빙산들이 서로 떨어졌는지 확인하는 BFS를 수행한다. 중간에 서로 떨어진 경우에는 현재 year를 출력하고 return 한다. 1 2 3 4 5 6 7 8 9 10 1..

[백준 3977] 축구 전술 C++

3977번: 축구 전술 World Soccer Championship이 다가오고 있다! 천재적인 전술을 창조하는 플랜 아티스트 감독 도현이는 자신의 팀이 승리하도록 만반의 준비를 가하고 있다. 도현이의 전략은 경기장을 여러 개의 구역 www.acmicpc.net 강한 연결 요소 1. 문제 해결 아이디어 도미노 문제와 매우 비슷한 문제이다. 이 문장을 통해서 SCC임을 알 수 있다. 강한 연결 요소 (SCC) - 타잔 알고리즘 [백준 2150] Strongly Connected Component C++ 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으..

[SWEA 1206] View (D3)

SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 1000*255 = 25만 밖에 안되고, test case도 10개 뿐이므로 문제에서 주어진 아파트를 배열에 모두 구현하는 방법을 사용했다. 현재 아파트의 현재 층에서 좌우로 1, 2개 의 칸이 비어있다면 조망권이 있는 집으로 분류했다. 아파트의 구조를 2차원 배열에 담지않고 [1000]인 1차원 배열에 아파트의 최대 층수만 가지고 있어도 거의 비슷하게 풀릴듯 하다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 ..

근거리 네트워크 (LAN)

algospot.com :: LAN 근거리 네트워크 문제 정보 문제 근거리 네트워크(LAN, Local Area Network)는 가정, 학교, 혹은 회사 등의 제한된 공간 내의 컴퓨터들을 연결하는 네트워크입니다. 알고스팟 대학교에서는 캠퍼스의 일 algospot.com 최소 스패닝 트리 문제 설명 더보기 N개의 정점의 좌표가 주어지고 가중치 없이 연결할 수 있는 정점의 번호가 주어진다. 양방향 간선이지만 u에서 v로 가는 간선 하나만 저장해주면 된다. (u < v) 2중 for문을 통해서 모든 정점끼리 연결될 수 있는 가중치가 포함된 간선을 구해준다. 크루스칼 알고리즘을 적용하기 전에 주어지는 정점들을 Union해버리면 가중치 없이 정점을 미리 연결해줄 수 있다. 그리고 나머지 정점들을 크루스칼 알고리..

선거 공약 (PROMISES)

algospot.com :: PROMISES 선거 공약 문제 정보 문제 경제가 침체기에 빠졌을 때 정치인들이 흔히 내거는 공약으로 대규모 토목 공사를 통한 경기 부양책이 있습니다. 이번에 집권당에서는 향후 N 년간 1년에 하나씩 전국 algospot.com 플로이드-와샬 문제 설명 더보기 우선 기존에 있던 고속도로들을 가지고 플로이드 알고리즘을 통해서 최단거리를 구해준다. 그리고 새로운 고속도로(a에서 b로 가는)가 건설 될 때마다 현재 최단거리와 비교해서 비용이 같거나 오히려 더 크다면 해당 고속도로를 설치할 필요가 없다. 하지만 새로운 고속도로를 설치하는게 이득이 된다면 a에서 b로 가는 고속도로를 추가하고 플로이드 알고리즘을 통해서 모든 간선의 최소비용을 갱신해 준다. r에서 c로 가는 비용을 갱신..

[백준 1504] 특정한 최단경로 C++

1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 다익스트라 1. 문제 해결 아이디어 반드시 방문해야 하는 정점이 2개 주어진다. 예를 들어 1번 정점에서 4번 정점으로 가야하는데 2, 3번 정점을 반드시 거쳐야 한다고 하자 첫 번째로 1 -> 2 -> 3 -> 4 순으로 정점을 방문할 수 있다. 위 순서는 각 정점이 방문된 시점을 순서대로 나열한 것에 불과하다. 1에서 2, 2에서 3, 3에서 4로 가는 최단 거리를 구하기 위해서 중간에 다양한 정점을 방문할 수 있..