live the life you love

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마 www.acmicpc.net BFS 문제를 풀어보았다. BFS는 큐를 사용해서 탐색을 구현하는 것으로 알고 있었는데 어떤식으로 큐에 넣어야 할 지 감이 잘 안잡혔다. ..

다익스트라에 대한 문제를 우선순위 큐를 사용하여 풀어보았다. 우선순위 큐는 최대 힙의 구조를 가지고 있는데, 최소 비용을 탐색해야하기 때문에, 비용 값을 음수화 하여 힙에 넣었다. 이 코드는 내가 구현한 코드가 아니라https://jaimemin.tistory.com/555 의 코드를 참고하였다. 함수의 형태가 void나 int가 아닌 vector를 사용하였는데 이런식의 코드 구현은 처음해봤다. return값을 담는 부분을 유의해야 할 것같다. 우선, 전역변수는 다음과 같이 선언하였다. #include #include #include const int MAX = 20001; const int INF = 987654321; using namespace std; int V, E, K; vectorgraph[..

그래프 문제 중 사이클의 개수에 대한 문제이다. 생각보다 어렵지 않게 구현했는데 사이클의 개수를 구하는 부분이 조금 어려웠다. 1 3 5 7의 사이클 개수는 1개인데 방문할 때마다 체크 하면 값이 4가 나오고 그랬다. 특히 재귀에 대한 부분을 해결하는게 관건이었다. 처음엔 void dfs로 했는데 int dfs로 구현하여 return 값을 통해 구해야 할 부분만 구하고 종료시키는 방법을 선택하였다. 입력 int size; cin >> size; int n; for (int i = 1; i > n; graph[i].push_back(n); } 처음에 입력받는 것에 잘못 접근해서 조금 헤맸었다. 입력 값을 정렬하여 새로운 벡터에 넣고 서로 이어줘야 하는지 생각했었다. 하지만 그럴 필요 없이 1,2,3..N번..

덱(Deque)을 사용하는 문제 중 하나. 문제를 이해하는데는 많이 어렵지 않았지만, 배열의 입력이 [1,2,3] 으로 들어오는 것을 처리하는게 까다로웠다. 빈 배열이 입력되는 경우 덱의 자료형이 int이기 때문에 원소 사이사이 쉼표를 넣고 마지막 원소에는 쉼표를 넣지 않는 처리 ex) [1,2,3,] 이렇게 되지 않도록 또한, 'R' 입력의 경우 실제로 덱을 reverse 하는것이 아니라 flag 변수를 선언하여 배열이 reverse 상태인지 확인만 시켜주어야 시간초과가 안난다. 테스트 케이스가 첫줄에 주어지는 문제여서 사용한 변수들의 초기화도 중요한 부분이다. 이 문제에서는 덱만 초기화 시켜주면 되었다. 처음에 문제를 풀때 덱의 자료형을 'char'로 선언하였다. 이렇게 하면 숫자가 두자리 숫자일 때..

기존의 백준 문제들과는 달리, 테스트케이스의 개수가 주어지다 보니 사용했던 벡터, 배열의 초기화가 필요했다. 코드에는 graph[j].clear()로 되어있지만, 처음에는 graph->clear()로 나와서 어떤게 문제인지 고민했다. 이분그래프란 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 2가지 색으로만 칠할 수 있는 그래프이다. [문제 해결 방법] color 배열을 만들어서 방문 정점, 정점과 이어진 정점의 숫자를 다르게 하여 설정하였다.(빨강 = 1, 파랑 = 2) 초기화 : 0 첫 정점 방문시 : 1 color가 1인 정점과 연결된 정점 : 2 color가 2인 정점과 연결된 정점 : 1 정점이 100개 이어져 있다고 해도, 1~4번 정점 사이에 이분그래프가 만들어지지 않으면 절대 이분그..

https://www.acmicpc.net/problem/1152 1152번: 단어의 개수 첫 줄에 영어 대소문자와 띄어쓰기로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 띄어쓰기 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 문자열의 앞과 뒤에는 공백이 있을 수도 있다. www.acmicpc.net getline(cin, str)을 사용해볼 수 있는 문제였다. "Hello world"와 같은 입력을 받는 경우 cin>>str을 하면 str에는 Hello 까지만 담기게 된다. getline의 경우 공백을 포함하여 입력을 받기 때문에 공백이 있는 문자열 처리에 사용하기 좋다. [문제 해결 방법] 공백의 아스키 코드값인 32를 확인하여 단어의 개수..

다음은 소스코드 이다. 12345678910111213141516171819public class DP_RGB_Street_1149 { public static void main(String[] args) { int R = 0, G = 1, B =2; // 빨 , 파, 초 순서 Scanner sc = new Scanner(System.in); int n = sc.nextInt(); // 집의 수 : 반복 횟수 int[][]arr = new int[n][3]; // 집을 칠할때 드는 비용. 맨 마지막 칸은 최종합 arr[0][R] = sc.nextInt(); arr[0][G] = sc.nextInt(); arr[0][B] = sc.nextInt(); for(int i=1; i

백준 온라인 저지 9095번(Java) 출처 : https://www.acmicpc.net/problem/9095 동적계획법(DP)를 연습하기위해 기초 문제를 풀어보았다. 재귀를 활용한 동적계획법으로 풀기 위해서 두 가지 관점으로 접근해보았다. 첫번째, 전체 문제를 부분 문제로 나눌 수 있을까? 두번째 , 재귀 함수를 이용하기 위해 규칙을 찾고 이를 통해 점화식을 구할 수 있을까? 노트에 끄적끄적이다보니 어느정도 실마리를 찾을 수 있었다. 예를들어 n = 4일 경우 1+1+1+11+1+2 1+2+1 2+1+12+21+3 3+1 의 총 7가지이다. 또 n = 5일 경우 1+1+1+1+1 1+1+1+2 1+1+2+1 1+2+1+1 2+1+1+11+1+3 1+3+1 3+1+12+2+1 2+1+2 1+2+2의 ..

백준 9012번 괄호검사 소괄호만을 이용하여 괄호검사를 하기 때문에 비교적 쉬운 문제에 속한다.1. 문제 조건 분석먼저 첫 줄에 들어오는 숫자가 만큼 괄호를 반복해서 입력받는다. 입력받은 괄호 문자열이 올바른 괄호의 구성이면 YES, 그렇지 않으면 NO를 출력한다. 2. 변수 선언num : 첫 줄에서 입력받은 숫자. num 길이 만큼의 배열이 생성ps 배열 : 입력받은 숫자만큼 괄호를 담을 배열ps 배열은 다음과 같이 생성된다.(())()) (((()())() (()())((())) ((()()(()))(((())))() ()()()()(()()())() (()((())()( ans 배열 : YES 또는 NO를 담을 배열. ps배열을 괄호검사 하여 ps[0]이 올바른 괄호이면 ans[0]에 YES 입력 ..

달팽이 문제란 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 와 같이 숫자가 시계방향으로 돌아가면서 바깥부터 안쪽으로 채워지는 형태의 2차원 배열을 구현하는것을 의미한다. 숫자는 어차피 1씩 증가하면서 배열에 저장되므로 중점을 두고 보아야 할 부분은 '배열의 index'이다. 편의상 배열의 index는 arr[i][j]로 한다. 달팽이 문제는 크게 다음과 같은 두가지 관점으로 볼 수 있다. 가로(width)부분은 j값의 증감 세로(length)부분은 i값의 증감 1set를 시작지점에서 가로 혹은 세로의 끝 지점까지 간다고 볼 때 각 set는 다음과 같다. 0~5까지를 보면 arr[0][0], arr[0][1] , arr[0][2], ..