백준26 [Java] 백준 11054 가장 긴 바이토닉 부분 수열 https://www.acmicpc.net/problem/11054 문제바로가기 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 1. 접근방법 1. dp기반의 LIS 알고리즘을 사용해야겠다 생각함 2. 처음에는 문제를 잘못이해해서 좌우로 같은 거리만큼 떨어진것이 바이토닉 수열인줄알아서 우측방향 LIS 왼쪽방향 LIS을 통해 각 인덱스별로 값이 같은거를 출력해주려고했음 3. 손으로 숫자 적어보면서 그냥 좌우로 길기만 하면된다고 판단해서 같은게 아닌 더해서 가장 큰값을 출력해주면 됐음 2. 실수 1. ->진행방향는 괜찮았지만 2022. 4. 11. [Java] 백준 1613 역사 https://www.acmicpc.net/problem/1613 문제바로가기 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 1. 접근방법 1. dfs, bfs, 다익스트라, 플로이드워셜로 풀 수 있겠다고 생각이 들었음. 2. 플로이드워셜을 자주 사용안해서 사용하기로 했음. 2. 실수 값이 뭐가 큰지 헷갈렸다 그러니까 어떤게 더 먼저 일어났는지 헷갈려서 바꿔줬음. 3. 코드 import java.io.*; import java.util.*; public class boj1613 { public sta.. 2022. 4. 11. [Java] 백준 1003 피보나치 함수 https://www.acmicpc.net/problem/1003 문제바로가기 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 1. 접근방법 1. 재귀함수로 0 1일때 리턴해주고 숫자세서 출력해줘야겠다. 2. 시간초과-> 0.25초라 재귀적으로는 풀지못하고 dp로 풀어야겠다고 생각함. 3. 0,1일때 각각 출력해줘야하므로 dp테이블 2개를 따로 선언해 각각 더해주고 출력해주기로 생각함. 2. 실수 및 느낀점 1. 문제를 꼼꼼히 읽지않고 바로 내 방식으로 품 만약 테케를 제공해주지 않거나 채점결과를 알려주지 않는 테스트라면 분명 좋지 않을 것이라고 생각함. 2. dp로 풀어도 좀더 효율적으로 짤 수 있지않을.. 2022. 4. 11. [Java] 백준 9012 괄호 클래스 2++ 도전기 https://www.acmicpc.net/problem/9012 문제바로가기 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 1. 접근방법 1. 괄호에 짝이 맞으면 가능하겠구나 생각함 2. 그래서 여는괄호 닫는괄호수를 새서 같으면 YES해주려고하니 순서가 )))((( 이면 틀린 것이기 때문에 이방법으로는 불가능 3. 그래서 스택을 통해서 (나오면 스택에 넣고 ) 나오면 pop해주는 방식으로 구현해야겠다라고 생각함 구현시간 5분 2. 실수한 부분 1. )나오면 pop해줄때 st이.. 2022. 4. 9. [Java] 백준 19236 청소년 상어 https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 1. 접근방법 1. 문제를 읽어보면 딱히 어려운 설명은 없어서 천천히 읽어보고 이해한 후 풀어야 겠다고 생각함 2. 물고기 이동 함수, 상어 재귀 함수, 딥카피 함수 3개가 있으면 편하겠다고 생각함 2. 어려웠던점 좌측과 우측은 서로 독립적인 공간에서 작업하고 돌아오기에 같은 값으로 돌아와야했다. 하지만 그렇지 않았다... 객체를 생성하고 딥카피 할때 일반적인 2차원 배열처럼 복.. 2022. 4. 7. [JAVA] 백준 11559 뿌요뿌요 Puyo Puyo https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 1. 접근방법 1. bfs를 통해서 블럭이 4개가 인접해있는지 판단하고 맞으면 부쉬고 내려줘야겠다 2. 내리는 함수 down, 확인함수 및 파괴 check를 구현하면 되겠다. 2. 어려웠던 부분(실수) 1. 색을 총 5개 입력받아야 하는데 4개만 받아서 로직은 맞지만 틀려서 뭐때문인지 찾는게 힘들었다. 맞왜틀 2. 연쇄 폭발 횟수와 총 폭발 횟수를 혼돈했다. ex)입력받은.. 2022. 4. 6. [JAVA] 백준 12100번 2048 (Easy) https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 문제접근방법 1. 5번을 어떤방식으로 만들어서 전해줄것인가 -> 순열, 조합, 부분집합으로 도저히 생각이 안나서 5중포문 사용했다. 2. 그 뒤로는 게임방식을 이해하면서 코드를 짜면서 자잘한 오류들을 수정함 3. 상하, 좌우 묶어서 생각하니까 훨씬 편했다. 도움된테스트케이스 1번 3 2 0 2 0 2 0 2 0 2 답은 4가 나와야 하는데 8이 나와서 이부분에서 잘못된.. 2022. 3. 31. [JAVA] 백준 1929 소수 구하기 https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 클래스2++도전기 나만의 문제접근방법 1. 소수는 약수가 1과 그수 자신인 숫자라고 알고 있었다. 2. 시작이 3 끝이 16이면 3부터 반복문을통해 일차원적으로 소수인지 아닌지 검토하는 방식 -> 시간초과 메모리간당간당 3. 뭔가 알고리즘이 있을것같아 찾아보니 에라토스테네스의 체라는 알고리즘을 사용하거나 더 뛰어난 알고리즘을 사용해야했었다. 4. 간단히 공부 후 코드를 작성해 제출했음 어려웠던 점 출력해줄때 0,1을 예외처리해주.. 2022. 3. 28. [JAVA] 17404 RGB거리 2 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 접근방법 1) 문제를 읽고 바로 dp라고 생각이 들었다 1행이 2행에 영향이 있고 ... N행까지 영향을 주니까 2) 첫번째집을 R G B 각각 선택했을때 N행에서 만약 첫행 선택한 색이 R을 선택했다면 마지막행 R은 최솟값 선택에서 제외 3) 아래 그림을 그리면서 아이디어 획득함 이전 행에서 현재 색을 제외하고 최소값을 구해준다. 예를 들면 현재 레드2행 이라면 1행.. 2022. 3. 27. [Java] 백준 2164 카드2 https://www.acmicpc.net/problem/2164 문제바로가기 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 백준 스트릭 2++ 100% 도전기 문제접근방법 1) 카드를 세워서 처음 맨위카드는 버리고 그다음 카드는 맨뒤로 보낸다라는 글을 읽고 앞뒤 => 큐를 써야겠다 2) 반복문을 통해 뽑아 버리고 맨뒤로 보내고를 반복했다. 느낀점 크게 어렵지 않은데 다른사람들이 푼 숏코딩을 보니 더좋은 방법이 많아서 최적화를 더할수 있을것 같았다. import java.io.*; import java.ut.. 2022. 3. 27. [JAVA] 백준 4153 직각삼각형 https://www.acmicpc.net/problem/4153 4153번: 직각삼각형 입력은 여러개의 테스트케이스로 주어지며 마지막줄에는 0 0 0이 입력된다. 각 테스트케이스는 모두 30,000보다 작은 양의 정수로 주어지며, 각 입력은 변의 길이를 의미한다. www.acmicpc.net 2++ 클래스 도전기 접근방식 1. 문제설명과 그림을 통해 피타고라스 정리를 통해 직각삼각형을 유추한다고 판단 2. 0,0,0 들어오면 끝내주고 배열로 받아드려 정렬하고 가장큰수를 대각선으로 잡아서 피타고라스 정리 3. 값이 서로 같으면 직각삼각형 아니면 직각삼각형 아님으로 판단 느낀점 3만개의 입력이 들어오는데 이부분을 system.out.println으로 하면 시간을 많으 잡아 먹을것 같다 그래서 버퍼드라이터와.. 2022. 3. 24. [JAVA] 2206 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 접근방법 1. 기본적으로 최단거리 찾기 문제라 바로 BFS가 떠올랐다. 2. BFS 돌릴때 모든 맵의 벽을 모두 한번씩 지워보며 가면 정답이 나오겠네 시간초과 (맞왜틀?) 3. 그럼 가는길에 부술수있으면 부수고 아니면 그냥 갈길 가면서 BFS 타보자 시간초과,메모리 (맞왜틀?) 4. 갈때 부순경우 안부순경우 모두 체크해서 큐에 넣자 (이게맞네?) 느낀점 고정관념을 버려야 .. 2022. 3. 24. 이전 1 2 3 다음
