class 6https://www.acmicpc.net/problem/13334   # 문제  # 필요개념배열에 담아서 정렬하면 편한 문제겠지만 시간이 1초라서 O(n^2) 가 되면 시간초과가 발생한다. 혹시나 해봤지만 역시나이니 시도하지 않아도 된다. 이렇게 일정 간격을 순회해야 할 경우 투포인터를 응용하여 문제를 풀 수 있다. 이 문제는 일정 간격(dis) 안에 집과 회사가 모두 들어있는 루트의 개수를 구해야 하는 문제이다. 푸는 기본적인 로직은 다음과 같다.입력받은 수를 저장할 이차원 배열과 실제 문제풀이에 이용할 리스트를 각각 생성한다.숫자 두개를 입력받되, 작은 것을 집, 큰 것을 회사라고 가정한다. 입력을 받을 때 작은 숫자가 앞에 오지 않는 경우도 있기 때문에 애초에 배열에 저장할 때 min..

class 6https://www.acmicpc.net/problem/14725   # 문제# 필요개념이 문제는 결론적으로 노드들의 깊이를 오름차순으로 도출해야하는 문제이기 때문에 dfs를 사용하였다. 평소 그래프 문제를 풀 때에는 이중 리스트를 만들어 풀었지만, 이 문제는 이름이 같은 노드가 존재할 수 있고, 깊이라는 개념이 도입되기 때문에 이중리스트로 풀지 않았다.  A노드의 자식노드인 B노드에게 C라는 자식노드가 존재한다고 가정할 때, A노드에게 C라는 자식노드가 있을 수 있다. 이 두 노드는 이름만 같을 뿐, 아예 다른 노드이기 때문에 그래프문제처럼 풀면 안 된다. Node라는 클래스를 만들고, 여기에 자신의 값과 children을 넣어주었다. children에 값을 추가하는 것은 별도의 메소드 ..

알고리즘 분류 (그래프 탐색)https://www.acmicpc.net/problem/7569   # 문제 # 필요개념지금까지 했던 2차원 배열 탐색과 달리, 토마토가 들어있는 3차원 상자를 탐색해야 한다. 그래서 삼차원 배열을 생성해주었다. 지금까지 BFS로 그래프탐색을 할 때 방문 여부를 확인하는 isVisit 배열을 생성했었는데, 이 문제는 애초에 전체 토마토를 익게 할 수 있는 "시간" 을 물어보고 있기 때문에, 시간을 넣어줄 배열(map)을 생성해주었다. 토마토 입력이 0인 자리에 초기값을 -1로 설정해주어서 -1이면 방문하지 않은 곳임을 알 수 있도록 했다. 모든 익은 토마토들은 동시에 주변을 익게 만들기 때문에, 입력이 1인 토마토들을 일단 모두 Queue에 담고, 다 담은 후에 bfs 탐색..

알고리즘 분류 (dfs)https://www.acmicpc.net/problem/1707  # 문제  # 필요개념이 문제를 풀기 위해서는 이분 그래프의 개념에 대해 먼저 이해해야한다. 개념 공부를 제대로 하지 않고 접근했다가 내 정답률만 잔뜩 낮춰버렸다 😇 그래서 개념 정리겸 블로그 작성 완료 ! 아래 링크를 걸어두었다https://wanna-developer02.tistory.com/191 [Data Structure] Bipartite Graph (이분 그래프) | 자바백준 문제를 풀다가 처음보는 자료구조를 정리하려고 한다. "이분" 이라는 단어가 들어가는 자료구조들이 꽤 있는 만큼, 개념을 헷갈리지 않게 정리하는 것도 중요하지 않나 싶다. 순서는 간단wanna-developer02.tistory...

알고리즘 분류 (dfs)https://www.acmicpc.net/problem/1520   # 문제여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아..

class 6https://www.acmicpc.net/problem/2533   # 문제페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망에서 사람들의 친구 관계는 그래프로 표현할 수 있는데,  이 그래프에서 사람은 정점으로 표현되고, 두 정점을 잇는 에지는 두 정점으로 표현되는 두 사람이 서로 친구 관계임을 표현한다. 예를 들어, 철수와 영희, 철수와 만수, 영희와 순희가 서로 친구 관계라면 이를 표현하는 친구 관계 그래프는 다음과 같다.  친구 관계 그래프를 이용하면 사회망 서비스에서 어떤 새로운 아이디어가 전파되는 과정을 이해하는데 도움을 줄 수 있다. 어떤 새로..

class 6https://www.acmicpc.net/problem/2357   # 문제N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자.여기서 a번째라는 것은 입력되는 순서로 a번째라는 이야기이다. 예를 들어 a=1, b=3이라면 입력된 순서대로 1번, 2번, 3번 정수 중에서 최소, 최댓값을 찾아야 한다. 각각의 정수들은 1이상 1,000,000,000이하의 값을 갖는다.  # 예제입력 :  첫째 줄에 N, M이 주어진다. 다음 N개의 줄에는 N개의 정수가..

단계별 문제풀이 23단계 (동적계획법1)https://www.acmicpc.net/problem/11054   # 문제수열 S가 어떤 수 Sk를 기준으로 S1    > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만, {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.  # 예제입력 :  첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄..

단계별 문제풀이 (23단계)https://www.acmicpc.net/problem/2565   # 문제두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다.예를 들어, 과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. 전깃줄이 전봇대에 연결되는 위치는 전봇대 위에서부터 차례대로 번호가 매겨진다. 전깃줄의 개수와 전깃줄들이 두 전봇대에 연결되는 위치의 번호가 주어질 때, 남..

알고리즘 분류 (dp)https://www.acmicpc.net/problem/2293   # 문제n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.  # 예제입력 :  첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다.3 10125  출력 :  첫째 줄에 경우의 수를 출력한다. 경우의 수는 231보다 작다. 10 # 필요개념n이 100 이하, k..