전체 글122

• [백준 JAVA] 11561 N과 M(3) 백트랙킹 https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net dfs로 m만큼의 깊이만큼 반복한다. 각 깊이에 arr[d]의 값을 가능한 범위 (1~N)까지의 값을 모두 넣고 만약 깊이가 만족되면 stringbuilder에 저장하여 마지막에 출력한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.String.. 알고리즘 2022. 11. 6.

• 

  이진탐색(binary search) 먼저 이진 탐색을 위해서는 내부의 데이터가 정렬되어 있어야 한다. 이진 탐색을 위해서는 시작점 start, end, mid 를 이용하여 탐색한다 찾으려는 데이터와 중간점 위치의 데이터를 비교하며 반복하면서 데이터를 찾는다. 와 같은 과정으로 탐색해 나간다. - python 코드 def binary_search(arr,goal,start,end): if start>end: return None mid = (start+end)//2 if arr[mid]==goal: return mid elif arr[mid]>goal: return binary_search(arr,goal,start,mid-1) else: return binary_search(arr,goal,mid+1,end) def binary_searc.. 알고리즘 2022. 11. 5.

• 

  [백준 JAVA] 16724 피리부는 사나이 백준 자바 16724 피리 부는 사나이 BFS 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net [문제 풀이 방법] 사이클을 따라서 방문 처리되지 않은 원소(0인 원소들) 들을 방문 처리하면서 길을 따라가다가 만약 이전에 방문했던 곳이면 사이클을 따라 safezone이 하나 있어야 하므로 safezone을 하나 증가시켜야 한다 하지만 만약 사이클을 따라가다가 이전에(이번 턴이 아닌) 방문처리가 된 원소라면 이미 이전 턴의 사이클에 safezone이 존재하므로 safezone을 .. 알고리즘 2022. 10. 25.

• 

  [백준 java] 2166 다각형의 면적 백준 boj 2166 다각형의 면적 골드 5 🔗 문제링크 🔗 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 🌟 생각 흐름 🌟 문제를 읽고 다각형의 면적을 구하는 방법이 있을 것 같아 구글링을 했다 아래 페이지를 참조하여 구현하였다. 다각형 넓이 구하기: 15 단계 (이미지 포함) - wikiHow 다각형의 넓이를 계산하는 일은 정삼각형 넓이를 구하는 것처럼 간단하기도 하지만 각 변의 길이가 다른 11각형의 넓이를 구하는 것처럼 복잡하기도 합니다. 다양한 다각형의 넓이를 구하는 방 ko.wikihow.com 위에 페이지에서 참조한 부분.. 알고리즘 2022. 10. 25.

• 

  [백준 java] 2225번 합분해 DP https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net [문제 풀이] arr[a][b] -> a개의 숫자를 이용해서 b를 만들수 있는 경우의 수 1개의 숫자를 이용해서 b를 만들수 있는 경우는 무조건 1개 임으로 1로 초기화 한다. arr[a][b]=arr[a-1][b]+arr[a][b-1] arr[3][2] = 002,020,200,110,101,011 (6) arr[4][1] = 0001,0010,0100,1000 (4) arr[4][2] = 0002,0020,0200, 0110,0101,0011,1001,1010,1100, 2000 (10) arr[3][2]의 앞에 0을 .. 알고리즘 2022. 10. 23.

• 

  [백준 Java]9466_텀프로젝트 [문제 링크] 9466 텀 프로젝트 자바 백준 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net [생각 흐름] 처음에는 for문으로 i에서 모든 경로를 확인하여 사이클을 확인하려 하였는데 시간 초과가 났다. 그래서 O(n)으로 통과할 수 있는 방법을 찾다가 i번째부터 연결된 경로를 따라가다가 사이클이 생기면 처리하는 방식으로 해결하였다. 1) 1->2->3->4->2 와같은 상황이라면 사이클이 생겨서 2번 사람의 전 사람은 혼자 해야 한다. 각 노드를.. 알고리즘 2022. 10. 22.

• 

  [백준 JAVA] 14889 스타트와 링크, 합 이용 [문제링크] 스타트와 링크 실버2 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 팀원이 되는경우 계산하는 부분을 두 가지로 나누어 코딩하였다. [1번 풀이] vistied 되었다면 A팀으로 생각하여 백트랙킹후 이중포문으로 계산 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public .. 알고리즘 2022. 10. 19.

• 

  [백준 Java] 2638 치즈 [문제 링크] boj 2638 치즈 골드 3 자바 https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net [생각 흐름] init 함수에서 배열에서 바깥쪽을 모두 -1로 초기화하고 안쪽에 있는 것과 다르게 표기한다. 이때 만약 치즈가 있는 칸이 하나도 없다면 true를 리턴하여 더 이상 진행하지 않도록 해준다. 이후에 remove 함수에서 치즈가 있는 칸이라면 4면 중 2면이 -1로 노출되어 있는 치즈 인지 확인하고 노출되어있다면 본 배열의.. 알고리즘 2022. 10. 17.

• 

  [백준 JAVA] 1644 소수의 연속합 [문제 링크] 자바 1644 소수의 연속합 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net [생각 흐름] 먼저 에라토스테네스의 체를 이용하여 목표하는 값 이하까지의 소수 배열을 구한다. 이후에 투 포인터를 활용하여 만약 goal 값보다 현재값이 커지면 left를 오른쪽으로 옮기고 , goal 보다 작아지면 right를 오른쪽으로 옮겨 가면서 계산한다.(현재 sum에는 left~right까지의 배열의 합이 들어있다) 만약 목표값과 같으면 cnt를 하나 증가시키고 오른쪽을 증가시키도록 한다 종료시점은 right가 끝에 닿을 때까지 진행하도록 하였다. left를 확인하.. 알고리즘 2022. 10. 14.

• 

  [백준 Java] 10942 팰린드롬? 자바 10942 팰린드롬 dp https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 시간제한이 0.5초이고 메모리 제한이 커서 dp를 이용해서 저장해 두고 테스트 케이스에 대해서 계산된 값을 출력해야겠다고 생각했다. dp 테이블에는 팰린드롬이라면 1을 저장하고 아니면 0을 저장하였다. 포인트라고 생각한 아이디어는 i ~ j 까지가 팰린드롬인지를 확인하기 위해서 input[ i ]와 input[ j ]를 비교하고 i+1과 j-1까지가 팰린드롬 인지를 확인하면 된다. 예를 들어 만약 테스트 .. 알고리즘 2022. 10. 13.

• 

  [백준 java] 2473 세 용액 [문제링크] 자바 2473 세 용액 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 투 포인터를 이용하여 해결하였다. 3가지를 선택하는 경우를 전체 포문을 이용하여 0~n 까지를 기준으로 두고 정렬이 된 배열에서 left(왼쪽 포인트), right(오른쪽 포인트)를 이동하여 가장 작은 값을계산 하였다.(두 용액에서 했던방식과 같음) 만약 temp < 0 이면 left 를 증가시켜서 덜 감소되도록 하고 0 < temp 이면 .. 카테고리 없음 2022. 10. 12.

• 

  [백준 JAVA]13172 시그마 Σ [문제링크] Σ 13172 백준 자바 https://www.acmicpc.net/problem/13172 13172번: Σ 모듈러가 11에서 1,000,000,007이 되어 답이 달라졌지만, 역시 3을 곱한 다음 1,000,000,007으로 나눈 나머지는 7이 된다. www.acmicpc.net [코드] import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { private static final long mod =1000000007; private static long solution(long n, .. 카테고리 없음 2022. 10. 7.