알고리즘
-
[백준] 10158번 : 개미 - 자바(JAVA)알고리즘/백준 2022. 4. 23. 00:01
https://www.acmicpc.net/problem/10158 10158번: 개미 가로 길이가 w이고 세로 길이가 h인 2차원 격자 공간이 있다. 이 격자는 아래 그림처럼 왼쪽 아래가 (0,0)이고 오른쪽 위가 (w,h)이다. 이 공간 안의 좌표 (p,q)에 개미 한 마리가 놓여있다. 개미는 오 www.acmicpc.net 문제 해석 개미가 2차원 공간에서 움직이는데 경계면에 부딪히면 반사되어 움직입니다. (초기 방향 = 오른쪽 위 45도) 개미는 1시간마다 이동합니다. t시간 이후에 개미의 좌표를 출력하세요 문제 풀이 전 설계 개미는 오른쪽위/ 왼쪽 위/ 오른쪽 아래/ 왼쪽 아래로 움직입니다. 하지만 오른쪽위로 가다가 어느 벽에 부딪히느냐에 따라 방향이 달라지기 때문에 이점을 고려해야 합니다. 만..
-
[백준] 8320번 : 직사각형을 만드는 방법 - 자바(JAVA)알고리즘/백준 2022. 4. 22. 00:01
https://www.acmicpc.net/problem/8320 8320번: 직사각형을 만드는 방법 상근이는 변의 길이가 1인 정사각형 n개를 가지고 있다. 이 정사각형을 이용해서 만들 수 있는 직사각형의 개수는 총 몇 개일까? 두 직사각형 A와 B가 있을 때, A를 이동, 회전시켜서 B를 만들 수 www.acmicpc.net 문제 해석 1 x 1 크기의 정사각형이 N개 존재합니다. 이 정사각형을 이용하여 만들 수 있는 직사각형을 개수를 구하세요. 문제 풀이 전 설계 반복문을 통해 i= 1 ~ N까지 반복합니다. 하나의 반복을 통해 i개 정사각형으로 만들 수 있는 직사각형의 개수를 구합니다. 우선 홀수/ 짝수로 나누어 생각해봤습니다. 홀수 1, 3, 5, 7, 9의 경우에는 한 줄로 밖에 가능하지 않을..
-
[백준] 2116번 : 주사위쌓기 - 자바(JAVA)알고리즘/백준 2022. 4. 21. 00:01
https://www.acmicpc.net/problem/2116 2116번: 주사위 쌓기 첫줄에는 주사위의 개수가 입력된다. 그 다음 줄부터는 한 줄에 하나씩 주사위의 종류가 1번 주사위부터 주사위 번호 순서대로 입력된다. 주사위의 종류는 각 면에 적혀진 숫자가 그림1에 있는 www.acmicpc.net 문제 해석 주사위는 1~6까지의 숫자가 적혀있다. 하지만 마주 보는 면의 숫자의 합이 반드시 7이 되는 주사위가 아니다. 아래에서부터 1번 주사위, 2번 주사위, 3번 주사위,... 의 순서로 주사위를 쌓는다. 이때 다음과 같은 규칙이 존재한다. 서로 붙어 있는 두 개의 주사위에서 아래에 있는 주사위의 윗면에 적혀 있는 숫자 = 위의 있는 주사위의 아랫면에 적힌 수 (단 1번 주사위는 마음대로 놓을 수..
-
트라이 자료구조알고리즘/알고리즘 2022. 4. 20. 20:34
트라이(Trie)란? 트라이란 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조입니다. 우리가 검색할 때 볼 수 있는 자동완성 기능, 사전 검색 등 문자열을 탐색하는데 특화되어 있는 자료구조입니다. Trie라는 말은 탐색 트리(retrieval tree)에서 나온 단어입니다. 트라이 자료구조의 예시이며 주황색으로 된 노드들이 입력된 문자열입니다. 예를 들어 cat이라는 단어를 검색하기 위해서는 제일 먼저 'c'를 찾고, 다음에 ca 그다음에 cat의 순서로 찾습니다. 여기에서는 리프노드(끝 노드)들에 모든 문자열들이 들어가 있습니다. 트라이 자료구조의 장단점 문자열을 탐색할 때, 하나하나씩 전부 비교하면서 탐색하는 것보다 시간 복잡도에서 훨씬 더 효율적입니다. 각 노드에서 자식들에 대한 포..
-
[백준] 17413번 : 단어 뒤집기 2 - 자바(JAVA)알고리즘/백준 2022. 4. 20. 00:01
https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 문제 해석 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 문자열 S는 아래와 같은 규칙을 지킵니다. 1. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 있다. 2. 문자열의 시작과 끝은 공백이 아니다. 3 ''가 문자열에 있는 경우 번갈아가면서 등장하며, '
-
[백준] 1244번 : 스위치 켜고 끄기 - 자바(JAVA)알고리즘/백준 2022. 4. 19. 00:01
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main_1244_스위치켜고끄기 { static class Student { int gender; int switchNumber; public Student(int gender, int switchNumber) { super(); this.gender = gender; this.switchNumber = switchNumber; } @Override public String toString() { return "S..
-
[백준] 17144번 : 미세먼지 안녕! - 자바(JAVA)알고리즘/백준 2022. 4. 18. 00:01
https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 문제 해석 R x C 크기의 격자판이 존재합니다. 공기청정기는 항상 1번 열에 설치되어 있고 크기는 두 행을 차지합니다. 1초동안 아래 적힌 일이 순서대로 일어납니다. 1. 미세먼지가 확산된다. 확산은 미세먼지가 존재하는 모든 칸에서 동시에 일어납니다. - 미세먼지는 인접한 네 방향으로 확산됩니다. - 인접한 방향에 공기청정기가 있거나, 칸이 존재하지 않으면 그 방향으로는 확산이 일어나지 않습니..
-
[백준] 13300번 : 방배정 - 자바(JAVA)알고리즘/백준 2022. 4. 17. 00:01
https://www.acmicpc.net/problem/13300 13300번: 방 배정 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 수학여행에 참가하는 학생 수를 나타내는 정수 N(1 ≤ N ≤ 1,000)과 한 방에 배정할 수 있는 최대 인원 수 K(1 < K ≤ 1,000)가 공백으로 분리되어 www.acmicpc.net 문제 해석 남자는 남자끼리, 여자는 여자끼리 방배정을 해야 한다. 방의 최소 개수를 구하자 한방에는 같은 학년끼리 한방에 배정할 수 있는 최대 인원수 K 문제 풀이 전 설계 2차원 배열을 선언하여 거기에 성별 /학 생년의 학생수를 저장합니다. 예를 들어 한방에 2명밖에 못 들어가는데 학생이 3명이면 반이 2개 필요합니다. 학생수 == 0이라면 그냥 넘어가고 학생수가 K ..