Definition of Seon

쏘 심플한 오늘의 문제..파이썬으로 첫 문제를 풀었던 이 문제로 자바 알고리즘을 시작했다.입력 받기부터 어려워서 개념을 정리해보기로! 풀이Scanner를 사용해서 두 수를 받아주고두 수를 더한 값을 출력하면 된다. 코드import java.util.*;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int a, b; a = sc.nextInt(); b = sc.nextInt(); System.out.println(a+b); }} 자바 Scanner자바의 스캐너는 java.util패키지 안에서 찾을 수 있는 클래스로메서드를 사용해서 Boolean, ..

그동안 백준을 풀 때 파이썬만 사용해오다가처음으로 자바를 사용해서 문제를 풀기 시작했다.가장 기본 문제(?)인 1000번 A+B 문제이다.파이썬으로 풀 때는 코드길이와 시간이 상대적으로 짧은 반면에자바로 풀었을 때는 코드길이와 시간이 현저히 높음을 확인할 수 있다.물론 메모리에 있어서는 자바가 승리..!하지만 그동안 메모리가 부족해서 못 푼 문제 보다는 시간의 문제로해결하지 못한 문제들이 더 많았어서... 이번에 자바로 문제를 풀기 시작한 이유는 크게 두 가지다.1. 싸피에서 자바반에 입과했기 때문!2. 언젠가 코딩테스트에서 파이썬이 금지되는 경우가 있을까봐 그렇지만 벌써부터 쉽지 않다...기본 문제를 풀려고 해도 몇 개의 메서드를 import 해야하는 건지... 나와 같은 시행착오를 겪을 사람들을 위해..

1. 문제 이 문제는 배열을 한 변의 길이가 2 ** n인 배열을 Z 모양으로 탐색하며r행 c열을 몇 번째로 방문하는지 출력하는 프로그램이다.r과 c, 그리고 순서 모두 0부터 시작한다. 2. 풀이재귀적으로 접근하기! 4등분을 반복한다!1. 만약 size가 1이 될 경우 ans는 start로 초기화한다.2. size가 2 이상인 경우 배열을 4등분하여 r과 c가 어디에 위치하는지 확인한다.3. 해당 사분면에 대해서 r과 c의 값을 갱신하고 해당 조각의 가장 왼쪽 위가 몇 번째인지를 구한다.4. 위와 같은 방법으로 find 함수를 반복한 뒤 ans를 출력한다. 3. 코드import sysinput = sys.stdin.readlinedef find(start, size, r, c): global an..

1. 문제우선순위 큐, 힙큐를 활용하여 풀어야 하는 문제. 2. 풀이heapq의 기본적인 동작, heappush와 heappop만 활용하면 되는 문제이다. - heapq.heappush(배열 이름, 원소)- heapq.heappop(배열 이름) 이 두 가지만 알면 이 문제를 쉽게 풀 수 있다.단, 평소에 사용하던 기본 리스트나 deque의 사용법과는 좀 달라서 주의가 필요하다. 3. 코드import heapqimport sysinput = sys.stdin.readlinen = int(input())arr = []for i in range(n): x = int(input()) if x == 0: if len(arr): print(heapq.heappop(arr)..

1. 문제이 문제는 배열을 반시계 방향으로 R번 회전시킨 결과를 구해 출력하는 문제이다. 2. 풀이귀찮고 오래 걸릴 것 같은 구현 문제였다.풀기 싫어서 이틀은 미루었다..ㅠㅠ 배열에서 어느 위치에 있느냐에 따라 돌렸을 때 자리까지 돌아오는 횟수가 달라진다.최대한 시간을 줄이기 위해 꼭 필요한 만큼만 돌려야겠다는 생각을 했다.즉, 다시 자기 자리에 돌아와 한 바퀴 회전하는 경우를 빼야 한다는 것.전체 길이로 돌리는 횟수를 나눈 나머지 만큼만 돌리면 된다. 2차원 배열로는 어려워서 1차원 배열로 바꾸기로 정했다.좀 지저분하지만 각각의 그룹을 모두 분리해냈고,그 뒤에 1차원 배열 내에서 돌리기를 쉽게 수행했다. 그 뒤 다시 2차원 배열로 바꾸어 출력해주었다. 3. 코드n, m, r = map(int, inpu..

1. 문제 이 문제는 접두사X집합의 최대 크기를 구하는 문제이다.주어진 배열에서 어떤 단어가 다른 단어의 접두어가 되지 않는 부분집합을 만들어야 한다.단어의 개수는 최대 50이어서 숫자가 크지 않다. 2. 풀이접두어가 되려면 자신보다 길거나 같은 길이의 문자여야 하므로길이를 기준으로 짧은 길이부터 긴 길이 순으로 정렬을 했다.이후 이중 반복문을 사용하여 가장 짧은 단어부터 시작해 자기 자신 다음 단어부터 가장 긴 단어까지 확인한다.만약 단어 j를 i 단어의 길이 만큼 잘라서 i와 자른 j가 같다면 단어 i는 부분집합에 들어갈 수 없다. 직접 배열 자체에서 그 단어를 삭제하는 것도 방법이지만,결국 출력해야 하는 것은 크기 값 뿐이므로 ans 변수를 새로 만들어 겹치는 단어를 빼주었다.처음에는 n 자체를 변..

1. 문제 이 문제는 스티커를 뗄 때 얻을 수 있는 최대 점수를 구하는 문제이다.그러나 스티커를 떼면 맞닿는 스티커들은 사용할 수 없어진다. 2. 풀이이 문제는 코테 스터디에서 시간을 정해두고 풀었다.20분 정도 소요되어서 풀었다.이전에 풀어봤던 dp 문제들 덕에 금방 풀이 방법을 생각해냈다. 스티커 배열을 입력받고 그것과 같은 형태로 dp 테이블을 초기화한다.자기 자신을 뜯을 경우에는 바로 왼쪽 칸은 뜯을 수 없고, 대각선에 있는 걸 뜯을 수 있다.그래서 자신 + 왼쪽 대각선을 뜯은 값과 왼쪽 칸을 뜯은 값 중 최댓값으로 dp 테이블을 갱신한다.마지막에는 모든 값 중 최댓값을 출력한다.3. 코드import sysinput = sys.stdin.readlinet = int(input()) #테스트케이스f..

1. 문제 이 문제는 호텔의 홍보 비용에 따른 고객 수 증가 정보를 가지고호텔의 고객을 c명 이상 늘이기 위해 투자해야 하는 돈의 최솟값을 구하는 문제이다. 2. 풀이[접근 1 - dfs] 시간초과처음에는 dfs를 활용하여 재귀 형태로 모든 경우의 수를 확인하도록 했다.모든 방법을 확인하다가 고객 수가 c 이상이 될 경우 최솟값을 갱신하고 return하는 형태이다.답을 찾는 데는 무리가 없었으나 시간초과가 떠버렸다.이에 시간을 줄일 수 있는 다른 방법을 고민했다. [접근 2- dp]목표 고객 증가 수인 c에다가 한 번의 투자로 늘어날 수 있는 최댓값인 100을 더해서 dp테이블을 만들었다.혹시 c보다 c+1이 더 비용이 적게 들 수도 있기 때문이다.dp 테이블은 모두 큰 수로 초기화해두고 반복문을 돌렸다..

1. 문제 이 문제는 어떤 단어가 주어지고 사전식 정렬을 하였을 때그 바로 다음에 오는 단어를 찾는 문제이다.2. 풀이[접근 1]처음에는 모든 사전식 배열을 다 늘어놓고그 중에서 입력값을 찾은 뒤, 그 다음 값을 출력하는 방식을 생각했다. 1. 순열 라이브러리를 이용해 단어 조합을 모두 리스트에 넣는다.2. 처음 입력한 단어의 인덱스를 찾는다.3. 마지막 단어가 아닐 경우 다음 단어를 출력한다. 역시 코드 자체에 문제는 없었으나 결과가 시간 초과가 떠버렸다.필요 없는 데이터까지 다 구해서일까...바로 다음 순열을 어떻게 찾을지 긴 시간 고민했다. [접근 2]고민의 과정을 거쳐 뒤에서부터 숫자 크기를 비교하는 방식을 발견했다.그 뒤 숫자 위치를 바꾸고 거꾸로 정렬하는 방식으로 문제를 해결할 수 있었다.뒤의..

백준 21918번 전구https://www.acmicpc.net/problem/21918 1. 문제 전구의 상태를 숫자 0과 1로 표현한다.전구가 꺼진 경우는 0, 켜진 경우는 1이다.전구를 제어하는 명령어 1~4번을 입력된 순서대로 처리한 뒤의 전구 상태를 확인하는 문제이다. 2. 풀이이 문제는 간단한 구현 문제로, 난이도가 쉬운 편이었다.각각의 명령어를 수행하는 코드를 짜서 명령어가 입력된 순서에 맞게 실행만 시키면 된다. 함수형 프로그래밍 구현을 위해 조건문을 사용해 각 경우를 함수 안에 넣었다.반복문을 사용해 명령어들을 입력받은 순서대로 실행했다. 3. 코드처음 시도에서는 평소 자주 사용하던 방식대로 입력 받은 명령어 정보를 배열에 저장했다.그 뒤에 배열에 저장한 각각의 명령어 정보에 대해 순서대..