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. 풀이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. 문제 독서실에서 원하는 자리를 이용 가능한 시간을 구하는 문제다.1, 2번 규칙에 따라 새로 온 사람이 이용하는 좌석을 파악해 문제를 해결해야 한다. 2. 풀이1. 0900 ~ 2100 이라는 숫자로 나오지만 이걸 분 형태로 바꿔주어야 계산이 편함 (아니면 9시 ~ 10시가 100분이 됨..!)2. 사람들이 선호하는 좌석을 구하는 함수 만들기3. heapq를 사용하여 새로운 사람이 오면 추가하고 visited를 True로 바꾸어주기4. 정답은 720에서 시작해서 자리를 사용할 수 없는 시간 만큼 빼기1. max_dist, best_seat 변수 초기화2. 1부터 n+1까지 돌려서 각각 좌석 번호에 대하여, 이미 방문하지 않은 경우에만 실행3. left_dist, right_dist를 무한대로 초기화..

1. 문제 이 문제는 풍선 m개를 만드는데 걸리는 최소 시간을 구하는 문제이다.스태프마다 만드는 속도가 다른 상황에서 짧은 시간 안에 최소 시간을 구해야 한다. 2. 풀이1. l, r을 양 끝 숫자 0과 max(time) * m으로 초기화한다.2. l보다 r이 크거나 같은 동안 반복문을 실행한다.3. 두 수의 중간값 mid에 대하여 스태프마다 해당 시간에 몇 개를 만들었는지 그 합을 구한다.4. 그 값이 m보다 크거나 같을 경우 답을 mid로 초기화하고 최솟값을 찾기 위해 r을 mid - 1로 바꾼다.5. 아닌 경우 l을 mid + 1로 바꾸어 계속 탐색한다.3. 코드import sysinput = sys.stdin.readlinen, m = map(int, input().split())time = li..

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

1. 문제 이 문제는 직사각형 종이를 한 변이 1인 직사각형 모양의 조각으로 잘라서조각 안의 수를 왼->오, 위->아래로 붙인 수의 합을 최대로 만드는 프로그램을 짜는 문제이다.특이점은 종이의 크기가 최대 4*4로 작다는 점이다.2. 풀이이 문제는 다양한 시도를 했으나 그만큼 실패를 많이 경험했다.처음에는 단순히 생각해서 그냥 가로로 쭉 자른 종이들의 합, 세로로 쭉 자른 종이들의 합,이 두 값을 비교해서 큰 값으로 하면 되잖아? 라고 생각했다.왜냐면 종이를 쭉 이어서 자르지 않고 막 조각내면 자릿수가 작아지니까.근데 이건 잘못된 생각이었다.문제에서 나온 예시와 달리 '0'이 들어가는 경우에 이상한 상황이 생긴다. 예를 들어서, 아래와 같은 종이조각 말이다.0023001299990011 1. 가로로 쭉 ..

백준 14391 종이조각 문제를 풀면서 메모리 초과가 계속하여 떴다.아무리 해도 해결이 되지 않아 검색해보니 비트마스킹이라는 새로운 방법을 쓰는 사람이 많았다.처음 듣는 방법이지만 메모리를 아낄 수 있는 방법이라 종종 쓸 일이 있을 것 같다. 비트마스킹특정 비트를 켜고 끄거나 반전시키기 위해비트 연산에 사용되는 데이터위키 백과에 따르면 비트마스크는 비트 연산에 사용되는 데이터로,다중 비트들을 싱글 비트 연산 작업에서 켜고 끄거나 상호 반전시킬 수 있다. 일단 비트 연산들을 알아보겠다.비트 연산자설명&AND (둘 다 1이면 1 반환)|OR (둘 중 하나라도 1이면 1 반환)^XOR (둘이 서로 다르면 1 반환)~NOT ( 1-> 0, 0->1 반전)left shift (지정한 수만큼 왼쪽으로 비트 이동)>..

1. 문제 이 문제는 선수의 능력치를 고려하여 포지션을 정해 가장 최대의 능력치를 구하는 문제이다.11명의 선수들에 대해 11개 포지션에 대한 능력치를 수치화하여 제시한다.그 숫자들 중 모든 경우의 수를 고려하여 가장 최대의 합을 구하는 문제이다.즉, 전형적인 백트래킹 문제.2. 풀이솔직히 이 문제를 어떻게 풀어야 할지 감이 안 왔다.아직 알고리즘 실력이 부족하기 때문인 것 같다.어떤 상황에서 어떤 알고리즘을 써야 하는지 아직 잘모르는 것 같아서백트래킹 알고리즘을 다시 정리해야겠다고 생각했다.https://jemarque.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9-Backtrackin..

최근 코딩테스트 문제를 풀면서 알고리즘 정리가 필요함을 느꼈다.자주 출제되는데 아직 나에게 어려운 백트래킹을 먼저 정리해보려고 한다. 백트래킹 모든 경우의 수를 고려하는 알고리즘 백트래킹은 재귀를 활용해 모든 경우의 수를 확인하는 알고리즘이다.대표적으로 DFS, BFS를 사용하며 코딩테스트에서 잘 다루어지는 알고리즘이기도 하다.시간복잡도는 중복이 가능한 경우, N**2이고 중복이 불가한 경우는 N!이다. 목표한 조건에 도달하는 경우를 탐색하는 것인데,절대 목표에 도달할 수 없다고 판단이 되면 앞으로 돌아가서 다시 그 조건에 맞는 경우를 탐색한다. 1. DFS깊이 우선 탐색트리에서 바닥에 도달할 때까지 한쪽 방향으로만 내려가는 방식으로재귀함수를 사용하여 목표한 바가 나올 때까지 반복한다.일반적으로 모든 경..