농부공학자

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 스택을 활용한 문제이다. 6 9 5 7 4 의 높이를 가진 탑일 때 4의 높이에서 레이저를 쏜다면 7에, 7의 높이에서 레이저를 쏜다면 9에 맞을 것이다. 해당 위치에서 왼쪽 방향으로 레이저를 쐈을 때 몇 번째 건물에 맞는지 구하는 문제이다. 여기서 알아야 할 것은 6 다음에 9를 스택에 넣었을 때, 다음 건물들은 6에 레이저를 절대 맞출 수 없다는 것이다. 그래서 스택에 첫 번째 건물부터 넣으..

https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 완전 탐색으로 풀었다. 어차피 B보다 값이 커지면 멈출거고, A=2, B=10^9이어도 최솟값이 1억보다 작기 때문에 괜찮다고 판단함 B보다 커지면 Queue에 안넣을거라서 int값으로 했는데 long값으로 해줘야했다. 흠 코드 import java.io.*; import java.util.*; public class Main { static class Node implements Comparable{ long value, cnt; public Node(long value, long cnt) { this.value = v..

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net dp문제이다. 표를 그려서 확인해보면 감이 온다. 이렇게 그려봤다. 열에 있는 0~9까지의 숫자가 각 자리수(행 번호)에 들어갔을 때 나올 수 있는 경우의 수 이다. 예를 들어 행이 2, 열이 0인 수는 20, 21, 22, 23, 24, 25, 26, 27, 28, 29 이렇게 10개가 된다. 아무튼 저 표를 봤을 때 규칙을 찾을 수 있다. 노랑 + 노랑 = ..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 처음에는 문제 접근을 백트래킹으로 했다. 그런데 n값이 10만까지인데 재귀를 빠져나올 조건이 딱히 안보였음. 실컷 보다가 dp같아서 다른사람 풀이 참고했다. 풀이 예를 들어 저기에 있는 50은 무조건 스티커를 뜯는다고 하자. 그러면 저 파란색인 50과 70을 뜯었을 때 최대가 되도록 해야한다. 노란색의 오른쪽 10과 아래 30은 못 뜯는게 자명한데, 저 파란색 두 군데만 신경쓰는 이유는..

https://www.acmicpc.net/problem/1918 스택 사용하는 문제이다. 처음에는 괄호를 치고 계산하려고 했는데 괄호 치는 과정이 너무 어려워서 관둠. 일단 '(' 가 나오면 ')' 가 나와야하는게 자명함 그리고 ')'가 나오면 '('가 나올 때까지 어딘가에 저장해둔 연산자를 빼야하는것도 자명하다! 그럼 이걸 1. 어딘가에 저장해야하고 2. 연산자를 어떻게 빼서 가져올지 고민하면 될 것 같다. 물론 저도 틀렸음ㅎㅎㅋㅋㅋ 코드 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new Buffered..

https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net N값만큼 입력받은 애들이 M값만큼 안에 contain하는지 확인하면 되므로 HashSet 사용했다. 몇 개가 듣보일지 모르므로 ArrayList 사용함 그리고 사전순 정렬해줬다. 코드 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws Exception { Buf..

https://www.acmicpc.net/problem/2607 2607번: 비슷한 단어 첫째 줄에는 단어의 개수가 주어지고 둘째 줄부터는 한 줄에 하나씩 단어가 주어진다. 모든 단어는 영문 알파벳 대문자로 이루어져 있다. 단어의 개수는 100개 이하이며, 각 단어의 길이는 10 이 www.acmicpc.net 내가 푼 방법은 원본 DOG를 HashMap에 로 넣어놓고 다른 문자열을 비교할 때마다 clone해서 사용하는 방법이다. 비교 단어가 최대 100개이고 단어 길이도 최대 10이라서 가능함! 주의할 점은 비교 문자열의 알파벳을 원본 문자열 알파벳에서 개수를 빼주고 원본 문자열에 남은 문자열이 있는지도 체크해줘야함. 조건 하나의 문자를 1. 더하거나 2. 빼거나 3. 바꾼다 체크 잘하기! 코드 im..

https://www.acmicpc.net/problem/20920 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 오랜만에 푸는 알고리즘......ㅎㅎ map에는 다양한 메소드가 많은데 맨날 put get contains 이런거만 쓰는 것 같아서 언제한번 정리해보려고 한다. 아무튼 풀이를 해보자면 사실 신경써야하는건 얘네가 정렬되는 순서이다. 자주 나오는 단어일수록 앞에 배치한다. 해당 단어의 길이가 길수록 앞에 배치한다. 알파벳 사전 순으로..

https://www.codetree.ai/training-field/frequent-problems/tree-kill-all/description?page=3&pageSize=20 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 6개월 전 쯤 풀어봤던 문제였다. 진짜 문제 그대로 읽으면서 풀면 된다. 이런 문제는 순서대로 구현하면서 구현이 잘 됐는지 디버깅하면서 풀어야함. 일케 해도 처음부터 다 맞는건 쉽지않다. 풀이 자료구조 - int[][] tree: 살아있는 나무만 표시 - int[][] diedTree: 제초제(

https://www.codetree.ai/training-field/frequent-problems/battle-ground/description?page=3&pageSize=20 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 문제를 읽고 그대로 구현하면 되는 문제였다. 구상..은 1시간도 안걸렸는데 구현하고 디버깅하느라 2시간 걸렸음 신경쓸게 크게 없는데.. 모든 구현 문제가 그렇겠지만 본인이 어떻게 구현하느냐에 따라 자기 코드때문에 헷갈릴 수 있을 것 같다. 개인적으로 코드트리빵이 더 어려웠다 풀이 자료구조 - HashMap< PID, (현재 ..