2JINISHAPPY 2JINISHAPPY

www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 미로 만들기 문제 2차원 배열에서의 최단거리 문제이다. 벽부수고 이동하기와 미로만들기처럼 벽(cost가 높은 좌표)를 최소화해서 목적지에 도착하기 위해서는, 가중치 그래프의 최단거리를 이용해야 한다 따라서 2차원 배열에 다익스트라 알고리즘을 적용하면 문제를 해결할 수 있다 문제에서는 흰색(지나갈 수 있는 곳)을 1, 검은색을 0으로 해줬는데 입력받은 뒤 이를 완전히 뒤집고 다익스트라 알고리즘을 통해 (N,N)으로 갈 ..

www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 1. 문제 정의 N줄에 걸쳐 3개의 숫자 중 최대 점수를 얻을 수 있는 숫자를 선택한다. 단, 이전에 선택했던 열과 인접한 열에 있는 숫자만 선택 가능하다. 2. Recursion&Subproblem K-1번째 줄에서 1번을 선택했다면 K번째 줄에서 1, 2번 중 큰 숫자를 선택한다 K-1번째 줄에서 2번을 선택했다면 K번째 줄에서 1,2,3번 중 큰 숫자를 선택한다 K-1번째 줄에서 3번을 선택했다면 K번째 줄에서 2,3번..

www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 1. 문제 정의 좌표 평면 내의 1로 이루어진 가장 큰 정사각형의 넓이를 출력한다 이 때, 넓이를 구하기 위해 가장 큰 정사각형의 한 변의 길이를 구한다 위와 같은 그림에서 최대 정사각형의 한 변의 길이는 2이므로, 답은 4이다 2. Subproblem&Recursion 특정 좌표를 오른쪽아래 꼭지점으로 정사각형의 길이를 구한다고 할 때, 이 좌표의 북, 서, 북서쪽 좌표는 반드시 1이어야 한다. 그리고 좌표가 아래와 같을 경우, 0111001 -> 0111001 0111001 -..

www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 이차원 배열을 이용하는 DP문제 욕심쟁ㅇㅣ 판다🐼 1. 문제 정의 이차원 배열에서 특정 칸에서 연결된 상하좌우의 칸이 인접하다고 할 때, 인접한 칸이 현재 칸보다 숫자가 큰 최대 연결 회수 구하기 2. Recursion & Subproblem 4 14 9 12 10 1 11 5 4 7 15 2 13 6 3 16 8 위의 예시에서, 5의 최대 연결 수는 5-11-15로 3번이다. 이 때, 2의 최대 연결..

1. 한 메서드에서의 indent는 1로 제한한다. - 한 메서드에서 2중 for문 같이 반복문과 제어문을 혼용해서 쓰는 것 보다는, 메서드를 분리한다. - 메서드를 분리했을 경우 하나의 메서드가 맡고있는 일이 더욱 세분화되고 리팩토링 시 용이하다. 2. else 예약어를 지양한다. - else 예약어가 많아지면 indent도 증가하고 가독성도 좋지 않다. - guard clause, ealry return을 이용하면 else 예약어의 사용을 줄일 수 있다. 3. 모든 원시값과 문자열을 포장한다. - class도, enum도 가능하다. - 사실 프리코스를 할 때는 이 부분에 대해서 명확하게 이해를 하지 못 했는데, 이제 알 것 같다. - 특정 메서드에서 매개변수로 String형 변수를 받아왔을 때, 이 ..

MST는 그리디 알고리즘을 이용해서 구할 수 있는 트리의 한 형태이다. 연결 그래프(하나의 Connected Component로 이루어진 그래프)에서 생성할 수 있는 부분 그래프이기도 하다. 그래프의 형태를 한 네트워크 회선이 존재할 때, 네트워크 구축 비용을 최소로 하는 경우의 수를 찾고 싶을 때 쓰이기도 한다. 그래프 G=(V,E)와 같고, 각 edge에 weight가 주어져 있을 때, 아래의 두 조건을 만족하는 G'( V(G), T )가 MST이다. 1️⃣ G'은 Connected하다. 2️⃣ G'은 포함할 수 있는 edge들의 cost 총 합을 최소로 한다. 해당 그래프에서는 연두색으로 칠해진 edge들을 선택했을 때 모든 vertex를 포함할 수 있으면서, cost의 합을 최소로 할 수 있기 때..

이번 싸피 5기에 지원을 하게 되었다 주변에 싸피 1기, 3기, 4기를 해왔던 선배들이 꽤 있었기때문에 옛날부터 관심이 많은 상태였다. 마음놓고 공부할 수 있는 환경이 조성된다는 점에서 가장 끌렸다 나는 공부할 때 환경을 많이 타기 때문에, 주위에 열심히 공부하는 사람들을 보면서 자극 받고 싶었다 싸피에서 지원해주는 취업지원서비스를 통해서 자기소개서랑 포트폴리오 컨펌도 받고싶다 또 혼자 취준할 때는 아르바이트와 취준을 겸해야 하는데, 싸피는 돈을 쌓아둘 수 있기 때문에 장기적으로도 이득이라고 생각한다 1. 서류 지원 기본 에세이는 ①SW에 관심을 갖게 된 계기&어떤 개발자가 되고싶은지 ②취업 목표로 한 활동&그것을 통해서 느낀점 이 두가지 항목으로 이루어져 있다. 기업 지원은 '나는 천재고 무슨 일을 시..

www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 바이토닉 부분수열은 가장 긴 증가+감소 수열을 섞은 문제이다 맨 앞부터 가장 긴 증가 수열을 구하고, 맨 뒤부터 가장 긴 증가 수열을 구하면 i번째 원소에 대해 (현재 원소를 포함하는 가장 긴 증가 수열의 길이, 현재 원소를 포함하는(맨 뒤부터) 가장 긴 감소 수열의 길이)를 구할 수 있다 for문을 두번 돌아준 뒤 해당 값들의 합이 가장 큰 쌍을 찾아주면 되는 문제 #include int n,dp[3][1001],ans; int..