분류 전체보기
-
BOJ) 벽 부수고 이동하기 4알고리즘/백준 2020. 7. 3. 16:37
벽 부수고 이동하기 4 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 � www.acmicpc.net 풀이 처음에는 모든 벽에 대해서 벽을 허물고 값을 구하고자 했다. 하지만, 주어진 n과 m의 최대값이 1000이나 되기 때문에 시간초과가 뜰 것 같았다. 그래서 생각한 것은 0에 대해서 grouping을 해주는 것이다. 빈칸이 이어진 곳들에 대해서 그룹 index를 남기고, 몇 개의 빈칸이 존재하는지 세주어서 저장하는 것이다. 이후에, Map을 돌면서 벽을 허물었을 경우, 상하좌우에 (인접한 곳에) 빈칸 그룹이 가지..
-
BOJ) 부등호알고리즘/백준 2020. 7. 3. 16:27
부등호 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제�� www.acmicpc.net 풀이 답은 바로 구했지만, 메모리를 너무 많이 잡고 속도가 느려서 몇 번을 다시 풀었다. 처음에는 모든 경우의 수를 다 구해서, 부등호의 갯수 n개 +1 만큼의 숫자를 뽑은 경우를 답 리스트에 넣어주었다. 이후, 정렬을 통해 양 끝에 있는 수를 출력해주었다. 정말 별로인 코드다... 그래서 조금 고쳐보기로 했다. String으로 다 저장해서 정렬을 하는것이 아니라, Long 타입 변수를 통해 MAX와 MIN 값을 저장해주었다. 로직 자체가 문제라서 메모리와 속도에 ..
-
BOJ) 스타트와 링크알고리즘/백준 2020. 7. 2. 16:22
스타트와 링크 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 풀이 주어진 짝수 인원(4~20)이 축구 경기를 하는데, n/2 : n/2 경기를 해야한다. 이 때, 실력차이가 가장 적게나는 경우를 찾는 문제다. 결국, 모든 경우의 수를 다 파악해야하는 Brute-force 문제였다. n이 20이나 되지만, DFS를 선택했다. 왜냐하면, N=20인 경우, 10 : 10 경기를 하기 때문에, 결론적으로는 2^20까지 가지 않기 때문이다. 중간에 한쪽 팀이 N의 절반이 넘어가는 경우를 가지치기만 해준다면 가능하다고 생각했다. dfs를 통..
-
BOJ) 에너지 모으기알고리즘/백준 2020. 7. 2. 16:16
에너지 모으기 16198번: 에너지 모으기 N개의 에너지 구슬이 일렬로 놓여져 있고, 에너지 구슬을 이용해서 에너지를 모으려고 한다. i번째 에너지 구슬의 무게는 Wi이고, 에너지를 모으는 방법은 다음과 같으며, 반복해서 사용할 수 있� www.acmicpc.net 풀이 브루트 포스 문제로 모든 경우의 수를 다 구해야 했다. BFS와 DFS 중 DFS가 더 적절하다고 생각해서 DFS로 문제를 풀었다. 문제 조건에 따라서, 1~n-1 까지 하나의 숫자를 골라 좌 우에 있는 에너지를 곱해서 더해나갔다. 이때, 에너지를 담을 변수는 ArrayList를 선택해서 따로 index값을 복잡하게 조정하지 않게 해주었다. 왜냐하면, ArrayList에는 특정 index에 값(Element)를 넣을 수 있는 메소드가 존..
-
BOJ) 연구소알고리즘/백준 2020. 7. 2. 16:09
연구소 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net 풀이 배열 복사 문제로 고생을 조금 했다. 바이러스가 퍼지는 부분을 갱신할 때, 기존 MAP에 덮어 씌우면 답과 거리가 멀어지기 때문이다. 왜냐하면, char[][] map은 dfs에 계속 이용이 되기 때문에.. 다른 값들에 영향을 미친다. 배열 복사 이후에 바이러스가 퍼지고, 안전 구역을 탐색하니까 답을 맞출 수 있었다. 일단 3번 답을 구했는데, 첫번째로 구했던 답은 LinkedList를 이용하는 것이었다. 바이러스를 퍼뜨릴 때, LinkedList를 이용해서 B..
-
BOJ) NM과 K (1)알고리즘/백준 2020. 7. 2. 15:56
NM과 K (1) 18290번: NM과 K (1) 크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접� www.acmicpc.net 풀이 N x M의 격자판에서 k개를 선택하여, 해당 칸의 수를 더했을 때 최대 값이 되는 경우를 찾는 문제다. 또한 k 개를 선택할 때, 특정 좌표의 상하좌우로 인접해있으면 안된다는 조건이 있었다. 두 조건에 따라서 코드를 짜내려갔다. 방문체크를 하면서, 방문한 적이 없는 경우 상하좌우를 체크해주고, 선택이 가능한 경우면 sum에 더해서 다시 탐색하도록 했다. k 개 만큼 선택을 했을 때, 최대 값을 비교하면서 최신화 해주며 답을 구..
-
4장 ) 머스테치로 화면 구성하기Java & Spring/스프링 부트와 AWS로 혼자 구현하는 웹 서비스 2020. 7. 1. 01:26
서버 템플릿 엔진과 머스테치 소개 템플릿 엔진 지정된 템플릿 양식과 데이터가 합쳐서 HTML 문서를 출력하는 소프트웨어 서버 템플릿 엔진 : JSP, Freemarker -> 서버에서 구동 ~> 브라우저로 전달 클라이언트 템플릿 엔진 : React, Vue -> 브라우저에서 화면 생성 JSP, Velocity : Spring-boot에서 권장 X Freemarker - 과한 기능, 자유도가 높아서 숙련도가 낮을 수록 사용하기 힘들다. Thymeleaf - Spring에서 강하게 밀고있지만, 문법이 어렵다. 머스테치 서버 템플릿엔진, 클라이언트 템플릿 엔진으로 모두 이용 가능 (다양한 언어 지원) 장점 문법이 간단하다. View의 역할과 서버의 역할이 명확하게 분리된다. Mustache.js와 Mustac..
-
BOJ) 계란으로 계란치기알고리즘/백준 2020. 6. 30. 15:01
계란으로 계란치기 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 풀이 이 문제가 너무 좋은 점은, 테스트 케이스가 충분히 주어졌기 때문이다. 그래서 그런지 정답 비율이 꽤나 높다. 문제가 제시한 조건을 살펴보면, 계란이 일렬로 나열되어있고 가장 왼쪽 계란부터 오른쪽 끝까지 순차적으로 들어서 계란판에 있는 다른 계란을 내려 치는 것이다. 두 계란의 내구도는 각각 상대 계란의 무게만큼 감소하게 된다. 한번 내리친 다음에, 손에 들고있던 계란을 내려놓고 다음 계란을 든다. 이때, 조건이 손에 쥔 계란..