CSE 전공노트

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 난이도: 골드 4 사용언어: JAVA 풀이 전형적으로 BFS를 이용하는 문제입니다. 단지 보통 BFS를 수행하는 문제와 다른 점은 지훈이와 불의 이동을 따로 체크해주어야 한다는 점입니다. 그래서 저는 BFS를 위한 큐와 BFS 함수를 2개씩 만들어 지훈이의 이동과 불의 이동을 따로 관리했습니다. 그 외에는 크게 고려해야 할 사항이 없는..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하이고, D는 10,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주 www.acmicpc.net 난이도: 골드 5 사용언어: JAVA 풀이 저는 이 문제를 다이나믹 프로그래밍을 이용해 해결했습니다. dp 배열을 생성하고, 해당 위치까지 올 수 있는 가장 짧은 거리의 값을 배열에 저장하였습니다. 특정 위치까지 올 수 있는 가장 짧은 거리는 현재 dp에 저장된 값과 한 칸 전까지 올 수 있는 가장 짧은 거리 +1, 그리고 해당 지점에 도..

React는 웹앱의 View를 개발하기 위해 사용하는 자바스크립트 라이브러리입니다. View를 개발하기 위해 사용한다는 말은 다시 말해 사용자가 조작하기 위한 UI를 만드는 라이브러리라고 할 수 있습니다. 우선 이번 글에서는 Windows에서 React를 실행시키는 방법을 알아보도록 하겠습니다. 가장 먼저 아래의 링크에서 Node JS를 다운로드 받아줍니다. Node JS는 자바 스크립트 언어를 웹 브라우저 환경이 아닌 곳에서도 구동할 수 있도록 런타임 환경을 제공하는 소프트웨어 플랫폼입니다. nodejs.org/ko/download/ 다운로드 | Node.js Node.js® is a JavaScript runtime built on Chrome's V8 JavaScript engine. nodejs...

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y(-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 난이도: 골드 5 사용언어: JAVA 풀이 시작점과 도착점에 대한 입력을 받아 시작점의 위치를 기준으로 오름차순 정렬만 할 수 있다면, 이미 문제를 푼 것이나 다름이 없습니다. 정렬을 해두었다면 그냥 선을 하나씩 확인하면서 현재 그려지고 있는 선과 분리된 것인지 또는 겹쳐지는 것인지를 판단하고, 그어진 선의 총 길이를 계..

1. 백트래킹(Backtracking) 가장 대표적으로 알고 있는 완전 탐색 알고리즘으로는 DFS를 꼽을 수 있습니다. 하지만 DFS는 정말 완전히 모든 경로를 탐색하므로, 때때로 비효율적일 수 있습니다. 여기서 백트래킹이라는 개념이 등장합니다. 바로 가능성이 있는 부분만 탐색한다는 것입니다. 즉, 어떤 노드를 탐색할 때, 목표로 가는 가능성이 없는 노드라면, 과감하게 배제하고 되돌아갑니다. 이를 가지치기(Pruning)이라고 합니다. 이해를 돕기 위해 예시를 이용해 설명을 더 해보도록 하겠습니다. 백트래킹을 설명할 때 가장 많이 사용하는 예시는 바로 N-Queen입니다. 2. N-Queen N-Queen 문제는 다음과 같이 설명할 수 있습니다. "크기가 N*N인 체스판 위에 퀸 N개를 서로 공격할 수 ..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 난이도: 골드 3 사용언어: JAVA 풀이 기본적으로 BFS를 이용하는 문제이며, 벽을 K번 부술 수 있기 때문에 이를 감안해서 코드를 작성해 주어야 합니다. 메모리 초과를 막기 위해 가장 중요한 아이디어는, 만일 누가 이미 한 번 지나간 경로를 발견했을 때, 해당 경로가 자신보다 더 적거나 같은 수의 벽을 파괴하..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 난이도: 골드 5 사용언어: JAVA 풀이 이 문제는 BFS를 사용하여 해결하는 대표적인 유형의 문제입니다. 출발층에서 BFS를 시작하여 스타트링크가 있는 G 층에 도달할 때까지 BFS를 반복해주기만 하면 됩니다. 물론 가장 빨리 도착하는 한 가지 경로만 찾으면 되므로 한 번 도착한 층은 마킹을 해주어 다시 검사하지 않도록 합니다. 1 2 3 4 5 6 7 8 ..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 난이도: 실버 2 사용언어: JAVA 풀이 전형적으로 다이나믹 프로그래밍을 이용하여 해결하는 문제이고, 구현도 어렵지 않습니다. 왼쪽부터 다이나믹 프로그래밍을 위한 dp라는 배열을 채워나갈 텐데, 다음과 같은 규칙을 갖습니다. 바로 A칸에 들어갈 dp의 값은 1번 칸까지의 dp 값과, 2번 칸까지의 dp 값과, 3번 칸까지의 dp 값 중 ..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 난이도: 골드 5 사용언어: JAVA 풀이 사실 어떤 알고리즘 문제가 아니라 구현 문제라서, 문제의 조건대로 쭉 구현해주시면 됩니다. 그리고 주의해야 할 점은 청소는 북-서-남-동으로 이루어지지만, 입력을 받을 때 d 값은 0이 북쪽, 1이 동쪽, 2가 남쪽, 3이 서쪽으로 방향이 반대라는 점입니다. 저는 3차원 배열을 이용해 현재의 방향과 이동할..

1. 모듈 (Module) 모듈이란 모듈화를 통해 분리된 시스템의 각 기능을 뜻합니다. 모듈화는 시스템을 모듈 단위로 나누는 것을 뜻하며, 이를 통해 시스템의 수정 및 재사용, 그리고 유지, 관리가 용이해지고, 소프트웨어의 성능을 향상할 수도 있습니다. 이 모듈은 단독으로 컴파일이 가능하고, 또 재사용이 가능합니다. 이 모듈들이 시스템 안에서 얼마나 독립적으로 기능을 하는지를 모듈의 기능적 독립성이라고 합니다. 즉 모듈이 하나의 기능만을 수행하고, 다른 모듈과의 과도한 상호작용을 줄이는 것이 기능적 독립성을 높일 수 있는 방법이며, 기능적 독립성이 높을수록 모듈화의 장점들을 더 부각할 수 있습니다. 시스템이 독립성이 높은 모듈들로 구성이 되어야 모듈을 수정하더라도 다른 모듈들에 영향을 최대한 덜 미칠 수..