본문 바로가기

전체 글1063

백준 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.
개인 도메인 티스토리 블로그 - 네이버 검색 등록 티스토리 도메인 그대로 (nahwasa.tistory.com) 사용하시는 분도 이하 내용대로 진행하는데 문제는 없음. 일단 예시는 개인 도메인(nahwasa.com)이 등록된 경우 네이버 검색에 블로그를 등록하는 방법 입니다. 1. 네이버 서치어드바이저 (이하 SA로 명명함) 접속 https://searchadvisor.naver.com/ 2. 웹마스터 도구 사용하기 클릭 3. 사이트 주소를 아래와 같이 써서 등록! 4. 소유확인에서 'HTML 태그' 선택하고 텍스트 복사 5. 티스토리 관리 -> 스킨편집 -> html편집 쪽에 붙여넣기 해줌. 대충 다른 meta 있는쪽에다가 넣어주면 됨. 6. 다시 SA 화면에서 소유확인 클릭 7. SA에서 등록된 사이트 클릭 8. 뜨는 페이지에서 '검증 -> robo.. 2021. 9. 27.
백준 2157 자바 - 여행 (BOJ 2157 Java) https://www.acmicpc.net/problem/2157 입력 받으면서 서쪽에서 동쪽으로 이동하는 경우는 제외해줬다. (a가 b보다 큰 경우) 동일 노선에 기내식이 별로인 경우도 제외해줌. 처음엔 무지성 Brute Force로 일단 갈겨봤으나 당연히 시간초과났음. ㅠ 다익스트라나 floyd-washall 같은걸로는 m회 이하를 체크하기 힘들꺼라 일단 제외함. 다행히 한방향으로만 진행하면 되므로 그냥 dp 돌리기로 결정함. dp 배열 설정은 dp[i][j] - i:도시번호, j:이동횟수, value:i도시번호까지 j이동횟수로 얻은 최대 기내식 점수 처럼 해줬음. 그럼 이제 dp[1][1] = 0; 을 베이스로 두고 (1번에서 출발했고, 1번도 방문한 도시에 포함되니 [1][1]이 됨. 기내식은 아.. 2021. 9. 26.
개인 도메인 티스토리 블로그 - 구글 검색 등록 (가비아 DNS 기준) 개인 도메인으로 돌려둔 티스토리 블로그를 구글 검색에 등록하는 법 이하 내용은 티스토리 블로그를 '개인 도메인'으로 돌려둔 유저에게 해당함. 물론 티스토리 URL 그대로 (nahwasa.tistory.com)도 구글 검색에 등록이 가능하지만(아마 URL 접두어 쪽에 해야할꺼임), 이렇게 개인 도메인을 만들어서 등록하면 장점이 있음. 차후 블로그를 바꾸게 되더라도 구글 검색쪽을 안건드려도 됨. (큰 장점은 아님 ㅋㅋ) A. Google Search Console -- B. 개인 도메인 (nahwasa.com) -- C. 티스토리 (nahwasa.tistory.com) 이런 형태이므로 나중에 C가 변경되도 A는 그대로 있음. 1. 구글 검색이 되도록 하기 위해 Google Search Console 접속 (.. 2021. 9. 26.
BFS 알고리즘 (너비 우선 탐색) - 배열 BFS, 그래프 BFS (2022-08-27 업데이트) 2022-07-21 업데이트 : 글 맨 아래에 '풀어보기'로 풀어볼만한 문제 링크 추가 2022-08-27 업데이트 : '풀어보기' 좀 더 추가, 목차 추가 목차 BFS (Breadth-first Search) 명확히 검증하면서 쓴게 아니라서 틀린 부분 있으면 알려주세요! - BFS와 DFS 대충 곰처럼 생긴 섬이 바다에 떠 있다. 편의상 이 섬을 20등분해서 격자 형태로 구역을 나누었다. 이제 우측상단의 귀(곰 입장에서 왼쪽귀)부터 출발해서 섬 전체를 둘러보려 한다. 둘러보는 방법은 여러가지가 있을 수 있다. 빨간 숫자는 둘러본 순서를 뜻한다. (0 부터 19까지) A처럼 자신과 가까운 곳부터 순서대로 살펴볼수도 있다. 격자형태로 나누었으므로 Manhattan Distance (Taxicab Geome.. 2021. 9. 24.
백준 2452 자바 - 그리드 게임 (BOJ 2452 Java) https://www.acmicpc.net/problem/2452 어려웠음.. 2일이나 걸렸음.. 기본적인 로직은 아래와 같이 잡음 1. 각 구간은 어차피 동시에 움직이므로 동일 색상으로 된 구간 전체를 하나로 생각함 2. 그러면 배열 전체에 대한 bfs에서, 그래프에 대한 bfs로 압축시킬 수 있음. bfs로 생각한 이유는 결국 각 구역별로 색상이 변하는거니 한칸만 잡고 계속 변경한다고 보면 결국 가장 먼 구역까지의 bfs라고 생각했음. 즉, 구역을 나누고 각 구역별로 모든 지역까지 bfs를 때린다음 그 횟수가 가장 적은게 답이라 생각함. 즉, 3 3 1 0 0 1 0 0 0 1 1 이러한 입력에 대해 구간을 나눠서 숫자를 붙임. (이게 필요할꺼라 생각해서 한건데 하고보니 이게 flood fill 인듯.. 2021. 9. 22.
알고리즘 시간복잡도에 대해 목차 Complexity Up & Down 게임을 해봅시다! 1~100까지의 숫자 중 하나를 생각해보겠습니다. 전 96을 생각할껍니다. 이걸 누군가에게 맞춰보라고 하고, up & down으로 대답하겠습니다. "1" ⇒ up "2" ⇒ up "3" ⇒ up .. (92번을 더 한 후) "96" ⇒ 맞았..어.. 이렇게 물어볼사람은 없을껍니다! 다들 자연스럽게 아래와 같이 물어볼꺼에요. "50" ⇒ up "75" ⇒ up "87" ⇒ up "93" ⇒ up "96" ⇒ 맞았어! 이걸 다르게 표현해보겠습니다. 우선 1부터 차례대로 물어본 전자의 경우를 보겠습니다. 1~100까지의 100개를 N개라 표현하겠습니다. 이 경우 만약 생각한 숫자가 100이라면(= 생각한 숫자가 N이라면) 최악의 경우로, 100번 물.. 2021. 9. 22.
CP 입문 추천 (코딩테스트 연습) CP 입문 추천 CP; Competitive Programing '입문'이라고 적었으나, 애초에 대회라는 특성상 입문이라고 하기엔 난이도가 다소 높은 편. 보통 아무런 공부 없이 참여하면 한 문제도 풀기 힘든 경우가 많음. PS를 경쟁적으로 진행하는 것으로, 프로그래밍 대회 혹은 코테를 부르는 용어라고 보면 됨. 예를들어 대회 접수를 사전에 받고, 9월 16일 오후 9시에 진행되서 2시간이 주어지고 그 동안 5문제를 푸는 경우. 일반적으로 정해진 시각에 시작해서, 정해진 시간동안 진행되며 Score Board로 서로 경쟁할 수 있도록 해두고 순위가 매겨짐. 방식은 개최하는 대회 혹은 개최하는 곳 마다 다르며, 지원하는 언어도 다르므로 확인하고 참여해야 함. (자바, C++, 파이썬은 보통 다 지원함) 프.. 2021. 9. 22.