-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
10 lines (10 loc) · 15.3 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
<!doctype html><html lang=ko dir=auto><head><meta name=generator content="Hugo 0.123.4"><meta charset=utf-8><meta http-equiv=X-UA-Compatible content="IE=edge"><meta http-equiv=Content-Security-Policy content="upgrade-insecure-requests"><meta name=viewport content="width=device-width,initial-scale=1,shrink-to-fit=no"><meta name=robots content="index, follow"><title>봄을 기다리는 낙엽</title> <meta name=description content><meta name=author content><link rel=canonical href=https://1eaf.site/><meta name=google-site-verification content="l76eAEMadEn1QzS8fLTbrl8ppayZprvV3uuAbMGSy_c"><meta name=yandex-verification content="XYZabc"><meta name=msvalidate.01 content="XYZabc"><meta name=naver-site-verification content="004739eff5dcb2ef7d1e7cb7fc43a0fc093da50c"><link crossorigin=anonymous href=/assets/css/stylesheet.b609c58d5c11bb90b1a54e04005d74ad1ddf22165eb79f5533967e57df9c3b50.css integrity rel="preload stylesheet" as=style><link rel=icon href=https://1eaf.site/favicon.ico><link rel=icon type=image/png sizes=16x16 href=https://1eaf.site/favicon-16x16.png><link rel=icon type=image/png sizes=32x32 href=https://1eaf.site/favicon-32x32.png><link rel=apple-touch-icon href=https://1eaf.site/apple-touch-icon.png><link rel=mask-icon href=https://1eaf.site/safari-pinned-tab.svg><meta name=theme-color content="#2e2e33"><meta name=msapplication-TileColor content="#2e2e33"><link rel=alternate type=application/rss+xml href=https://1eaf.site/index.xml><link rel=alternate type=application/json href=https://1eaf.site/index.json><link rel=alternate hreflang=ko href=https://1eaf.site/><noscript><style>#theme-toggle,.top-link{display:none}</style><style>@media(prefers-color-scheme:dark){:root{--theme:rgb(29, 30, 32);--entry:rgb(46, 46, 51);--primary:rgb(218, 218, 219);--secondary:rgb(155, 156, 157);--tertiary:rgb(65, 66, 68);--content:rgb(196, 196, 197);--code-block-bg:rgb(46, 46, 51);--code-bg:rgb(55, 56, 62);--border:rgb(51, 51, 51)}.list{background:var(--theme)}.list:not(.dark)::-webkit-scrollbar-track{background:0 0}.list:not(.dark)::-webkit-scrollbar-thumb{border-color:var(--theme)}}</style></noscript><script async src="https://www.googletagmanager.com/gtag/js?id=G-9PNFP00SSG"></script><script>var doNotTrack=!1;if(!doNotTrack){window.dataLayer=window.dataLayer||[];function gtag(){dataLayer.push(arguments)}gtag("js",new Date),gtag("config","G-9PNFP00SSG",{anonymize_ip:!1})}</script><meta property="og:title" content="봄을 기다리는 낙엽"><meta property="og:description" content><meta property="og:type" content="website"><meta property="og:url" content="https://1eaf.site/"><meta name=twitter:card content="summary"><meta name=twitter:title content="봄을 기다리는 낙엽"><meta name=twitter:description content><script type=application/ld+json>{"@context":"https://schema.org","@type":"Organization","name":"봄을 기다리는 낙엽","url":"https://1eaf.site/","description":"","thumbnailUrl":"https://1eaf.site/favicon.ico","sameAs":["https://github.com/leaf-nam"]}</script></head><body class=list id=top><script>localStorage.getItem("pref-theme")==="dark"?document.body.classList.add("dark"):localStorage.getItem("pref-theme")==="light"?document.body.classList.remove("dark"):window.matchMedia("(prefers-color-scheme: dark)").matches&&document.body.classList.add("dark")</script><header class=header><nav class=nav><div class=logo><a href=https://1eaf.site/ accesskey=h title="LEAF (Alt + H)">LEAF</a><div class=logo-switches><button id=theme-toggle accesskey=t title="(Alt + T)"><svg id="moon" xmlns="http://www.w3.org/2000/svg" width="24" height="18" viewBox="0 0 24 24" fill="none" stroke="currentcolor" stroke-width="2" stroke-linecap="round" stroke-linejoin="round"><path d="M21 12.79A9 9 0 1111.21 3 7 7 0 0021 12.79z"/></svg><svg id="sun" xmlns="http://www.w3.org/2000/svg" width="24" height="18" viewBox="0 0 24 24" fill="none" stroke="currentcolor" stroke-width="2" stroke-linecap="round" stroke-linejoin="round"><circle cx="12" cy="12" r="5"/><line x1="12" y1="1" x2="12" y2="3"/><line x1="12" y1="21" x2="12" y2="23"/><line x1="4.22" y1="4.22" x2="5.64" y2="5.64"/><line x1="18.36" y1="18.36" x2="19.78" y2="19.78"/><line x1="1" y1="12" x2="3" y2="12"/><line x1="21" y1="12" x2="23" y2="12"/><line x1="4.22" y1="19.78" x2="5.64" y2="18.36"/><line x1="18.36" y1="5.64" x2="19.78" y2="4.22"/></svg></button><ul class=lang-switch><li>|</li></ul></div></div><ul id=menu><li><a href=https://1eaf.site/posts/concept/ title=개념정리><span>개념정리</span></a></li><li><a href=https://1eaf.site/posts/review/ title="개발서적 리뷰"><span>개발서적 리뷰</span></a></li><li><a href=https://1eaf.site/search/ title=검색><span>검색</span></a></li><li><a href=https://1eaf.site/posts/ title=게시글><span>게시글</span></a></li><li><a href=https://1eaf.site/posts/tips/ title=미세팁><span>미세팁</span></a></li><li><a href=https://1eaf.site/posts/coldcase/ title=미제사건><span>미제사건</span></a></li><li><a href=https://1eaf.site/archives/ title=아카이브><span>아카이브</span></a></li><li><a href=https://1eaf.site/categories/ title=카테고리><span>카테고리</span></a></li><li><a href=https://1eaf.site/posts/cote/ title=코딩테스트><span>코딩테스트</span></a></li><li><a href=https://1eaf.site/tags/ title=태그><span>태그</span></a></li><li><a href=https://github.com/leaf-nam/blog title=Git><span>Git</span> <svg fill="none" shape-rendering="geometricPrecision" stroke="currentcolor" stroke-linecap="round" stroke-linejoin="round" stroke-width="2.5" viewBox="0 0 24 24" height="12" width="12"><path d="M18 13v6a2 2 0 01-2 2H5a2 2 0 01-2-2V8a2 2 0 012-2h6"/><path d="M15 3h6v6"/><path d="M10 14 21 3"/></svg></a></li></ul></nav></header><main class=main><article class="first-entry home-info"><header class=entry-header><h1>낙엽의 블로그 🍃</h1></header><div class=entry-content><p>Leaf, waiting for Spring | 봄을 기다리는 낙엽</p><blockquote><ul><li><strong>봄</strong>을 찾아 군에서 세상밖으로 나온 <strong>백엔드 개발자</strong>입니다.</li><li>많은 사람들에게 쓰임과 도움이 된다면 그걸로 좋습니다.</li></ul></blockquote></div><footer class=entry-footer><div class=social-icons><a href=https://github.com/leaf-nam target=_blank rel="noopener noreferrer me" title=Github><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 24 24" fill="none" stroke="currentcolor" stroke-width="2" stroke-linecap="round" stroke-linejoin="round"><path d="M9 19c-5 1.5-5-2.5-7-3m14 6v-3.87a3.37 3.37.0 00-.94-2.61c3.14-.35 6.44-1.54 6.44-7A5.44 5.44.0 0020 4.77 5.07 5.07.0 0019.91 1S18.73.65 16 2.48a13.38 13.38.0 00-7 0C6.27.65 5.09 1 5.09 1A5.07 5.07.0 005 4.77 5.44 5.44.0 003.5 8.55c0 5.42 3.3 6.61 6.44 7A3.37 3.37.0 009 18.13V22"/></svg></a></div></footer></article><article class=post-entry><header class=entry-header><h2 class=entry-hint-parent>백준 16236 아기 상어[java]</h2></header><div class=entry-content><p>출처 https://www.acmicpc.net/problem/16236 접근 알고리즘 시작지점부터 가장 가까운 물고기부터 탐색합니다. 문제 조건에서 주어진 물고기를 선택하는 기준을 만족하기 위해, Heap1에 다음 물고기를 넣어 정렬하였습니다. 다음 물고기가 먹을 수 있는 물고기라면, 해당 위치를 시작점으로 다시 BFS를 수행합니다. 시간복잡도 고민 BFS로 물고기를 먹으러 이동하면서 걸리는 시간 : O(N^2) 이동하면서 물고기를 정렬하는 시간(Priority Queue 사용 시) : O(NlogN) N = 20 이므로 시간복잡도 내 충분히 가능하다고 판단했습니다.
유의사항 PriorityQueue를 정렬할 때, Integer의 유틸리티 메서드인 compare()를 활용하면 좋다고 합니다....</p></div><footer class=entry-footer><span title='2024-07-08 18:05:08 +0900 KST'>2024. 7. 8.</span> · 4 분 · 643 단어 · Leaf</footer><a class=entry-link aria-label="post link to 백준 16236 아기 상어[java]" href=https://1eaf.site/cote/%EB%B0%B1%EC%A4%80_16236_%EC%95%84%EA%B8%B0_%EC%83%81%EC%96%B4/></a></article><article class=post-entry><header class=entry-header><h2 class=entry-hint-parent>백준 2573 빙산</h2></header><div class=entry-content><p>출처 https://www.acmicpc.net/problem/2573 접근 각 칸이 10이하이고 전체 칸은 10,000이므로 빙산을 모두 녹이려면 10 _ 10,000 _ 10,000이지만, 네 변이 노출되면 금방 사라지므로 완전탐색이 가능하다고 판단했습니다. 매 회마다 빙산을 녹이고, 빙산을 bfs(dfs)로 탐색해서 두 덩어리가 있는지 확인한다. 모든 빙산이 다 녹았지만 2개로 분리되지 않는 경우를 주의한다.1 풀이 package solving; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; /* * [조건] * 시간제한 : 1초, 메모리 제한 : 256MV * 이차원 배열의 크기가 300^2 이하이며 전체 칸의 개수는 10,000개 이하, 각 칸의 크기는 10 이하 * [풀이] * 각 칸이 10이하이고 전체 칸은 10,000이므로 빙산을 모두 녹이려면 10 * 10,000 * 10,000이지만, 네 변이 노출되면 금방 사라지므로 완전탐색 * 매 회마다 빙산을 녹이고, 빙산을 bfs로 탐색해서 두 덩어리가 있는지 확인한다....</p></div><footer class=entry-footer><span title='2024-06-27 11:35:43 +0900 KST'>2024. 6. 27.</span> · 3 분 · 612 단어 · Leaf</footer><a class=entry-link aria-label="post link to 백준 2573 빙산" href=https://1eaf.site/cote/%EB%B0%B1%EC%A4%80_2573_%EB%B9%99%EC%82%B0/></a></article><article class=post-entry><header class=entry-header><h2 class=entry-hint-parent>백준 1753 다익스트라</h2></header><div class=entry-content><p>출처 https://www.acmicpc.net/problem/1753 접근 각 정점에서 다른 정점으로의 최솟값을 다익스트라1를 통해 구합니다. 정점으로부터 최단거리의 간선으로만 이동하기 때문에 O(ElogV) ≈ 1,200,0002으로 모든 간선을 확인하는 것이 가능합니다. 탐색하는 간선 개수를 최적화하기 위해 LinkedList로 저장합니다.3 문제에서 주어진 예제를 그래프로 표현했습니다.
그래프 1 2 3 4 5 초기화 0 INF INF INF INF 1 -> 2, 3 0 2 3 INF INF 2 -> 3, 4 0 2 3 7 INF 3 -> 4 0 2 3 7 INF 5 -> 1 0 2 3 7 INF 위와 같이 거리 배열을 초기화한 후, 각 정점의 간선들을 탐색하며 배열을 채워나갑니다....</p></div><footer class=entry-footer><span title='2024-06-21 09:55:27 +0900 KST'>2024. 6. 21.</span> · 3 분 · 589 단어 · Leaf</footer><a class=entry-link aria-label="post link to 백준 1753 다익스트라" href=https://1eaf.site/cote/%EB%B0%B1%EC%A4%80_1753_%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC/></a></article><article class=post-entry><header class=entry-header><h2 class=entry-hint-parent>백준 1976 여행 가자</h2></header><div class=entry-content><p>출처 https://www.acmicpc.net/problem/1976 접근 일반적인 DFS로 구현하면 각 여행경로를 확인하는데 O(N^3)1가 소요됩니다. 도시가 1000개이므로 200 x 200 x 200 x 1000 = 8,000,000,000(80억)으로 시간초과가 발생합니다.
해당 문제에서는 다른 도시를 몇번이든 방문할 수 있기 때문에, 일일히 경로를 방문하는 것은 시간초과를 유발합니다. 이를 최적화하기 위해 모든 여행계획이 같은 네트워크(루트를 공유)에 포함되는지 확인하기만 하면 됩니다. 이는 유니온 파인드(Union-find)로 구현할 수 있습니다. 풀이 package solving; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /* * [조건] * 시간 제한 : 2초, 메모리 제한 : 128MB * N <= 200, M <= 1000 * [구현] * 유니온 파인드를 통해 연결그래프를 구하고, 주어지는 여행계획이 같은 루트에 속하는지 확인한다....</p></div><footer class=entry-footer><span title='2024-06-20 08:29:30 +0900 KST'>2024. 6. 20.</span> · 3 분 · 464 단어 · Leaf</footer><a class=entry-link aria-label="post link to 백준 1976 여행 가자" href=https://1eaf.site/cote/%EB%B0%B1%EC%A4%80_1976_%EC%97%AC%ED%96%89_%EA%B0%80%EC%9E%90/></a></article><article class=post-entry><header class=entry-header><h2 class=entry-hint-parent>백준 14503 로봇 청소기</h2></header><div class=entry-content><p>출처 https://www.acmicpc.net/problem/14503 접근 N, M <= 50, O(N^5) = 312,500,000 이므로 시간복잡도는 여유롭게 구현 가능합니다. 로봇 청소기의 이동 방식을 BFS로 구현했습니다. 다시 생각해보니 BFS형태가 아니더라도 구현 가능한데 습관적으로 BFS를 사용한 것 같습니다.
문제에서 주어진 방향설정이 중요합니다. 북(-1, 0), 동(0, 1), 남(1, 0), 서(0, -1)
친절하게 방의 둘레는 모두 벽(1)로 채워져 있기 때문에 ArrayIndexOutOfBoundsException1은 처리하지 않아도 됩니다. 풀이 package solving; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Queue; import java....</p></div><footer class=entry-footer><span title='2024-06-19 10:32:37 +0900 KST'>2024. 6. 19.</span> · 3 분 · 561 단어 · Leaf</footer><a class=entry-link aria-label="post link to 백준 14503 로봇 청소기" href=https://1eaf.site/cote/%EB%B0%B1%EC%A4%80_14503_%EB%A1%9C%EB%B4%87_%EC%B2%AD%EC%86%8C%EA%B8%B0/></a></article><footer class=page-footer><nav class=pagination><a class=next href=https://1eaf.site/page/2/>다음 페이지 »</a></nav></footer></main><footer class=footer><span>© 2024 <a href=https://1eaf.site/>봄을 기다리는 낙엽</a></span>
<span>Powered by
<a href=https://gohugo.io/ rel="noopener noreferrer" target=_blank>Hugo</a> &
<a href=https://github.com/adityatelange/hugo-PaperMod/ rel=noopener target=_blank>PaperMod</a></span></footer><a href=#top aria-label="go to top" title="Go to Top (Alt + G)" class=top-link id=top-link accesskey=g><svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 12 6" fill="currentcolor"><path d="M12 6H0l6-6z"/></svg>
</a><script>let menu=document.getElementById("menu");menu&&(menu.scrollLeft=localStorage.getItem("menu-scroll-position"),menu.onscroll=function(){localStorage.setItem("menu-scroll-position",menu.scrollLeft)}),document.querySelectorAll('a[href^="#"]').forEach(e=>{e.addEventListener("click",function(e){e.preventDefault();var t=this.getAttribute("href").substr(1);window.matchMedia("(prefers-reduced-motion: reduce)").matches?document.querySelector(`[id='${decodeURIComponent(t)}']`).scrollIntoView():document.querySelector(`[id='${decodeURIComponent(t)}']`).scrollIntoView({behavior:"smooth"}),t==="top"?history.replaceState(null,null," "):history.pushState(null,null,`#${t}`)})})</script><script>var mybutton=document.getElementById("top-link");window.onscroll=function(){document.body.scrollTop>800||document.documentElement.scrollTop>800?(mybutton.style.visibility="visible",mybutton.style.opacity="1"):(mybutton.style.visibility="hidden",mybutton.style.opacity="0")}</script><script>document.getElementById("theme-toggle").addEventListener("click",()=>{document.body.className.includes("dark")?(document.body.classList.remove("dark"),localStorage.setItem("pref-theme","light")):(document.body.classList.add("dark"),localStorage.setItem("pref-theme","dark"))})</script></body></html>