1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 핵심요소 DFS와 BFS의 정지 요건을 어떤식으로 지정해야 하는가? 인접행렬을 어떠한 방식으로 구현해야 하는가? 문제풀이 그래프를 표현하는 대표적인 방법인 인접 행렬을 구성하여 문제를 풀어야할 것 같다. 각 간선간의 이동 방향이 지정되지 않은 무방향 그래프 이므로 인접 행렬이 대칭으로 구현된다. 이제는 문제를 구현해보자. DFS > BFS 순으로 정답을 도출해내야 하기 때문에 DFS에서는 방문한 List를 저장하고 BFS에서..
1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 핵심요소 큐를 어떻게 회전시킬 수 있을까? 큐를 언제 좌,우로 회전시켜야 할까? 문제풀이 큐를 좌측으로 회전시킬 때는 List에서 첫 번째 인자를 뺀 후 뒤에 삽입하고, 큐를 우측으로 회전시킬 때는 List에서 마지막 인자를 뺀 후 맨 앞에 삽입하면 된다. 이러한 형태로 큐 회전 함수를 구현해보았다. 그러면 큐를 언제 회전시켜야 할까? 큐를 회전시킬 때 가운데를 기준으로 왼쪽으로 가까울수록 좌측회전이 이동 경로가 짧고 가운데를 기준으로 오른쪽으로 갈수록 우측..
2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 핵심요소 잘린 나무의 총 길이를 어떠한 방식으로 계산할 수 있을까? 절단기의 높이 조절의 기준을 무엇으로 해야 할까? 문제풀이 잘린 나무의 총 길이는 현재의 높이에서 잘릴 수 있는 모든 나무를 비교하면서 값을 하나씩 추가하도록 하자. 절단기의 높이는 잘린 나무의 길이가 원하는 값보다 클 경우 높이고, 잘린 나무의 길이가 원하는 값보다 낮을 경우 낮추도록 한다. 일반적인 브루트 포스로 문제를 풀이하기에는 1초라는 시간이 부족..
2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) www.acmicpc.net 핵심요소 매일마다 올라가는 총 높이는 몇인가? 문제풀이 하루에 올라갈 수 있는 높이에서 미끄러지는 높이를 빼면 매일 올라갈 수 있는 총 높이가 나온다 그러면 매일 마다 올라갈 수 있는 높이를 막대의 총 길이에서 나누면 해결되지 않을까? 어? 뭔가 이상하다 도착한 후에는 더는 미끄러지지 않는데 미끄러지는 것까지 계산해버린 것 같다. 그러면 총 높이에서 1번 미끄러지는 것을 빼고 계산을 하면 될 것 같다. 첫 번째 예시에 있는 결과가 나왔지만, 뭔가 하나 빠트린 게 있는 것 같다. 다른 예시를 사용해서 테스트해 보도록 하자..
백준 1436번 문제입니다. 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 핵심요소 처음 시작되는 숫자 666 ~ 임의의 숫자까지 Loop를 돌면서 666이 포함된 수를 찾는 것 666을 찾을 때 쓰는 방법은 어떻게 확인해야 하는가? 문제풀이 1. 요소처럼 문제의 첫 시작은 for 문을 돌면서 666 ~ 임의의 숫자까지 Loop를하면서 해당하는 요소가 발견되었을 경우 카운트를 추가 시켜 몇 번째 해당하는 수 인지 확인하도록 설정합니다. 임의의 숫자는 10,000,000으로 지정합니다. 2. 파이썬에는 in..
오늘 한일 알고리즘 마라톤 38 ~40번 문제를 풀었습니다. 마지막 남은 문제들은 난이도가 높지 않아 손쉽게 풀 수 있었고, 2가지의 브루트 포스 문제를 DFS방식으로 풀이하면서 부족한 DFS 지식을 최대한 활용하면서 머릿속에 넣을려고 노력하였습니다. 드디어 권장 진도를 전부 풀이하였습니다. 알고리즘 마라톤을 진행하면서 아직까지도 머릿속에 들어오지 않는 문제들이 있었습니다. 이런 문제들을 따로 체크해 반복학습하여 저의 지식으로 만들도록 노력해야겠다는 마음을 먹었습니다. 오늘 배운 것 알고리즘 마라톤 38 ~ 40번 문제 풀이 알고리즘 인터뷰 다익스트라 알고리즘 챕터 풀이 내일 할 것 알고리즘 마라톤 체크 문제 오답노트 및 풀이 알고리즘 인터뷰 풀이
오늘 한일 알고리즘 마라톤 36 ~ 37번 문제를 풀었습니다. 두 문제 모두 DFS를 기반으로한 백트래킹 문제이자, 다이나믹 프로그래밍 문제였습니다. 재귀함수에 대한 기본적인 개념은 이해하고있지만, 그것을 실제 적용하면서 다이나믹 프로그래밍으로 적용하는것이 쉽지 않다는 것을 깨달았습니다. 알고리즘 인터뷰를 10문제 보았습니다. 그리디 알고리즘, 다익스트라 알고리즘, 다이나믹 프로그래밍 파트를 확인하였고, 개념에 대해 이해하려고 노력했습니다. 오늘 배운 것 알고리즘 마라톤 36 ~ 37번 문제 풀이 알고리즘 인터뷰 10문제 확인 내일 할 것 알고리즘 마라톤 문제 풀이 알고리즘 인터뷰 풀이 코드잇 기본 강의 풀이
오늘 한일 항해톡 1회 발표영상을 편집했습니다. 녹화 화면에서 웹캠으로 크루원들과 튜터님의 얼굴이 노출되서 바로 유튜브에 올리기는 힘들다 생각하였고, 화면을 잘라서 올려야겠다는 생각을 했습니다. Adobe Premiere 로 튜토리얼 영상을 보면서 화면자르기, 해상도 조절, 블러효과를 사용해보았으며, 영상에서 의미없는 부분을 cut하면서 영상을 편집하였습니다. 2주차 WIL 작성을 하였습니다. 저번주의 WIL은 작성이 1시간 30분가량 걸렸던 것으로 기억하는데, 이번주는 항해톡 발표와 알고리즘 마라톤으로 인해 추가해야할 자료가 많았던 것 같습니다. 오늘 배운 것 항해톡 발표자료 Youtube 업로드 WIL 작성 내일 할 것 알고리즘 마라톤 문제 풀이 알고리즘 인터뷰 풀이
서론 6/14 ~ 6/23의 알고리즘 마라톤 일정이 시작되었습니다. Node.js, Spring Q&A 세션이 진행되었습니다. 항해톡 1회 발표가 진행되었습니다. 일정 6/14 (월) ~ 6/23 (수): 알고리즘 마라톤 일정 6/14 (월) : 알고리즘 특강 6/15 (화) : 1회 항해톡 6/16 (수) : Node.js QnA 세션 6/17 (목) : Spring QnA 세션 및 1회 알고싶니즘 6/18 (금) ~ 6/19 (토) : 주특기 면담 알고리즘 마라톤 10일간의 총 60문제의 풀이를 위한 알고리즘 마라톤 일정이 시작되었습니다. 권장 문제는 40문제이며, 매일 4문제씩 푼다면 권장 문제 풀이까지 가능합니다. 난이도는 하하 ~ 중상까지 다양하게 있으며, 40문제 ~ 60문제 까지는 중 ~ 중..
오늘 한일 알고리즘 마라톤 30~35번 문제를 풀었습니다. DFS, 백트래킹 등 재귀함수를 활용해서 푸는 문제들이 많았었고, Base case부터 논리적인 접근으로 어떤 구조로 동작하는지에 대해서는 대략적으로 이해를 하고 있지만, 재귀함수로 구현하면서 어떠한 방식으로 동작을 시켜야 할 지가 가장 애매했던 문제였습니다. 알고리즘 풀이도중 수열, 조합, 순열 등 수학과 관련되서 나온 문제들이 많았습니다. 구현을 하기위해 어느정도의 수학적 지식이 필요해 유튜브를 참조해서 문제를 풀었고, 관련된 알고리즘들에 대한 식을 공부해야될 것 같습니다. 오늘 배운 것 알고리즘 마라톤 30 ~ 35번 문제 풀이 DFS, BFS, 백트래킹 등 재귀함수 풀이 알고리즘 인터뷰 책 풀이방법 내일 할 것 일주일간의 재정비 항해톡 발..
