전체보기 (168) 썸네일형 리스트형 백준 10026 적록색약 https://www.acmicpc.net/problem/10026 10026번: 적록색약 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G( www.acmicpc.net 간단한 DFS 혹은 BFS 문제다. 두 개의 배열을 이용하면 금방 풀 수 있다. 아마 이 문제의 핵심은 Input 함수일듯...? /* 적록색약 */ #include #include #include using namespace std; void input(); void solve(); int N, WEAKNESS, NO_WEAKNESS; int dr[4] = { -1,0,1,0 }; int.. 백준 1103 게임 https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 1. 그래프를 이용해서 최장거리 + Cycle 체크로 푸는 사람도 있고 2. DFS + 다이나믹 프로그래밍을 이용해서 풀수도 있다 2번이 더 간단하므로 2번으로 풀었다. 기회가 된다면 1번으로 풀어보는 것도 좋겠다. (되는지는 확실치 않음) 이 문제에서 주어지는 input은 그래프로 치자면 양방향 간선이라서 그냥 방문한 곳을 또 방문하면 무한 루프가 생겼다고 볼 수 있다. 그래서 재방문시 -1을 .. 백준 2250 트리의 높이와 넓이 https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. �� www.acmicpc.net 트리의 중위 순회를 이용하는 문제이다. 전위순회, 중위순회, 후위순회도 정리하면 좋겠다 전위 : root --> left --> right 중위 : left --> root --> right 후위 : left --> right --> root /* 트리의 높이와 너비 */ #include #include #include #include #define MAX_NODE 1000.. Pintos Project(핀토스 프로젝트) 3 - Threads 이번에 할 프로젝트의 주인공은 Threads이다. Pintos Manual에는 제일 처음 등장하는 파트인데 울 학교에서는 제일 마지막에 했다. 이번에 일정상 Virtual Memory 구현 부분이 빠졌다고 들었는데, 그게 좀 아쉬워서 깃헙을 통해 Virtual Memory 테스트코드도 구해볼 생각이다. (OS는 내 사랑이니까!) 이번 프로젝트에서 Process나 Threads가 Priority에 맞추어 동작하도록 한다. 현재 PintOS의 thread는 RUNNING과 READY를 왕복하며 busy waiting을 한다. 아무것도 하는 일 없이 왔다~갔다~ 하면서 CPU를 낭비하고 있는 셈이다. CPU 낭비를 막기 위해 busy waiting 방식을 수정해서 더욱 합당한 waiting 방식을 구현한다. .. Pintos Project(핀토스 프로젝트) 2 - User Program_File management 이전 프로젝트에서 사용자와 상호작용할 수 있는 System call 몇 가지를 구현했다. 이번 프로젝트는 File Management와 관련된 System Call을 구현한다. 원래는 이전 프로젝트와 이번 프로젝트를 함께 진행해야 하지만 난이도가 워낙 높은 프로젝트이다보니... 학교 측에서 둘로 나눈 것 같다.(감사합니다 선생님...흑흑) 이전에 구현한 System Call과 잘 연동되어야 하는 것은 물론이고 File Processing도 잘 되어야 한다. 예를 들면 한 File을 두 Program이 접근할 경우 Race Condition이 발생할 수 있으므로 이를 잘 처리해야 한다. 이 외에도 파일을 이용한 Operation에 관한 다양한 이슈를 해결하면서 File System Call을 구현한다. 무.. Pintos Project(핀토스 프로젝트) 1 - User Program OS 과목에서 악명높은 프로젝트가 핀토스 프로젝트다. 그만큼 열심히하면 배워가는 것도 많다. 지금부터 핀토스 프로젝트 소개를 하려고 한다. 기준은 서강대학교에서 제공하는 Manual과 Pintos Manual이다. * 0_2 프로젝트는 핀토스의 data structure를 구현하는 것이다. 공식 Pintos에서 요구하는 test는 아니고 서강대에서 만든 것 같다. (test를 일일이 만든 게 대단하다...) Data structre를 열심히 공부한 사람은 쉽게 할 수 있고, 난이도도 높지 않으니 알아서 잘 하시길 바란다. Pintos Project 1은 User Program을 짜는 것이다. 현재 Pintos는 아주 기본적인 기능만 갖추고 있다. 할 수 있는 게 없다. 예를 들면 Boot하고 실행하고 P.. 백준 1238 파티 https://www.acmicpc.net/problem/1238 1238번: 파티 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 www.acmicpc.net 다익스트라 알고리즘이랑 메모이제이션을 섞어서 풀었다. 이중 배열을 이용한 다익스트라 알고리즘은 시간복잡도가 O(N^2)인데 반해서 우선순위 큐를 이용하면 O(N * log N)까지 줄일 수 있다. 1. 각 점에서 X까지 최단거리를 다익스트라를 이용해서 구한다. 이 때 지나치는 정점을 활용하는 게 중요하다 예를 들어서 1 -- > 2 --> 3 --> X가 경로라면 2 --> X의 비용은 1 .. 백준 9466 텀 프로젝트 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 문제 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 www.acmicpc.net 그래프 탐색과 DFS의 혼종이다. 그래프에 Cycle이 있는지 점검하는 문제다. 무식하게 풀자면 모든 노드를 DFS 돌려서 자기 자신으로 돌아오는 지 체크하면 된다! 근데 중복이 엄청 많을 것이다. 아무리 시간 복잡도가 3초라도 이런건 무조건 시간초과다 메모이제이션을 통해 최대한 중복 체크를 줄인다! 각 노드의 상태는 둘로 나뉜다. 1. 이전 DFS에서 방문한 노드 - Cycle 못 만든다. 2. 이번.. 백준 14499 주사위 굴리기 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 간단한 구현 문제다. 문제에 주어진 조건을 구현만 하면 된다. 다만 이 문제를 풀려면 제일 중요한 게 있는데 Input으로 들어오는 x,y 값이 반대다. 무슨 말인지는 밑의 코드에서 Input() 부분을 보기를 추천한다... /* 주사위 굴리기 */ #include #define MAX 21 using namespace std; i.. 백준 3197 백조의 호수 https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 가로로 R, 세로로 C만큼의 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있� www.acmicpc.net 1. 시간 복잡도 시간복잡도를 알면 문제 접근법이 그나마 보인다. 주어지는 R과 C가 각각 1500 이하 이므로 약 10^3이다. O(N^2) 까지는 너끈하지만 O(N^3)은 10^9가 된다. 대강 10억이다... 이건 시간 제한 1초에 무조건 걸리므로 최대 O(N^2 * logN)인 알고리즘을 찾는다. (적어도 N^3은 안된다...) 2. 문제풀이 L이 백조이고 이 둘이 만나는 데 걸리는 날을 .. 이전 1 ··· 13 14 15 16 17 다음
