begong블로그

dfs를 활용한 구현문제 로직상으로는 bfs로 풀어도 상관없을 듯 하나, visit처리를 하기 힘들어 dfs로 구현하였다. 한칸씩 이동하며 모든 도형을 검사해야한다. 바로 인접한 칸으로 이동하면서 4칸을 이동하면 된다. 4칸째 이동하면 그간 지나친 경로의 숫자를 다 더한것과 max를 비교하여 max를 갱신한다. ㅗ모양의 블럭은dfs로 해결이 안되어 해당 지점의 상하좌우에있는 블럭들을 모두 더한 뒤 하나씩 빼면서 최대치를 체크한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; class Main { static int[][] ..

처음 접근 방법 : 가장 긴 감소하는 부분순열 - 서류심사 등수, 면접 등수가 주어지기 대문에 배열의 index를 서류심사 등수로, 면접등수를 배열의 값으로 넣어주어 가장 긴 감소하는 수열을 찾으면 될 것 같았다. => 시간초과 n^logN 다음 접근 방법 : 위의 방식과 같이 서류심사 등수로 정렬을 한다(등수를 배열의 index로 활용하기때문에 입력을 받으며 정렬이 된다) 1등의 면접등수를 min으로 기록하고, 그 값보다 작은 값들만 추린다. min값보다 값이 작다면 answer에 1을 더해주고 min값을 해당 값으로 바꿔준다.(이렇게되면 1등보다 면접등수가 낮고, 서류심사등수가 높은 사람만 선택됨) import java.io.BufferedReader; import java.io.IOException..

자바의 여러기능을 잘 아는지 테스트하는 문제였다. parsing하는것이 주요 관건 import java.util.*; class Solution { public int[] solution(String today, String[] terms, String[] privacies) { int count = 0; boolean[] check = new boolean[privacies.length]; HashMap map = new HashMap(); StringTokenizer st; for(String s : terms){ st = new StringTokenizer(s); String key = st.nextToken(); int value = Integer.parseInt(st.nextToken()); m..

bfs문제 다른 문제와 다르게 방향과 이동 칸까지 맞춰줘야해서 조금 까다로울 수 있다. 풀이방법은 방향별로 visit을 만들어, 해당 위치와 방향을 방문하였는지 체크하면 된다. 이동 칸의 경우 한칸 앞에서부터 검사를 하여, 칸이 막혀있기 전가지만 큐에 넣어주면 된다. 최소명령으로 이동하는 것 이기때문에 우선순위 큐 를 사용해서 자동정렬시켜준다. 90도씩만 고개를 돌릴 수 있기때문에 이것또한 신경써야한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.StringTokenizer; class Main ..

https://school.programmers.co.kr/learn/courses/30/lessons/118668 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 처음 접근 방식: 1. 반복문을 돌며 최대 필요한 alp,cop를 구한다 => alpMax, copMax 2. alp,cop가 시작점이 된다. 3. 반복문을 돌며 i,j에서 문제를 풀면 도달할 수 있는 위치에 비용을 기록한다. (각각 공부하는 +1 에도 기록한다) 이 때, 배열을 충분히 크게 만들어, 목표치에 초과할 경우도 기록할 수 있게 한다. 4. alpMax,copMax보다 큰 배열의 범위..

구현문제 문제에 로직이 다 나와있어서 구현을 어떻게 하느냐가 중요한 문제이다. 톱니바퀴끼리 바라보는것을 검사하고, 조건이 만족하면 돌리면된다. 나는 큐를 두개로 나누어 돌릴바퀴의정보를 담는 큐, 탐색을 위한 큐를 만들었다. 이렇게 한 이유는 톱늬를 미리 돌려버리면 조건을 검사하기 상당히 까다롭기때문에 검사를 마친 뒤 톱니바퀴를 한번에 돌리기 위해서이다. 톱니를 돌리는 것은 간단하게 배열을 이용했다. 길이가 8이라서 굳이 다른 자료구조를 이용할 필요가 없을것이라 생각했다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import jav..

간단한 bfs문제 단 불이 번지는것을 어떻게 처리하냐가 관건이다. 처음에는 불이 도달한 배열 (일반적인 bfs문제의 visit배열과 같다), 지훈이가 방문한 노드를 저장하는 배열을 만들어 처리했지만, 다시 생각해보니 굳이 두개를 분리하지말고, 지훈이가 불이 번진곳에 도달 할 수 없게 visit배열을 하나만 만든뒤 불이도달했을때 visit처리를 하면 된다는 것을 발견했다. 지훈이와 불이 겹칠 수 없으니 불의 이동을 먼저 한 후 지훈이를 이동시킨다. 자료구조에 몇번째 이동인지 기록하는 count를 만들어 count에 따라서 절차가 진행되게 만들었다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamRead..

BFS문제 단순하게 BFS만 할것이 아니라 언제 토마토가 다 익는지까지 구해야된다. 내가 생각해낸 방법은 탐색을하면서 몇번째로 익는지 따로 기록하는 것이다. 그렇게 되면 마지막으로 익는 (마지막에 탐색되는) 토마토에 기록된 숫자를 보여주기만 하면 끝이다. 처음에 입력을 받으며 안익은 토마토의 개수를 구해놓고, 탐색을 하며 감소시킨다. 큐가 비었을때, 남은 토마토가 있다면 -1을 출력한다. (이부분은 visit을 활용하여 구할 수도 있을것이다.) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; class Main { public ..

그리디 알고리즘 문제 이문제의 접근방법은 앞에서부터 탐색할 것이 아니라, 뒤에서부터 탐색을 하는것이다. 매수점을 찾아 기준을 잡고, 그 앞의 매입점들과의 차이를 구해서 더해주면 된다. 마이너스가 될 일은 없다. 뒤에서부터 탐색을해 항상 최대치를 기준으로잡기때문에 조금이라도 높을때엔 사지않는다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedR..

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; class Main { static int N, M, K; static ArrayList[] graph; static int[] group; static int[] relate; static boolean[] isError; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamRea..