CSE 전공노트

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 난이도: 골드 3 사용언어: JAVA 풀이 겹쳐지지 않는 최대의 경우의 수를 묻는 문제이기 때문에, i 번째까지의 포트들을 겹쳐지지 않게 연결하는 최대 개수는 i보다 낮은 번호의 포트들을 겹쳐지지 않게 연결하는 최대 개수에 자기 자신을 포함하여 +1을 해주는 것입니다. 하지만 아무리 최대 개수라도 자신과 겹쳐지는 경우는 배제를 해..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 난이도: 골드 4 사용언어: JAVA 풀이 기본적으로는 BFS를 이용해 문제를 해결할 수 있습니다. 단지 불과 상근이의 위치를 모두 탐색해 주어야 하므로, 큐와 BFS 함수를 따로따로 만들어주었습니다. BFS에 관한 설명은 아래 문제의 풀이에서 확인하실 수 있습니다. jooona.tistory.com/63 [BOJ] 2178 - 미로 탐색 -개인적인 풀이일 뿐,..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 난이도: 골드 4 사용언어: JAVA 풀이 이 문제는 두 개의 포인터를 이용하여 해결할 수 있습니다. 수열에서 연속된 수들의 부분합 중에 그 합이 S를 넘는 것 중, 가장 짧은 것을 찾는 것이 문제이기 때문에, 연속된 수들의 첫 부분과 마지막 부분을 포인터로 가리키고, 이 두 포인터를 적절히 증가시키며 최소 길이를 구할 수 있습니다. ..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 난이도: 골드 4 사용언어: JAVA 풀이 이 문제는 다이나믹 프로그래밍을 이용하면 비교적 어렵지 않게 해결할 수 있습니다. 한 작업이 시작되기 전에 완수되어야 할 여러 작업들을 입력으로 받아서, 해당 작업들이 완료되는데 걸리는 시간들을 확인하여 가장 늦게 끝나는 작업의 시간에 자신의 작업 시간을 더해서 dp 배열에 추가해주면 됩니다. t라..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 난이도: 골드 5 사용언어: JAVA 풀이 언뜻 보기에는 bfs로 풀 수 있을 것 같은 문제이지만, 특히 JAVA를 이용해 bfs로 구현을 하면 메모리 초과, 또는 시간 초과가 뜰 확률이 굉장히 높습니다. 이 문제는 bfs 대신 다이나믹 프로그래밍을 이용해 해결할 수 있습니다. 우선 arr라는 배열에 입력으로부터 행렬을 받아 넣습니다. 그리고 arr[i][j]를 오른쪽 아래 꼭짓점으로 하는 정사각형의 한 변의 길이를 d..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 난이도: 실버 4 사용언어: JAVA 풀이 이 문제는 스택을 이용하여 해결할 수 있습니다. 자신보다 오른쪽에 있는 수 중에 자신보다 크고 가장 왼쪽에 있는 수를 찾는 문제이기 때문에, 배열의 가장 뒤에서부터 반복문을 돌며 자신보다 크고 가장 왼쪽에 있는 수를 스택에 저장하는 방법을 사용하였습니다. 아래의 예시를 이용해 설명해보도록 하겠습니다. 우선 스택에 가장 오..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 난이도: 골드 5 사용언어: JAVA 풀이 이 문제는 다이나믹 프로그래밍으로 접근할 수 있습니다. 상황에 따라 옮길 수 있는 위치가 다 다르므로 (직각으로 꺾을 수 없다던지...), 배열을 3개 선언하여, 오른쪽 칸으로 보내줄 수 있는 경우의 수, 아래쪽 칸으로 보내줄 수 있는 경우의 수, 대각선으로 보낼 수 있는 경우의 수..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 www.acmicpc.net/problem/2636 2636번: 치즈 첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수로 주어진다. 세로와 가로의 길이는 최대 100이다. 판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진 www.acmicpc.net 난이도: 골드 5 사용언어: JAVA 풀이 이 문제는 BFS를 이용하여 해결할 수 있습니다. BFS에 관한 설명은 아래 문제의 풀이에서 확인하실 수 있습니다. jooona.tistory.com/63 [BOJ] 2178 - 미로 탐색 -개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 설명 www.acmicpc.net/problem/2178 217..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 설명 www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 난이도: 골드 5 사용언어: JAVA N개의 높이가 모두 서로 다른 탑들이 일렬로 줄지어 있습니다. 각각의 탑들은 모두 좌측을 향해 꼭대기에서 레이저를 발사합니다. 이때, 특정 탑에서 쏜 레이저는 좌측에 있는 자신보다 높은 탑들 중 가장 가까운 탑에 수신될 것입니다. 만약 수신되는 탑이 없다면 0을 출력하고, 그 외의 경우에는 각 탑에서 쏜 ..

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다. 문제 설명 www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 난이도: 골드 5 사용 언어: JAVA 적록색약은 빨간색과 초록색을 구별하지 못합니다. 그래서 적록색약인 사람이 그림을 보면 일반인이 보는 것과는 조금 다를 수 있습니다. NxN 크기의 그림에 빨강, 초록, 파랑 세 가지 색을 이용해 색칠이 되어 있습니다. 그리고 이 색깔들에 의해 구역이 나누어져 있습니다. 같은 색깔들끼리 뭉쳐있으면, ..