YANGORITHM

문제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:..

문제https://www.acmicpc.net/problem/10799  풀이스택을 이용해 문제를 풀 수 있다 레이저가 발사되면 스택에 쇠막대기가 쌓인 만큼 조각이 추가된다 입력한 문자열을 탐색하면서 다음 과정을 반복한다  '('를 만나면 스택에 push 한다 ')'를 만나면 스택에서 '('를 pop한다. 이때 () 처럼 연속되어서 레이저로 나가는지 확인해야 한다인덱스 차이가 1이면 레이저로 나간다그렇지 않으면 막대기의 길이가 끝나는 것이다인덱스 차이가 1이면 스택의 크기만큼 총 개수에 추가한다 (스택의 크기만큼 조각이 생긴다)그렇지 않으면 총 개수에 1을 추가한다 (막대기의 마지막 조각)   코드python1234567891011121314151617brackets = input() stack = []..

문제 https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 풀이 큐를 이용해 문제를 해결할 수 있다. 큐에서 k - 1 번 데이터를 front에서 pop하고 rear에 넣어준다. 이것이 원을 이루면서 앉아있는 것과 같아진다. 그 다음 k 번째에 데이터를 pop한다. 이를 q가 빌 때까지 반복하고 pop한 숫자들을 차례대로 저장해 출력한다. 코드 python 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 from collections import deque def solution(n, k): answer = [] q = de..

문제 https://www.acmicpc.net/problem/17472 17472번: 다리 만들기 2 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다. www.acmicpc.net 풀이 지도에서 표시된 섬마다 다르게 숫자로 표시한다. 이를 위해 BFS로 탐색하면서 섬마다 값을 부여한다. 각 섬에서 다른 섬으로 연결할 수 있는 에지가 있는지 확인해서 에지 리스트를 만든다. 이를 위해 섬 마다 모든 점에서 상하좌우로 다리를 만들어본다. 만든 에지리스트로 크루스칼 알고리즘을 적용해 최소 신장 트리를 만든다. 코드 java import java.io.Bu..

문제 문제 링크 풀이 트리인지 확인하기 위해서 다음 2가지를 검사한다. Root가 1개인지 검사한다. V로 들어오는 간선이 2개 이상인지 확인한다. 트리는 Root가 1개이어야한다. 또한 V로 들어오는 간선도 1개이어야 한다. 2개 이상이면 사이클이 발생할 수도 있다. 문제에서는 트리의 노드 번호를 특정할 수 없으므로 배열을 사용할 수 없다. 그래서 Set을 이용해 문제를 해결했다. 코드 java import java.util.HashSet; import java.util.Scanner; import java.util.Set; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); St..

문제 문제 링크 풀이 해쉬맵을 이용해 문제를 해결했다. 인덱스를 키 값으로, 입력 받는 포켓몬 이름을 데이터 값으로 가지는 해시맵을 만든다. 다음과 같은 해시맵을 하나 만든다. (1 : Pikachu) 이어서 인덱스를 포켓몬 이름으로, 데이터 값을 인덱스 값을 가지는 해시맵을 만든다. 다음과 같은 해시맵을 또 만든다. (Pickachu : 1) 두 개의 해시맵을 이용해 간단히 풀 수 잇다. 해시를 사용하므로 시간복잡도는 O(1) 이다. 코드 java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.Map; pub..

문제 https://www.acmicpc.net/problem/2559 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 풀이 투 포인터를 이용한다. l 인덱스 값을 증가시키면 이전 l 인덱스에 있던 값을 지우고 r 인덱스까지의 합을 구한다. 그 후 최대값을 비교하여 답을 구해간다. 수열에 음수도 나올 수 있으므로 처음에 최소값을 설정할 때 주의한다. 코드 java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 ..

문제 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 풀이 투 포인터를 이용한다. r 인덱스를 늘리면서 합을 구하고 m 값과 같은지 확인한다. l 인덱스가 증가할 때는 이전 l 인덱스에 있던 값을 빼준다. 코드 java import java.util.Scanner; public class Main { static int n, m; static int[] a; public static void main(S..