분류 전체보기 (106) 썸네일형 리스트형 백준 9205 맥주 마시면서 걸어가기 - c++ 플로이드 와샬 풀이 문제 링크 www.acmicpc.net/problem/9205 풀이 아이디어 dfs bfs 말고 플로이드 와샬로 풀었다. x,y좌표를 한꺼번에 담아야 하므로 pair 꼴의 배열을 준비했다. 코드를 편하게 짜기 위해 갈수 있냐없냐를 bool 함수로 준비했고, 편의점 n개, 시작점 끝점 1개씩을 저장할 수 있는 d 이차원 배열 역시 준비했다. 적당히 큰 값으로 d 배열을 초기화 한 후, 한 포인트에서 다른 포인트로 갈 수 있으면 그 값을 1로 바꾸었다. 그리고 플로이드 와샬을 통해 경로를 최적화 한 후, d[0][n+1] 값을 비교해 (출발-끝 거리) 결과를 뽑아내면 된다. 코드 #include using namespace std; pair point[102]; int t,n; int d[102][102];.. 백준 1620 - 나는야 포켓몬 마스터 이다솜 문제링크 www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 www.acmicpc.net 풀이 아이디어 백준 풀면서 본 문제중 문제길이 제일 긴듯;;ㅋㅋㅋ 문제 자체는 쉽다. map 자료구조에 key,value쌍, value,key쌍 번갈아서 이렇게 두번 넣고 찾기만 하면 끝. c++로 풀 경우 입출력 속도에 주의하기 위해 반드시 첫 세줄은 넣도록 하자. 안넣으니 시간초과 나더라. 코드 #include using namespace std; int a,b; map.. [펌] 데브옵스 엔지니어가 공부해야 하는 것? brunch.co.kr/@topasvga/1385 69.DevOps 엔지니어가 공부해야 하는것? DevOps 엔지니어가 공부해야 하는것? Cloud Linux AWS cloud formation Ansible Terraform Git IT Infra전문가 되기 네트워크 이해하기 이미지 출처 : https://cordelia273.space/7 Cloud 1. 구글 brunch.co.kr 210106 백준 250문제를 풀고 느낀 점 200124 100문제 달성 200213 150문제 달성 200417 200문제 달성 210106 250문제 달성 50문제 더 푸는데 8달 반정도가 걸렸다. 9~10월 두달 제외하고는 그닥 많이 놀지는 않았었는데, 알고리즘에 소홀했던 건 팩트다. 그래서 요새는 퇴근하고 놀거나 딱히 그러지 않고 백준 붙잡고 파는 중. 4월까지는 솔직히 구현력이나, 풀이 아이디어, 알고리즘 사용능력 폼이 많이 올라온 상태였다. 알고리즘 공부한지 4달도 안된 시기였으나 그 4달을 알고리즘에 많이 시간투자를 한 결과였다. 8달 반 쉬고, 1월 시작한 이후부터 다시 초심잡고 차근차근 해나가고 있다. 쉬어보고 다시 잡아보니, 실버 문제들 중에서도 버거운 문제들이 등장하기 시작. 다행히 예전 짬이 있어서 어떤 문제를 보면 아 무슨 .. 백준 2565 전깃줄 - 아이디어가 중요한 DP 문제 문제 링크 www.acmicpc.net/problem/2565 풀이 아이디어 아이디어가 되게재밌다. 우선 전기줄이 '겹치게 되는는' 조건이 어떻게 되는지를 한번 생각해 봐야된다. 왼쪽 전봇대에서 위 아래로 시작하는 줄이 오른쪽 전봇대에서 아래 위로 끝나면 겹치게 된다. 근데 이렇게 생각하기 시작하면 개인적으로 좀 어려워 진다고 생각한다. 하나 기준을 정해야 한다. 왼쪽 전봇대로 정하는 것이 편하다. sort가 편하기 때문이다. 그러면 왼쪽 기준으로 정렬 되어있는 상태에서 for문을 돌릴 때, 오른쪽 에서 대소관계의 순서가 유지되면 안겹치는 것이다. 문제의 그림을 예시로 들자면 A를 기준으로 오름차순 정렬을 한 후 탐색을 진행하는 것이다. 1,2에서 시작하는 전기줄은 각각 8,2에서 끝난다. 1,2를 볼 .. 백준 2644 촌수계산 - bfs에서 메모리초과가 안뜨게 하려면? 문제 링크 www.acmicpc.net/problem/2644 풀이 아이디어 최단거리 문제니까 당연히 dfs가 아닌 bfs를 이용해서 푸는 것이다. 노드번호와 cost의 쌍을 큐에 넣고 bfs돌리면 쉽게 풀 수 있다. 문제는 메모리! 아래 주석 친 부분에 처음에 if-return문을 넣었다가 메모리 초과가 떴었다. BFS 조건 판단은 반드시 방문여부 체크한 후에 하기!! 코드 #include using namespace std; vector tree[101]; bool visited[101]; int bfs(int a, int b){ queue q; q.push({a,0}); visited[a]=true; while(!q.empty()){ int front = q.front().first; int cos.. ACM craft - 테스트케이스 while(t--) 스타일 문제, 위상정렬 문제 링크 www.acmicpc.net/problem/1005 풀이 아이디어 fill_n을 통한 메모리 관리 및 초기화 전형적인 위상정렬 문제 위상정렬은 항상 '조상 개수 0인 노드 queue에 넣고 문제에 맞는 해당 작업 진행하기' 임을 기억하기. 코드 #include #include #include #define N 1005 using namespace std; int ans; int n, k, w; int dp[N] = {}; int arr[N] = {}; int inDegree[N] = {}; vector v[N]; queue q; void f_initialize(int n) { fill_n(dp, n + 1, 0); fill_n(arr, n + 1, 0); fill_.. 백준 3190 뱀 - 앞뒤로 넣고 빼야 될 때는 deque를 활용하자! 문제 링크 www.acmicpc.net/problem/3190 풀이 아이디어 아이디어 랄건 딱히 없는데 구현을 잘 해야 풀 수 있는 문제다. 뱀의 머리와 꼬리를 이동시키고, 복제시키고 하는 로직때문에 머리꼬리를 동시에 관리해야 한다. 이럴 경우에 적합한 자료구조는 deque라고 널리 알려저 있기 때문에 deque을 사용해서 변수를 관리한다. 주의해야 할 점을 몇 가지 적자면 1. 뱀의 몸통이랑 부딪히는 것까지 생각을 해야 하므로 bool snake[][] 배열을 만들어, 뱀이 있는 공간은 true로 설정을 한다. 2. 명령이 L개 주어지는데, 명령이 있을 때만 명령을 읽고 처리하기 위해 if(opdq.size()) 조건이 꼭 필요하다. 만약 명령이 담긴 deque인 opdq의 size가 0일때는 그냥 실.. 이전 1 2 3 4 5 6 ··· 14 다음
