JAVA - 백준 [BAEK JOON]
[백준] 17298번 : 오큰수 - JAVA [자바]
[백준] 17298번 : 오큰수 - JAVA [자바]
2021.01.21www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 Stack의 원리를 이해하면 생각보다 그리 어렵지는 않다. 알고리즘 [접근 방법] 이 문제가 의외로 어떻게 스택을 활용해야할지 갈피를 못잡는 문제인 것 같다. 이중 for문을 사용하면 최대 1,000,000 * 1,000,000 = 1,000,000,000,000 (1조)으로 시간초과 날 것이 뻔하다. 스택의 기본 원리는 딱 한 가지만 기억하면 된다. '후입선출' 즉, 가장 최근에 들어온 것이 가장 먼저 나오는 것이다...
[백준] 1010번 : 다리 놓기 - JAVA [자바]
[백준] 1010번 : 다리 놓기 - JAVA [자바]
2021.01.18www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 문제 문제만 제대로 이해한다면 쉽게 풀 수 있는 문제다. 알고리즘 [접근 방법] 문제는 매우 간단하다. 우선 문제에서 두 가지 포인트를 짚고 넘어가보자. 1. 한 사이트에는 한 개의 다리만 놓일 수 있다. 2. 서로 다른 다리가 겹치면 안된다. 즉, 위 그림처럼 첫 번째 같이 서로 겹치지 않게 다리를 놓는 경우 외엔 한 사이트에 두개의 다리가 놓이거나, 서로 다른 다리가 가로지르면 안된다. 그럼 무엇을 생각할 ..
[백준] 1934번 : 최소공배수 - JAVA [자바]
[백준] 1934번 : 최소공배수 - JAVA [자바]
2021.01.17www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net 문제 바로 직전 문제인 '최대공약수와 최소공배수' 문제를 풀었다면 그리 어렵지 않게 풀 수 있었을 것이다. 알고리즘 [접근 방법] 이 문제는 유클리드 알고리즘으로 풀라고 나온 문제다. 즉, 유클리드 호제법(Euclidean algorithm)을 사용하라는 것인데, 앞서 필자가 이미 '최대공약수와 최소공배수' 문제를 풀이하면서 설명했다. '꼭 아래 포스팅을 먼저 보고 오시길 바란다' http:..
[백준] 13305번 : 주유소 - JAVA [자바]
[백준] 13305번 : 주유소 - JAVA [자바]
2021.01.13www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 문제 설명이 조금 복잡해보이나 원리만 이해하면 정말 쉬운 문제다. 알고리즘 [접근 방법] 문제 설명이 길어서 그렇지 내용 자체가 어려운 문제는 아니니 먼저 문제부터 이해하고 넘어가보자. 먼저 N개의 도시가 있고, 각 도시를 잇는 N-1개의 도로가 있다. 그리고 각 도시에는 주유소의 리터당 가격이 써져 있고, 각 도로에는 거리가 적혀져 있다. (1km당 1L 기름을 사용함) 문제에 있는 예시를 보면..
[백준] 11653번 : 소인수분해 - JAVA [자바]
[백준] 11653번 : 소인수분해 - JAVA [자바]
2021.01.09www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 문제 말 그대로 소인수분해를 하는 문제라 쉽게 풀 수 있을 것이다. 알고리즘 [접근 방법] 소인수분해. 영어로 prime factorization이라고 한다. 아마 대부분 우리나라 교육과정을 다 마치셨다면 기억하실 것이다. 말 그대로 어떤 수를 더이상 쪼개지지 않는 수들의 곱으로 분해하는 것이다. 이를 약간 변형해서 말하자면 어떤 정수 N을 소수들의 곱으로 나타낸다는 것이다. 위 문제에서는 즉, 다음과 같은 구조로 짜면 된다. /* * 임의의 정수 N에 대하여 곱셈으로 분해하면 * 제곱근(√N)을 기준으로 대칭이 된다. * 예로들..
[백준] 9184번 : 신나는 함수 실행 - JAVA [자바]
[백준] 9184번 : 신나는 함수 실행 - JAVA [자바]
2021.01.05www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 문제 문제가 어려운 편은 아니다. 주어진 조건에 따라 함수를 그대로 옮겨적고 메모이제이션만 추가하면 된다. 알고리즘 [접근 방법] 문제를 설명하기는 모호한데.. 일단 동적계획법의 특징은 대체로 재귀 + Memoization(메모이제이션) 이라는 것을 생각하면 된다. 위에서 설명한 조건에 따른 함수(재귀)호출은 코드로 보면 이렇다. static int w(int a, int b, int c) { if(a 20) { ..
[백준] 2164번 : 카드2 - JAVA [자바]
[백준] 2164번 : 카드2 - JAVA [자바]
2020.12.19www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제 큐에 대한 원리만 알고 있어도 쉽게 풀 수 있는 문제다. 알고리즘 [접근 방법] 이 번 문제같은 경우 자료구조를 한 번쯤 접해봤거나 큐에 대한 개념이 있다면 쉽게 풀 수 있는 문제다. 잠깐 큐에 대해 설명하자면 큐 자료구조의 경우 '선입선출' 자료구조로 말 그대로 먼저 들어간 요소가 먼저 나오는 방식이다. 쉽게 생각해서 놀이기구를 타기위해 줄서있는 모습을 생각하면 된다. 큐에 대한 자세한 내용과 구현은 아..
[백준] 18258번 : 큐 2 - JAVA [자바]
[백준] 18258번 : 큐 2 - JAVA [자바]
2020.12.13www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 큐에 대한 원리만 알고 있어도 쉽게 풀 수 있는 문제다. 알고리즘 [접근 방법] 단계별로 풀어보기 큐와 덱 카테고리 첫 문제다. 이 번 문제같은 경우 자료구조를 한 번쯤 접해봤거나 큐에 대한 개념이 있다면 쉽게 풀 수 있는 문제다. 잠깐 큐에 대해 설명하자면 큐 자료구조의 경우 '선입선출' 자료구조로 말 그대로 먼저 들어간 요소가 먼저 나오는 방식이다. 쉽게 생각해서 놀이기구를 타..
[백준] 1874번 : 스택 수열 - JAVA [자바]
[백준] 1874번 : 스택 수열 - JAVA [자바]
2020.12.03www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 스택의 원리만 이해한다면 쉽게 풀 수 있는 문제다. 알고리즘 [접근 방법] 아마 이 문제를 처음 접한다면 무슨 말인가 할 수도 있겠지만, 이해만 한다면 정말 쉬운 문제다. 스택 자료구조는 본문에서도 나와있듯이 LIFO(후입선출) 특성을 갖고있다. 스택에 대한 기본적인 이해는 다음 포스팅을 참고하시길 바란다. 자바 [JAVA]..
[백준] 4949번 : 균형잡힌 세상 - JAVA [자바]
[백준] 4949번 : 균형잡힌 세상 - JAVA [자바]
2020.12.01www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net 문제 이전 괄호 문제에서 좀 더 업그레이드 된 버전이다. 알고리즘 [접근 방법] 이 문제는 이 전 문제인 9012의 괄호 문제를 정확히 이해하고 있다면 쉽게 풀 수 있을 것이다. 만약 괄호 문제를 풀어보지 않았다면 먼저 아래 포스팅을 먼저 보고 오시길 바란다. [백준] 9012번 : 괄호 - JAVA [자바] www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Par..