사이트명 백준 문제 링크 www.acmicpc.net/problem/17142 주요 알고리즘 조합, BFS 사용 언어 Java 자바 알고리즘이 낯선 사람들을 위해 생각 노트를 같이 두었습니다. 1. 문제 2. 입력 / 출력 🧶 Check Point - 풀이 알고리즘의 결정 1. 바이러스 개수는 최대 10개 = 10C5 조합 결과 250개 2. 최대 칸 수 50칸 = 50^2 그래프 탐색시 최대 걸리는 시간 2500 ===> 완전 탐색으로 가능 - 출력 값 출력이 결국 모든 칸에 바이러스가 있게 되는 최소 시간. 따라서 칸과 시간을 중점으로 체크해야 한다. 3. 풀이 3-1. 생각 노트 1. 바이러스(2)인 수를 전부 virusList에 넣기 2. nCm 의 형식으로 모든 경우에 대한 조합 생성 3. 조합..
사이트명 백준 문제 링크 www.acmicpc.net/problem/16236 주요 알고리즘 시뮬레이션, BFS, 사용 언어 Java 자바 알고리즘이 낯선 사람들을 위해 생각 노트를 같이 두었습니다. 1. 문제 2. 입력 / 출력 3. 풀이 3-1. 생각 노트 골드4의 아기상어 문제. 일단 삼성의 주요 기출 형태(구현) 중 하나이다. 조합같은 개념이 적용되진 않아서 어려운 편은 아니다. 그저 문제를 잘 읽고, 그대로 잘 구현 하면 된다. 3-2. 변수명 변수명 설명 Class Fish 물고기들의 시간값(거리)를 기록하기 위한 객체 ArrayList feedList 식사 가능한 경우 들어가는 후보 먹이 리스트! 추후 정렬을 통해 어느것을 먹을지 결정한다. Queue q 이동 가능한 경우에 들어가는 이동 대..
사이트명 백준 문제 링크 www.acmicpc.net/problem/1260 주요 알고리즘 그래프, DFS, BFS 사용 언어 Java 자바 설명이 장황합니다.. 도움되는 것만 파악하세요 :-) 1. 문제 2. 입력 / 출력 3. 풀이 3-1. 생각 노트 이전에 인접 행렬로 풀었던 것을 다시 보며 리뷰를 진행하려 한다. 특히 인접 리스트로 풀 땐, 가장 작은 노드부터 방문한다는 정렬 조건 때문에 고민했는데, 이전에 푼 코드를 보니 정렬에 대한 고민의 흔적이 없었다.. 그 이유는, 이미 행렬의 경우 1부터 순차적으로 접근하기 때문에 작은 노드부터 접근하게 된다. 반면, 리스트의 경우 내가 삽입한 순서대로 들어가기 때문에 정렬이 필요하다. 그림으로 표현하면 아래와 같다. 3-2. 변수명 변수명 설명 int[..
사이트명 백준 문제 링크 www.acmicpc.net/problem/1260 주요 알고리즘 그래프, DFS, BFS 사용 언어 Java 자바 설명이 장황합니다.. 도움되는 것만 파악하세요 :-) 1. 문제 2. 입력 / 출력 3. 풀이 3-1. 생각 노트 이전에 인접 행렬로 푼 문제인데, DFS/BFS를 다시 공부할 겸 이번엔 인접 리스트로 풀려고 도전했다. 인접 리스트가 인접 행렬보다 시간도 적게 걸리는 이유도 있고, 리스트 형식으로 푸는 걸 연습하고 싶었다. *참고로 시간복잡도는 다음과 같다. 인접 행렬 : 간선 개수와 무관하게, O(V^2) 인접 리스트 : O(V+E) 풀이 과정은 기본적으로 다음과 같다. 1. 간선 리스트 배열 생성 -> 초기화 2. 간선 리스트에 양방향으로 노드 넣기 3. DFS..
사이트명 백준 문제 링크 www.acmicpc.net/problem/2252 주요 알고리즘 위상 정렬, 그래프 사용 언어 Java 자바 설명이 장황합니다.. 도움되는 것만 파악하세요 :-) 1. 문제 2. 입력 / 출력 3. 풀이 3-1. 생각 노트 맨 처음 단순히 for문을 이용하여 문제를 해결하려 했다. 문제에서 크다/작다로 입력되는 모든 수를 카운팅(크면 +, 작으면 -)하고, 최종적으로 카운팅 된 수 크기대로 출력하는 방식을 생각했다. int[][] height = new int[N][2]; for (int i = 0; i < N; i++) { height[i][0] = i; } for (int i = 0; i < M; i++) { int t = sc.nextInt(); int s = sc.nex..
사이트명 정올 문제 링크 jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1775&sca=2050 주요 알고리즘 #문자열탐색 사용 언어 Java 자바 설명이 장황합니다.. 도움되는 것만 파악하세요 :-) 1. 문제 2. 입력 / 출력 3. 풀이 3-1. 생각 노트 타겟이 되는 문자열을 char[] 배열에 넣고, 그 갯수만큼 추가로 for문을 돌면서 맞는지 체크한다! 여기선 KOI, IOI 둘다 O I 여서 그냥 target 배열 하나만 만들어서 2회만 돌렸다. 다만, 맞을 때마다 i 값을 증가시키고, 아니라면 temp에 저장한 인덱스 값으로 원상복귀 시킨다! 그리고, 문자열이 맞다면 i 값을 하나 줄여서 다시 그 자리부터 체크하도록 한다. 다만, 마지막 문자가 I 혹..
사이트명 정올 문제 링크 jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=944&sca=2060 주요 알고리즘 탐색, BFS, DFS 사용 언어 Java 자바 설명이 장황합니다.. 도움되는 것만 파악하세요 :-) 1. 문제 2. 입력 / 출력 3. 풀이 3-1. 생각 노트 둘레 구하는 공식은 평행 사변형이나 정사각형 처럼 일반적인 도형에나 있지, 복잡한 형태는 없다. 따라서 이 문제는 그래프에서 표현되는 도형 특성상 주위를 둘러싸는 녀석들은 카운팅하면 구할 수 있다는 특징을 캐치해야 한다. 배열에 수를 채워넣고, 주위에 아무것도 없는 것들을 조사하여 그 수를 세는 식으로 하면 된다. 3-2. 변수명 변수명 설명 dx dy 사방 탐색을 위한 int[][] paper 겹..
사이트명 정올 문제 링크 jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=706&sca=2030 주요 알고리즘 #수학 사용 언어 Java 설명이 장황합니다.. 도움되는 것만 파악하세요 :-) 1. 문제 2. 입력 / 출력 3. 풀이 3-1. 생각 노트 A, B, C의 곱을 String으로 변환한다. 해당 문자열을 toCharArray()를 통해 char배열에 넣는다. 하나씩 값을 보며 해당 정답 변수의 개수를 카운팅한다. 끝. 🌟 중요 1. String과 int 서로간의 형변환 String -> int Integer.parseInt(문자열); int -> String Integer.toString(숫자); char -> int char 문자 - '0'; 중요한 건, ..
사이트명 정올 문제 링크 jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=931&sca=2030 주요 알고리즘 #수학 사용 언어 Java 설명이 장황합니다.. 도움되는 것만 파악하세요 :-) 1. 문제 2. 입력 / 출력 3. 풀이 3-1. 생각 노트 최대공약수 GCD : 두 수의 약수 중에서 가장 큰 수 최소공배수 LCM : 두 수의 배수 중에서 가장 작은 수 우선, 최대공약수는 유클리드 호제법과 for문으로 처음부터 찾는 방식이 있다. - 유클리드 호제법은 나머지연산(%)을 활용하는 것으로, 나머지가 0이 될 때까지, 나머지와 그 전 수를 계속 나누는 방식이다. - 노동으로 찾는 방법은 1부터 N까지 나누었을 때, 두 수 모두 나머지가 0이 되어 약수가 되는 수를..
사이트명 정올 문제 링크 jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=767&sca=2020 주요 알고리즘 #구현 사용 언어 Java 설명이 장황합니다.. 도움되는 것만 파악하세요 :-) 1. 문제 2. 입력 / 출력 3. 풀이 3-1. 생각 노트 행(= 커서)이 바뀌는 걸 바깥 for문으로 안에 하나씩 증감하며 옮기는 줄 부분은 c라는 변수로 횟수 카운트! 배열에 접근하는 변수 [i][j] 를 변수값의 변화에 따라 접근시킬지 맨 처음엔 1번, 그담엔 2번, 3번 ... 하는 횟수에 따라 접근시킬지를 정해야 한다..? 3-2. 변수명 type 변수명 설명 int[][] arr 결과값 int text 내부에 숫자를 기록하기 위한 변수 int cnt 몇 번 째로 체크..
사이트명 정올 문제 링크 jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=914&sca=2020 주요 알고리즘 #for #구현 사용 언어 Java 설명이 장황합니다.. 도움되는 것만 파악하세요 :-) 1. 문제 2. 입력 / 출력 3. 풀이 3-1. 생각 노트 2번과 3번의 경우, 시작 점이 어디인지를 파악하고 그 후에 몇 회 실행시키는지를 결정한다. 둘다 시작점이 (0,0) -> (1,1) -> (2,2) -> ... 이고, 그 때를 기준으로 5회 -> 3회 -> 1회 식으로 줄어든다. 이걸 카운트하기 위해, for문 안에 int c를 선언해서 사용한다. 3-2. 변수명 type 변수명 설명 int[][] arr 결과값을 넣는 배열 -> 나중에 출력해서 최종 정답 ..