공부하자

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net "가장 빠른 시간"을 구해야 하는 문제니 BFS를 적용하여 풀었다. 처음엔 그냥 산술적으로 브루트포스 같은것들을 적용시켜 도전하려 했으나, 주어지는 입력의 최댓값이 100,000이고, 제한시간이 2초니까 O(N^2)짜리 코드로 풀면 시간초과가 날것이다. 따라서, BFS를 이용하여 푸는쪽으로 방향을 잡았다. 그래프를 형태가 인접리스트로 주어지는것이 아니기 때문에 오로지 큐..

- 상승 출발 했던 코스피, 상승분 반납하며 강보합, 삼성전자 2%대 하락 - 日 증시 '버블붕괴' 후 33년10개월만에 최고 - 네이버페이, ‘주택담보대출 비교’ 출시 - 새해 초 부진했던 미국 증시 1월 둘째주 첫날에 큰 폭 상승, 나스닥지수 2.2% 상승, S&P500, 다우존스 1.4%, 0.6% 상승 - 오는 11일 개장 전 지난해 12월 소비자 물가지수(CPI) 발표 - 오는 12일부터 지난해 4분기 실적 발표 본격화 - 9일부터 12일까지 CES 개최 - 공공이 아닌 민간 주도 주택사업에 심의 기간 단축, 용적률 완화 등 각종 특례를 주는 '민간 제안 도심복합사업' 도입

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net BFS를 활용하면 금방 풀리는 문제이다. 입력으로 주어지는 그래프를 인접 리스트 형식으로 구현해놓고, BFS만 돌리면 끝이다. 다만 여기서 포인트는 BFS를 순회하면서 정점들을 기록하는것이 아닌 정점들의 갯수만 카운트 시키고, 마지막 출력할때에 카운트된 변수에서 1만 빼주면 된다. 문제에서 요구하는 출력 조건이 "1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수"이기 때문에 1번 컴퓨터 본인은..

- 코스피 2580선 상승 출발 - 외환 당국, 올해 외환시장 선도은행으로 국민은행, 산업은행, 신한은행, 우리은행, 제이피모간체이스은행, 크레디아그리콜은행, 하나은행 등 7개 은행 선정 - 삼성전자, 모두를 위한 AI 미래 비전 공개 - 삼성전자, 1년만에 분기 영업익 3조원대 복귀 전망 - 서울 아파트 10억->8억 낙찰, 경매시장 한파 지속 - 지난해 30대 전국 아파트 매입 비중 역대 최대, 전체의 26.7% 차지

- 상승폭 되돌리는 코스피, 2600선 회복 관건 - 골드만삭스, S&P 500 기업 작년 4분기 실적 시장 전망치 웃돌 것 - 태영건설, 지주사 살리기 오너일가에 격앙.. 정부는 법정관리 대비에 착수 - 미 재정감축 하지않으면 인플레이션 재발할것, 석학들 경고 - 두 전쟁에 세계경제 삼극화, 중장기적으론 달러 지위 약화될 것 - 미 법무부, 애플 반독점법 위반 행위로 기소 예정 => 5분기 연속 역성장, 폭스콘 매출 급감에 따라 이후 발표될 실적 위축 예상

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 이전에 한번 게시했던 문제인데, 애초에 백준 계정을 새로 파서 푼 흔적이 없어졌기 때문에 한번 더 풀었고, 최근에 DFS랑 BFS 개념을 다시 복습하면서 다시 한번 풀어보았다. 문제 자체에서 어려운점은 크게 없었던 것 같다. 그래프를 인접리스트 형태로 주어지는대로 입력받고 입력받은 그래프를 토대로 각각 DFS와 BFS를 적용하여 풀어내면 되는 문제이다. 필자는..

너비 우선 탐색이란? (breath First Search, BFS) 시작 정점을 경계에 추가하는 것으로 시작한다. 경계는 이전에 방문했던 정점들에 의해 구성되고, 현재 경계에 인접한 정점을 반복적으로 탐색한다. BFS의 중요한 특징은, 모든 정점에 대해 자식 정점을 손자 정점보다 먼저 방문한다는 점이다. 이를 구현할 때에는, 보통 경계를 별도의 자료구조로 만들어 명시적으로 사용하지 않고, 대신 정점 ID를 큐(Queue)에 저장하여 시작 정점과 가까운 정점을 멀리 있는 정점보다 먼저 방문할 수 있도록 구현한다. 다음은 너비 우선 탐색을 표현한 애니메이션이다. 두 애니메이션을 보면 그래프를 탐색함에 있어 무조건 같은 Level의 부모 정점들이 먼저 탐색되고, 그 다음 Level에 있는 자식 정점들이 나중..

그래프 탐색이란? 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것. 이때, 어떤 탐색 알고리즘을 쓰는지에 따라 방문하는 방식이 달라진다. 깊이 우선 탐색이란? (DFS, Depth First Search) 시작 정점에서 시작하여 특정 경로를 따라 가능한 멀리 있는 정점을 재귀적으로 먼저 방문하는 방식이다. 그리고 더 방문할 정점이 없어지면 다른 경로를 찾아 다시 멀어지는 방향으로 탐색을 반복한다. 이러한 그래프 탐색 방식을 백트래킹(Backtracking) 이라고 한다. 다음은 깊이 우선 탐색을 표현한 애니메이션이다. 애니메이션에서 연한 녹색으로 칠해지는것이 정점을 방문하는 절차이고, 진한 녹색으로 칠해지는것이 더 방문할 정점이 있는지 탐색하는 백트래킹 과정이다. 트리구조에서 전..

- 새해 들어 코스피 대비 코스닥 강세, 애플 충격, 금리 인하 기대감 둔화에도 상대적 강세 => 코스피는 3일 연속 하락, 하지만 코스닥은 반등 성공 - 3대 뉴욕증시 지수 소폭 상승 마감, 나스닥 0.09% 상승 - 이상기후, 전쟁 악재에도 작년 식량가격 14% 하락, 쌀, 설탕은 상승 - LVMH 사 프레데렉 아르노 태그호이어 CEO, 시계 부문 CEO 승진 => 태그호이어, 위블로, 제니스 등등 - 애플 최대 협력업체 폭스콘 23년 4분기 매충 5.4% 감소 - 미 연준, 금리 인하 아직 일러 - 전세 사기 피해자 10명 중 7명 2030, 1억 이하 소액이 최대, 수도권 중심으로 피해

https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 문제 요구조건은 꽤 간단하다. 전위순회로 주어진 트리를 후위순회로 변환하면 끝이다. 이때 중요한 키 포인트는 세가지가 있다. 1. 전위순회에서 가장 첫번째 노드는 루트 노드이다. 2. 전위순회에서 루트노드보다 커지는 첫번째 원소를 기점으로 왼쪽, 오른쪽 자식트리가 나뉘게 된다. 3. 나뉜 자식트리에 대하여 1~2의 과정을 재귀 형태로 반복하고, 그 과정에서 맨 첫번째 노드(루트 노드)..