YANGORITHM

문제https://www.acmicpc.net/problem/1083  풀이그리디 문제다 사전 순으로 뒤에 서기 위해 왼쪽에서 오른쪽으로 갈수록 수가 작아져야 한다왼쪽에서 오른쪽으로 순회한 인덱스를 기준으로 오른쪽에 있는 수 중 남은 s번을 교체해서 가져올 수 있는 최댓값을 매순간 바꿔주면 된다 연속된 수만 교체할 수 있는데, 이는 인덱스 차이가 남은 s 이하라면 바로 바꿀 수 있다는 것을 의미한다- s가 3일 때 3과 5의 위치를 바꾼다 -> 5 3 1 2 4, s = 2                    1과 4의 위치를 바꾼다 -> 5 3 4 1 2, s = 0  코드python123456789101112131415161718192021222324252627n = int(input())arr = l..

보조 스트림실제 읽고 쓰는 스트림이 아닌 보조 기능을 제공하는 스트림이다FilterInputStream, FilterOutputStream이 보조 스트림의 상위 클래스다생성자의 매개변수로 또 다른 스트림(기반 스트림이나 다른 보조 스트림)을 가진다InputStreamReader, OutputStreamWriter바이트 단위로 읽거나 쓰는 자료를 문자로 변환해주는 보조 스트림이다FileInputStream으로 읽은 자료를 문자로 변환하는 예제다import java.io.FileInputStream;import java.io.IOException;import java.io.InputStreamReader;public class InputStreamReaderTest { public static void..

문제https://www.acmicpc.net/problem/1931  풀이그리디 문제다 1. 회의가 끝나는 시간이 빠를수록 더 많은 회의를 고를 수 있다2. 회의가 끝나는 시간 이후부터 가장 빨리 시작되는 회의를 골라야 한다 이를 위해 끝나는 시간이 작은 순서대로 오름차순 정렬을 한다만약 끝나는 시간이 갔다면 시작 시간이 작은 순서대로 또 오름차순 정렬을 한다  코드python12345678910111213141516171819meet = []answer = 0endTime = 0 n = int(input()) for _ in range(n):    begin, end = map(int, input().split())    meet.append([begin, end]) meet.sort(key= ..

Thread프로세스실행 중인 프로그램이다.프로그램이 실행되면 운영체제로부터 메모리를 할당받아 프로세스가 된다스레드하나의 프로세스는 하나 이상의 스레드를 가진다.실제 작업을 수행하는 단위는 스레드다multi-thread여러 스레드가 동시에 수행되는 프로그래밍, 여러 작업이 동시에 실행되는 효과스레드는 자신만의 작업 공간을 가진다 (context)스레드 사이에서 공유하는 자원이 있다 (자바에서는 static instance)여러 스레드가 자원을 공유하는 경우, 서로 자원을 차지하려는 race condition이 발생할 수 있다여러 스레드가 경쟁하는 자원을 critical section이라고 한다critical section에 대한 동기화를 구현하지 않으면 오류가 발생할 수 있다Thread 만들기Thread ..

문제https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다.www.acmicpc.net  풀이55-50+40 에서 55-(50+40)으로 괄호를 씌우면 최소값인 -35가 나오게 된다. 이 때 ()를 전개해서 표현하면 '+' 기호는'-' 기호로 바뀌어서 55-50-40이 된다. 이 원리를 이용해서 첫 번째 '-' 이후에 나오는 모든 '+' 기호를 '-'로 치환하면 최소값이 나오게 된다.   1. 첫 숫자부터 -가 나오기 ..

해당 게시물은 인프런 - "영리한 프로그래밍을 위한 알고리즘 강좌" 강의를 참고하여 작성한 글 입니다강의 링크RecursionRecursion은 자기 자신을 호출하는 함수다void func(...) { ... func(...); ...}다음 Recursion 코드를 실행하면 무한루프에 빠진다public class Code01 { public static void main(String[] args) { func(); } public static void func() { System.out.println("Hello..."); func(); }}무한루프에 빠지지 않으려면?recursion을 무한 루프에 빠지지 않으려면 적절한 구조를 ..

문제https://www.acmicpc.net/problem/1715  풀이오름차순으로 정렬해서 더하면 되는 그리디 문제다이때 주의할 점은 작은 수끼리 더한 값도 다시 리스트에 넣어서 오름차순으로 정렬해야 한다우선순위 큐를 이용하면 최소값을 O(1) 시간 만에 찾을 수 있고, 오름차순으로 정렬하는 데 O(log n) 만큼 걸리므로 문제를 해결할 수 있다  코드python12345678910111213141516171819import sysimport heapq heap = []sum = 0 n = int(sys.stdin.readline()) for _ in range(n):    card_size = int(sys.stdin.readline())    heapq.heappush(heap, card_si..

문제https://www.acmicpc.net/problem/3190 3190번: 뱀문제  'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따www.acmicpc.net  풀이문제에 나와있는 순서대로 구현을 해주면 된다. 특별히 신경 쓴 부분은 종료조건과 꼬리의 이동 부분이다.  뱀의 몸이 있는 공간을 chec..

문제https://www.acmicpc.net/problem/9375  풀이headgear 의상 종류에 대해서 현재 hat, truban이 있다이때 가능한 경우의 수는 {hat}, {turban}, {}(공집합) 3가지 이다 모든 옷 종류에 대해서 각각 가능한 경우의 수를 곱하고 모든 옷 종류를 하나도 안 입는 경우(1가지)를 빼주면 된다  코드python123456789101112131415161718t = int(input()) for _ in range(t):    n = int(input())    d = {}    for _ in range(n):        clothes, category = input().split()        if category not in d:            ..

문제https://www.acmicpc.net/problem/11279  풀이우선순위 큐를 이용해 O(n * logⁿ) 시간복잡도로 해결한다 파이썬에서는 heapq 라이브러리를 이용해 최소 힙으로 우선순위 큐를 사용할 수 있다문제에서 최대 값을 찾아야하므로 숫자를 저장할 때 음수로 바꿔서 저장하면 최대 힙처럼 사용할 수 있다  코드python12345678910111213141516import heapqimport sys n = int(input()) heap = [] for _ in range(n):    x = int(sys.stdin.readline())    if x == 0:        if heap:            print(-heapq.heappop(heap))        else:..