공부 기록장

이 문제는 백준 골드 4 레벨 문제이다. 처음에는 이렇게 풀었는데 시간초과가 났다. O(nlogn)정도 인 것 같은데, O(n) 에 풀어야 하나보다. 이 식은 처음부터 수열을 검사하면서 목표치가 넘으면 cnt에 값을 추가해주고, 다음 번호부터 검사하는 것이다. import java.util.Scanner; public class 부분합_1806 { //시간초과 static long cnt, ans; static int[] map; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); long S = sc.nextInt(); map = new int[N]; for(int i=0; i..

이 문제는 백준 실버 2 레벨의 문제이다. 이 문제는 실버 2임에도 불구하고 뭔가 생각해야 할 것도 많고 되게 까다로웠다. 처음에는 식을 어떻게 세워야 할 지 몰라서 헤매고 있었는데 스터디 같이 하던 오빠가 어떤식으로 풀면 되는지 알려주었다. 1) (나 [와 같은 열리는 괄호가 나오면 스택에 넣어주기 2) 닫히는 괄호가 나왔을 때 스택 제일 위에 있는 것이 짝이 맞는 열리는 괄호라면 2 혹은 3 으로 바꿔주기 3) 열리는 괄호가 아니라면 스택을 검사하며 열리는 괄호가 나올 때 까지 값을 더해주거나 곱해주기. 4) 단, 짝이 맞지 않는 열리는 괄호가 나오면 올바르지 않은 문장이기 때문에 종료. 이게 가장 큰 틀이다. import java.util.Scanner; import java.util.Stack; ..

이 문제는 백준 골드 5 문제이다. 이 문제는 다익스트라 알고리즘을 이용해서 풀었다. 다익스트라 알고리즘에 대해서는 포스팅을 한 적이 있는데 간단하게 설명하자면 현재 있는 위치로부터 방문하지 않은 곳 중 가장 비용이 적게 드는 점을 찾아가는 것이다. 그렇게 가다가 목적지가 나오면 끝내는 알고리즘이다. 이 문제는 다른것보다 입력처리가 제일 오래걸렸다. 버스의 비용이 0일 경우를 생각하지 않고 코딩을 했는데, 버스의 비용이 0인 경우가 문제가 됐다. 2 2 1 2 0 1 2 10 1 2 의 예시를 넣으면 10이 나와서 이걸 처리하는게 오래걸렸다. 그래서 입력을 받을 때 1) 맵을 작은 값으로 초기화해주고, 2) 이번에 들어온 값이 이미 가지고 있는 값보다 작으면 새로운 값 넣어주기 3) 맵이 초기값 그대로라..

이 문제는 백준의 골드 4 레벨 문제이다. 처음에는 이 문제를 보고 각 단어가 어떤 문자를 가지고 있는지 확인한 뒤에 각 문자가 포함된 단어가 몇 개 있는지 계산해서 정렬을 해 주는 방법을 사용해 보려고 했다. 테스트케이스가 맞길래 될 줄 알았는데 생각해보니 반례가 있었다. 그래서 생각해 낸 방법이 조합을 이용해서 푸는 것이다. 알파벳은 총 26개가 있고, 그 중 5개는 무조건 가르쳐야 하는 단어이기 때문에 acint를 제외한 K-5개의 알파벳을 뽑아서 가장 많은 단어를 읽을 수 있는 조합을 찾아내면 된다. 1 )일단 a,c,i,n,t는 모든 단어에 들어가기 때문에 단어를 5개 미만으로 가르치면 읽을 수 있는 단어가 없으므로 다른 연산을 하지 않고 0을 출력한 뒤 종료시킨다. 2) 2차원 boolean ..

이 문제는 백준의 골드 5레벨 문제이다. 어제부터 어떤 분이 정리해두신 코딩테스트 대비를 위한 문제 리스트를 풀고 있는데, 레벨별로 정말정말 정리를 잘 해두셨다. 이 문제도 그 문제 중 하나였다. 시뮬레이션 기본 문제라고 하셨는데, 사실 골드 5 레벨 치고는 좀 쉬웠던 것 같다. 문제 푸는 시간보다 블로그 포스팅이 더 오래걸릴 수도 있겠다는 생각이 들 정도로..? 이 문제는 빗물이 쌓인 부분들을 계산하면 되는 문제인데, 1) 2차원 배열을 만들어서 땅이 있는 부분이라면 1을 저장해준다. 2) 2차원 배열을 처음부터 돌면서 2-1) 이번에 도착한 곳이 땅인데 지난번에 도착한 곳도 땅이라면 temp = 0 2-2) 이번에 도착한 곳이 빈 공간인데 지난번에 땅이였다면 카운팅 스타트! 2-3) 이번에 도착한 곳..

이 문제는 백준의 실버 1 레벨 문제이다. 이 문제는 보자마자 순열을 사용하면 되겠다는 생각이 들었다. 그래서 숫자 배열을 순열로 만들었다. 숫자의 순서를 바꾸고 + - * / 를 순서대로 진행하면 될 거라고 생각했는데 테스트케이스부터 틀렸다. 예시에서 3 4 5 1 0 1 0 이 주어졌는데, 이 경우엔 3*4+5 = 17 이 가장 작은 값이다. 하지만 내가 한 대로 풀면 (4+5)*3 = 27이 가장 작은 값으로 나온다. 그래서 연산을 가지고 순열을 돌렸다. 그러면 숫자의 배열은 그대로 가지고 가지만, 연산의 위치가 바뀌면서 최소값과 최댓값을 구해준다. 순열을 돌리는 과정을 조금 살펴보자면, 보통은 boolean 배열을 이용해서 방문처리를 해주지만 이번에는 연산자가 여러개 일 수도 있기 때문에 연산자의..

이 문제는 백준의 골드 3레벨 문제이다. 이 문제는 구현해야 할 게 많아서 혹시 어디선가 틀리면 디버깅하기가 너무 막막했는데, 다행히 한번에 맞았습니다가 나왔다ㅠㅠㅠㅠ 감격... 하여튼, 이 문제는 이런 방식으로 풀어냈다. 1. 층 정하기(Floor, 순열) 2. 각 층의 방향 정해주기(direction, 중복순열) 3. 층이랑 방향대로 map에 넣어주기.(change) 4. 시작점인(0,0,0)이 1이라면 들어가기. (bfs) 이 과정을 계속해서 반복하면 된다. 층은 총 5개이고, 각 층마다 4개의 방향을 가질 수 있으니 5!*4^5 개의 조합이 생긴다. 이 것들을 다 돌려주면 된다. 일단 Floor 함수에서는 boolean 배열과 int 배열을 이용해 5개의 판을 가지고 순열을 만들어준다. 만약 cn..

이 문제는 백준의 골드 1레벨 문제이다. 입력은 똑같이 받아주고, map에 0이 나오는 곳이 출발지이기 때문에 출발지가 나오면 move 함수에 넣어주었다. 다른 bfs와 비슷하게 큐에 넣고 큐가 끝나면 끝나는 방식이지만, 까다로운 부분이 있다. 바로 열쇠랑 문을 처리하는 부분이다. 일단 열쇠가 6개나 되고, 그 각각에 맞는 문이 있다. 게다가 문제에서 어떤 열쇠와 어떤 문이 주어질 지 모른다. 그래서 열쇠를 해결하기 위해 비트마스킹을 이용했다. a부터 f까지 각각 이진수를 이용해 000001 부터, 100000 으로 처리해주고, a와 b가 있다면 000011, a와 f가 있다면 100001 식으로 처리해서 방문 여부 체킹을 해주었다. 사실 이 부분만 잘 처리하면 다른 bfs와 비슷하게 풀 수 있는 문제인..