오늘 배운 것그래프 탐색: BFS, DFSDFS: 스택, 재귀 함수로 푸는 방법이 있는데, 나는 주로 재귀 함수를 사용해서 풀이했다.BFS: 큐를 기반으로 사용한다. 아직 생소한 구현 방법이라 연습이 더 필요할 것 같다..! 해야 할 것못 푼 알고리즘 문제 마무리(창고 다각형...)도커, redis 공부하기! 벌써 알고리즘 2주차가 마무리 되어 가고 있다.내일 코테 보는데 잘 봤으면 좋겠고..!2주 동안 수많은 알고리즘 문제를 풀고, 새로운 개념도 많이 알아가면서 정말 재미있었다. 특히 새로 배운 것을 다루는 데에 익숙해질 때, 어려운 문제를 끝까지 풀어낼 때 그 쾌감은 이루어 말할 수 없었다.하지만 아직 알고리즘에서 부족한 것이 많아 알고리즘 주차가 끝나고도 꾸준히 문제는 풀어 볼 예정이다. 시간이....
https://www.acmicpc.net/problem/2805 문제상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 ..
https://www.acmicpc.net/problem/11399문제인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지..
https://www.acmicpc.net/problem/1377문제버블 소트 알고리즘을 다음과 같이 C++로 작성했다.bool changed = false;for (int i=1; i A[j+1]) { changed = true; swap(A[j], A[j+1]); } } if (changed == false) { cout 위 소스에서 N은 배열의 크기이고, A는 정렬해야 하는 배열이다. 배열은 A[1]부터 사용한다.위와 같은 소스를 실행시켰을 때, 어떤 값이 출력되는지 구해보자.입력첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에..
오늘 배운 것힙(heap) - O(logN)특정 규칙을 따르는 완전 이진 트리 구조heapq 라이브러리: 최솟값을 우선순위로 하는 힙heapify: 리스트를 힙으로 변환heappush, heappopex) 우선순위 큐, 힙 정렬해시 테이블(hash table) - O(1)키를 사용하여 데이터를 효율적으로 저장하고 검색하는 배열 기반 자료구조해시 함수를 사용해 키를 배열의 인덱스로 변환해서 데이터 저장key와 value를 매핑한 자료 구조라이브러리: dictionary, collections.defaultdict알고리즘에서 힙과 해시를 만난 건 처음이라 생소하지만 기존에 사용하던 것들을 거의 그대로 사용해서 아직은 괜찮은 것 같다..! 그저 정렬이 걱정될 뿐 😇알고리즘을 공부하기 시작한 지 한달 반 정도..
문제그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.입력첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.출력첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.예제 입출력..
2주차에 접어드니 저번 주는 정말 연습 게임한 것 같은 기분이었다.TIL을 빼먹은 사이에 많은 일이 있었다,,, 코딩테스트에 참패하고 내가 얼마나 부족한지 뼈저리게 느꼈고다음 알고리즘 문제를 대비하기 위해 BFS, DFS도 미리 준비하고 있는데, 이걸 내가 완전히 이해하고 백지에서부터 완전히 구현하기까지 많은 시간이 필요할 거 같다는 생각이 들었다...그와중에 틀린 코테 문제는 지금까지도 해결 못 하고 있는데, 진도가 지지부진한 상태이다..언젠ㄱ ㅏ할 수 있겠지..?😂 오늘 배운 것스택큐덱나의 부족함,,,✅ 해야 할 것 BFS/DFS 마저 공부하기도커 배포 공부하기코테 문제 해결하고 정리하기하루가 부족해😥 항해 개발자 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다.https://hanghae99..
https://www.acmicpc.net/problem/1018 문제지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후..
어제 하루 푹 쉬고 놀기만 했더니 그새 감을 잃어버렸다,,그리고 내가 짠 코드인데 뒤늦게 보니 이해를 못 했다는 건,, 나도 정확히 이해를 못 했다는 뜻이기도 하니 더 꼼꼼히 살펴보고 분발해야 겠다.이제 일요일이라고 놀지 말고 조금씩이라도 문제를 풀어봐야 겠다ㅠㅠ! 오늘 배운 것2차원 배열기능을 분리해서 로직을 구현할 것!(되도록이면 크게,,) 해야 할 것1. 오늘 추가 문제 마저 풀기2. 체스판 문제 정리하기 항해 개발자 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다.https://hanghae99.spartacodingclub.kr/reboot