본문 바로가기

전체 글1050

백준 21772 자바 - 가희의 고구마 먹방 (BOJ 21772 JAVA) https://www.acmicpc.net/problem/21772 BFS로 착각할 여지가 있는 문제이다. 하지만 한번 지나간 곳을 다시 올 수 있다는 점과, 지나간 경로상에 있는 고구마의 갯수를 세야 하는 문제이므로 방문체크를 할 수 없다. 따라서 모든 경로를 보는 Brute Force 문제이다. 정확히 따지자면 내 로직의 경우 사실 모든 경우를 보진 않았고, 답이 될 수 없는 경로인 경우 취소시켰으므로 Back Tracking이라 봐도 되는데, 어차피 모든경로 다 봐도 시간초과가 나진 않으므로 큰 의미는 없다. t가 최대 10이고 한 장소에서 상하좌우 4개의 방향으로 이동 가능하므로 최대 O(4^10) 짜리 BF라고 보면 된다. 그냥 DFS 돌리면서 모든 경우를 확인하면 된다. 주의점은 '가희가 고구.. 2021. 10. 3.
백준 11048 자바 - 이동하기 (BOJ 11048 JAVA) https://www.acmicpc.net/problem/11048 만약 이동이 상하좌우로 가능했었다면, 혹은 [우측, 아래, 우측아래, 좌측]과 같이 좌측으로도 이동이 가능했다던지 하면 BFS 등의 방법으로 전체 경우를 보면서 풀어야 한다. 하지만 이처럼 방향이 우측, 아래, 우측아래 대각선 처럼 한쪽 '사분면'으로 고정되어 있다면 Dynamic Programming(DP; 동적계획법)으로 더 간단하게 풀 수 있다. 일단 다음의 그림을 보자. 위 그림은 이 문제에서 (1,1)에서 (N,M)으로 갈 때 각 위치에서 이동할 수 있는 방향을 나타낸 것이다. 그럼 위 그림에서 예를들어 정중앙의 '5'로 올 수 있는 화살표만 남겨보겠다. 다음으로 중앙 우측의 '6'으로 오는 화살표이다. 그럼 벽에 붙어있는 '2.. 2021. 10. 2.
백준 2825 자바 - 수업시간에 교수님 몰래 교실을 나간 상근이 (BOJ 2825 JAVA) https://www.acmicpc.net/problem/2825 알고리즘 분류랑 솔브닥 티어 표시 끄고, 문제 검색 옵션에서 실~플로 랜덤으로 나오게 하고 문제푸니 쫄깃하게 재밌다. 이건 처음엔 실버상위~골드하위 정도일줄 알았는데, 생각할수록 최소 골드 중간쯤은 될꺼란 생각이 들었다.. 처음엔 단순하게 1이 포함된 숫자 리스트, 2가 포함된 숫자 리스트, ... 이렇게 분류해서 union-find나 각 쌍을 hashset에 넣으면서 nCr로 계산하면 될 것 같았다. 하지만 아무리 생각해봐도 시간복잡도를 O(N^2)에서 줄일수가 없었다. 이쯤에서 실~골하위는 아닐꺼라 일단 생각이 들었다 ㅋㅋ N이 100만개이므로 O(N^2) 풀이는 아예 불가하고, 못해도 O(NlogN) 정도 수준으로 생각해내야 한다. .. 2021. 10. 2.
자료구조 리스트 (List) - Linked List, Array List, Vector 차이점 포함 리스트? (Linked List - 연결 리스트) 일반적으로 '리스트'는 연결 리스트(Linked List)를 뜻한다. 이후 Array List와 Vector를 추가로 설명하기 전까지 모든 설명은 연결 리스트(Linked List)에 대해 다룬다. 리스트는 배열처럼 데이터를 순서대로 표현하는 자료구조 중 하나인데, 구현 방법에 큰 차이가 있다. 배열은 메모리 상에 연속된 공간을 '미리 할당받고' 메모리상에 데이터를 순서대로 넣어 만든 자료구조이다. 리스트는 메모리 상에 데이터가 어디에 있던 신경쓰지 않는다. 'data = [12. 3. 11. -2]'를 배열과 리스트로 표현해보겠다. 위의 정갈하게 메모리상에 순서대로 들어가 있는 것이 배열, 아래쪽에 메모리상에 흩뿌려져 있는 것이 리스트이다. 이 때 배열.. 2021. 9. 30.
백준 2617 자바 - 구슬 찾기 (BOJ 2617 JAVA) https://www.acmicpc.net/problem/2617 홀수인 N개의 구슬 중 '중간이 될 수 없으려면' 자신보다 무게가 작은게 (N/2+1)개 존재하거나, 무게가 큰게 (N/2+1)개 존재하면 된다. 예를들어 N이 7일 때 자신보다 큰게 4개라면 무조건 중간엔 가고싶어도 갈 수 없다. 이 문제는 다소 이해하기 난해할수도 있으나, 결국 '자신보다 큰게 (N/2+1)개 이상 있거나, 자신보다 작은게 (N/2+1)개 이상 있는 구슬의 갯수를 구하면 된다.' 그럼 어떻게 구할까? M개의 쌍에 대해 어느쪽이 무거운지 알려줬는데 이걸 단방향 그래프(=directed graph =유향 그래프 =방향 그래프)의 edge라 생각하면 쉽다! 문제에서 제시된 예시를 단방향 그래프로 그려보겠다. 우선은 '무게가 .. 2021. 9. 30.
[자바] 프로그래머스 - 지형 이동 [코딩테스트 연습 Lv4] - 문제 : https://programmers.co.kr/learn/courses/30/lessons/62050 - 코드 : https://github.com/NaHwaSa/Programmers_OnlineJudge/blob/main/Level%204/%EC%A7%80%ED%98%95%20%EC%9D%B4%EB%8F%99.java 1. 모든 칸을 방문한다고 했지, 한 칸에 여러번 가면 안된다는 말은 없었다. 따라서 높이차이가 height 이하인 곳은 가중치 0으로, 아무런 제약 없이 돌아다닐 수 있다. -> 다시 말해, 상하좌우로 높이차이가 height 이하인 곳은 서로 그룹으로 생각해도 됨. -> 예를들어 [[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, .. 2021. 9. 29.
백준 6549 자바 - 히스토그램에서 가장 큰 직사각형 (BOJ 6549 JAVA) https://www.acmicpc.net/problem/6549 코드가 긴 문제는 아니었지만, 공책에 그려보며 생각한걸 구현하기가 좀 어려웠다. 많이틀렸다 ㅋㅋ (맞았습니다가 여러개인 이유는 시간을 좀 더 줄여보려 했으나 유의미하게 시간차이를 못냈다.) 풀고보니 사람들이 참 다양한 방법으로 푼 문제인것같다. 스택, 분할정복, 세그먼트 트리, 분리집합+우선순위 큐 크게는 이렇게 4가지 방식으로 푼 듯 하다. 저의 경우엔 스택으로 풀었다. 높이(h)가 너비(n)에 비해 수치가 많이 크다. 처음 들었던 생각은 어차피 높이가 많다해도, n이 최대 10만이므로 h의 종류는 아무리 많아봐야 10만 가지이다. 따라서 좌표압축처럼 높이를 1~10만까지로 압축할 수 있다. (예를들어 높이가 3,5,2 처럼 들어왔다면 .. 2021. 9. 29.
백준 2638 자바 - 치즈 (BOJ 2638 Java) https://www.acmicpc.net/problem/2638 안쪽에 빈 공간은 공기에 접촉하지 않은 것으로 가정하므로, 단순히 배열 전체를 확인하며 공기부분의 상하좌우를 파악하면 안됨. 치즈가 존재하지 않는 외곽에서 시작해서 (코드에선 (0, 0)에서 시작함) dfs나 bfs를 돌려 인접한 공기들로 탐색하면서 인접한 치즈를 확인해야 함. 구현은 사실 간단했음. 반복문 돌리면서 매번 다음의 처리를 해줌. 1. 매번 (0, 0)부터 dfs 돌리면서 상하좌우로 접한게 치즈라면 해당 치즈 부분의 값을 +1 해줌. 접한게 공기라면 그쪽으로 dfs 계속 진행함. (42 line) 2. 치즈인 부분의 갯수를 세줌 (cnt 변수) 3. 공기와 접한 부분이 2면 이상이라면 (코드상으로는 따로 배열 만들기 귀찮아서 .. 2021. 9. 28.
백준 1655 자바 - 가운데를 말해요 (BOJ 1655 Java) https://www.acmicpc.net/problem/1655 발상이 쉽지 않았다. 시간제한도 짧아서 어떻게 구현할지 좀 막막했음. 일단 0.1초같이 극악한 제한시간이 있는 문제들의 경우 자바로는 아예 통과가 불가한 문제들도 있다. 그래서 일단 채점 현황에 자바로 AC 받은게 있나부터 확인했는데 있어서 자바로 도전함 ㅋㅋ 힙을 배열로 어떻게 잘 만들면 O(NlogN)으로 집어넣으면서 바로바로 정렬되고 중간값을 O(1)로 찾을 수 있지 않을까 싶기도 했지만 딱히 구현방식이 생각나지 않았음. 그렇다고 ArrayList에 집어넣고 매번 정렬하는건 당연히 시간초과 날꺼고.. 그다음으로는 이분탐색쪽을 생각해봤으나 역시 구현할 방법이 딱히 떠오르지 않았음. 그러던 중 보통 이런식으로 2부위나 절반씩 나눠 생각하.. 2021. 9. 28.
스프링부트 Swagger UI 적용 방법 - 스프링부트 2.2 미만 (Spring Boot Swagger UI) Spring Boot Swagger 적용하기 * 주의 : 스프링부트 2.2 이상을 사용한다면 여기를 참고하여 진행하세요. 2.9.2를 이미 사용 중에 3.0.0으로 마이그레이션을 한다면 여기를 참고하세요. Swagger ? 간단히 말하자면 API 문서를 자동으로 만들어주는 라이브러리임 https://swagger.io/ 예시는 스웨거의 Live Demo 참조 (https://petstore.swagger.io/) 완전 기본적인 적용방법에 대해서만 다룸. 단순 문서 뿐 아니라 API를 문서내에서 parameter를 넣어가며 바로바로 실행 해볼 수 있음. rest api 제작 후 따로 테스트 페이지나 postman으로 실행해보는 대신 swagger 문서 만들어서 실행 가능. 복잡하지 않은 시스템이라면 res.. 2021. 9. 27.

티스토리툴바