본문 바로가기

알고리즘98

항해99 30일차 TIL(설탕배달 / 백준) 문제         https://www.acmicpc.net/problem/28391 번째 시도   5킬로그램 봉지가 0개에서부터 5킬로그램 봉지의 최대 개수까지 탐색하며 답을 업데이트 한다.만약 답이 한 번도 업데이트 되지 않는다면 정답이 없는 것이기 때문에 -1을 출력한다.// 3, 5킬로그램 봉지가 있다.// 최대한 5킬로그램 봉지를 많이 들고가야 한다.// 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다. import java.util.*;import java.io.*;class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(.. 2024. 4. 29.
스택 문제 판별능력 키우기(with 백준 7문제) 문제1   https://www.acmicpc.net/problem/2800 아이디어'('를 스택에 넣은 후 ')' 만날 때마다 괄호클래스 혹은 이차원 배열에 추가해주기2의 n승(n개의 괄호쌍이 있다, 없다) 의 경우의 수를 어떻게 dfs 재귀함수로 표현할 것인가dfs 함수 안에 괄호 제거한 버전 괄호 포함한 버전으로 dfs 호출 두 번한다.ex) private static void dfs(int idx, int len) { if (idx == len) { print(); return; } if (arr[idx] == '(') { // 여는 괄호를 만나면 해당 괄호와 짝 괄호를 vist배열에 true처리한.. 2024. 4. 28.
항해99 29일차 TIL( 에디터 / 백준) 문제         https://www.acmicpc.net/problem/14061 번째 시도   스택 문제를 골라 풀기 시작했지만 처음 봤을 때 스택 문제라고 생각이 안들었습니다.다른 풀이)ArrayList에 문자열을 담는다. 커서위치를 cInd라는 변수에 담는다cInd가 가르키는 곳에 추가하거나 삭제한다.import java.util.*;import java.io.*;class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String input = br.readL.. 2024. 4. 27.
항해99 28일차 TIL( 쇠막대기 / 자바) 문제         https://www.acmicpc.net/problem/10799 1 번째 시도   import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Stack;public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String s = br.readLine(); int answer = 0; Stack st = new Stack(); .. 2024. 4. 26.
항해99 27일차 TIL( 괄호 / 백준) 99클럽 모의고사를 보고나서 나의 문제점을 발견했다. 문제를 보면 어떤 유형인지 파악하지 못한다는 것이다. 유형을 생각지도 않은 채 무작정 문제를 풀어 생긴 문제라 본다. 알고리즘 문제 별로 푸는 연습을 해야겠다. 오늘은 Stack 문제를 풀어볼 것이다. 문제          9012번: 괄호괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고www.acmicpc.net1 번째 시도   조건에 부합하면 스택에 넣고 차례차례 빼는 느낌의 문제면 Stack문제라 생각하기import java.util.*;import java.io.*;.. 2024. 4. 25.
[프로그래머스] 미로 탈출 명령어 / 자바 문제          프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr1 번째 시도    1. 한 번에 정답 결론내리기 힘드니  정답 루트 다 도출 후 탐색하기2. or 사전순으로 먼저 탐색하기2번이 구현이 쉬으므로 2번 선택 // [아이디어] // d(아래)>l(왼쪽)>r(오른쪽)>u(위쪽)// 위치 비교 후 아래쪽으로 가야 하면 상하 움직임보다 먼저 나오기, 위쪽으로 가야 하면 상하 움직임이 위쪽보다 먼저 나오기// 최소 이동거리와 k는 2의 배수 만큼 차이 나야 한다 아니다면 impossible!// [구현목록]//.. 2024. 4. 24.
항해99 26일차 TIl( 단어 변환 / 프로그래머스) 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1 번째 시도 target -> start로 가는 길 찾기 DFS ? BFS? 이와 같은 단어 찾기 아니면 백트래킹 DFS 최소 횟수이니까 최단 거리? BFS 최소 횟수 = 최단 거리로 판단, BFS 구현 BFS를 이해하기 쉽게 디버깅 넣은 코드 import java.util.*; class Word { String name; int index; int cnt; Word(String name, int index, int cnt) { this.name= name; this.index = index; thi.. 2024. 4. 23.
[프로그래머스] 네트워크 / 자바 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1 번째 시도 DFS 문제 인접행렬 탐색할 때 대각선 기준으로 위 아래 둘 중 하나만 봐도 된다. 이거 구현하려니 머리가 터질 것 같았다 패스 ~ 숫자 0(의미적1)부터 살펴본다. 방문한적이 없다면 answer ++ dfs로 숫자 0 과 관련되어 있는 숫자들을 다 살펴본다. dfs에 거쳐지면 visted = true 해당 노드에 인정행렬을 흝어보며 연관되어 있는 숫자들을 살펴본다(dfs) 즉, 재귀호출 import java.util.*; class Solution { public int solution(.. 2024. 4. 22.
항해 99 25일차 TIL( 게임 맵 최단거리 / 프로그래머스) 문제 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1 번째 시도 DFS 문제 DFS를 통해 동,서,남,북 위치 중 갈 수 있는 곳을 다 탐색한다. 이때 depth로 길이를 알 수 있다. 계속 최소 depth를 업데이트 한다. import java.util.*; class Solution { int[] x = new int[]{1,0,0,-1}; int[] y = new int[]{0,1,-1,0}; boolean[][] visited; int answer = Integer.MAX_VALUE; public int solution(int[][] maps) .. 2024. 4. 22.

티스토리툴바