본문 바로가기

백준

 (10)
[C++] 14442 벽 부수고 이동하기 2 | 그래프 탐색, 3차원 방문 체크 교수님들이 쓰시는 표현을 빌리면, 나에게 너무 challenging하다.. 방문 체크 배열을 3차원으로 만들어야 하는 것이 특히 그렇다. 1. 문제 분석 https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 미로를 탐색하며 (0, 0)에서 (N-1, M-1)까지의 최단 경로를 찾아야 한다. 이때 부술수 있는 벽의 최대 개수만 지키면 되고 적게 벽을 부수든, 많이 부수든 관계 없다. 따라서 각 위치를 탐색하며 (0,..
[C++] 2293 동전1 | DP(Dynamic Programming) 비슷한 문제를 몇번 풀어본 것 같은데, 감이 잘 안 잡혔고 풀이를 읽어봐도 잘 이해가 안 됐었기 때문에 논리를 한번 정리해보려한다. 1. 풀이 우선 dp로 저장할 배열의 크기는 n * k + 1이다. dp[i][j]에 j원을 만드는 데 i번째 동전까지 고려하여 경우의 수를 저장한다. (i = 0, 1, ...) k가 아닌 k + 1인 이유는 0원을 만드는 경우를 1로 저장하여 뒷쪽 요소에서 활용하기 위함이다. 문제에 주어진 예시를 이용해 자세히 설명해보자. 3 10 1 2 5 dp[1][5]에 5원을 만드는데 1번째 동전까지 고려하여 경우의 수를 저장할 것이다. 즉, 1원과 2원으로 5원을 만드는 경우의 수가 저장된다. 이때 1번째 동전인 2원을 기준으로 하여 안 쓰는 경우와 쓰는 경우로 나누어 생각한다..
[C++] 2512 예산 | 이진탐색(Binary Search) 1. 이진 탐색 반복문에서 빠져나오는 부분을 깔끔하게 구현하는 것이 어렵다. 44~51 줄에서 고민을 많이 했는데, 다른 분들의 코드를 참고해서 수정해볼 예정이다. break를 쓰지 않고, while의 조건인 min
[C++] 2660 회장뽑기 | 그래프(Graph) 1. 간단한 그래프 탐색 문제이다. edge의 방향성에 대한 설명이 없으니 양방향 그래프다. 그래프 node와 edge 입력은 요새 벡터 리스트를 만들어 각 벡터요소가 하나의 node이고 edge로 연결된 node들을 벡터에 추가하는 방식을 자주 활용한다. 2. 회원 i를 root로 생각했을 때, 그래프의 depth가 '점수'가 된다. 문제 설명은 한번 읽으면 난해하게 느껴지지만, 예시를 한번 그려보면 쉽게 상황 파악이 된다. 3. 코드 #include #include #include #include using namespace std; int N; int BFS(vector *fri, int root) { bool *visited = new bool[N](); visited[root] = true; i..
여름방학 백준 스터디 후기 + 완벽주의 대한 생각 정리 어느새 대학에서의 마지막 학기가 개강했다. 방학 끝무렵에는 모든 의욕을 상실하고 게임만 한 것 같다. 4학년이 이렇게 시간을 날릴 수도 있구나.. 다시 마음을 잡아보고자, 여름방학 8주간 백준 스터디를 했던 경험을 정리해봐야 겠다. ps.. 백준 스터디는 학기 중에도 문제 수를 줄여 계속 진행하기로 했다. 1. 선정된 10개의 문제만 풀기에는 내 실력이 부족했다. 하지만 실력과 시간이 10개 마저도 풀기 어렵게 만들었다. 그럼 어떻게 해야 할까? 문제를 다 못풀더라도 몇몇 유형을 꼼꼼히 공부하는 방법과 특정 유형을 제대로 타파하지 못하더라도 꾸준히 숙제를 완성하는 방법이 있다. 두 방법 모두 좋은 방법이지만, '꼼꼼하게' 라는 것에 지나친 완벽주의로 스트레스를 받는 내 성향을 고려해서 두번째 방법으로 선..
[C++] 11000번 강의실 배정 - 문제 해결 Point 1. 문제 해결 Idea 문제를 읽고 처음 생각해낸 Idea는 일찍 끝나는 수업부터, 공백이 최소가 되도록 배치하자! 였다. 이 생각을 바탕으로 머리를 쥐어짜보고, 도저히 안돼서 다른 분들 풀이도 읽어보니 이 문제를 풀기 위한 (그리고 풀이를 이해하기 위한..) 가장 중요한 Point는 다음과 같다.. ^-ㅠ 배치 완료된 수업 목록은 끝나는 시간을 기준으로, 새로 배치할 수업은 시작 시간을 기준으로 생각해야한다. 2. 해설 ex) 입력 : 4 1 3 2 4 4 6 3 11 출력 : 2 배치 완료된 수업 목록은 sche 에 넣는다. 그럼 새로 배치할 수업은 sche 의 top인 "가장 일찍 끝난 수업"과만 만나서 합칠 수 있는지 여부를 체크할 것이다. -> 이때 "가장 일찍 끝난 수업"과도 합칠 수 없다면..
[백준 PS 스터디] 5주차 진단 너무 답답할 때가 많다. 거의 90%는 실버에서 푸는데, 떠오르는 아이디어들은 진부하게 느껴진다. 풀이법을 검색해보기는 너무 싫은데, 답답해서 몸에 열도ㅋㅋㅋ나고 짜증날 때 쯔음 검색해서 살짝 읽어보고 다시 풀면 너무나도 환상적으로 풀린다....... 그래서 도전의식을 자꾸만 높아지고 내 실력은 시간이 지나도 처참하고.. 나중에 PS 장인이 되면, 이런 상태는 어떤 level인지 마치 어렸을 때 영어학원가서 레벨테스트 보듯 진단해보고 싶다.
[무작정 백준 풀기] 3주차 느낀점 풀다보니 solved.ac에서 티어가 실버3이 되어있었다. ㅎㅎ 롤 티어보다도 높은!!ㅎㅎ 꾸준히 풀어서 골드도 찍어보고 싶다. 풀다가 든 생각들이 꽤 있는데, 정리해보지 못한 것 같아 아쉬워서 이제라도 하나하나 기록해보려한다. 1. 오늘 인상깊었던 점은 당연하게도 문제마다 정답 알고리즘이 있다는 것이다. 자료구조는 언어에 따라, 사람에 따라 조금씩 다를 수 있지만 알고리즘은 확실히 출제 의도에 따라 정답이 있다는 느낌을 받았다. 물론 무작정 사고력을 요하는 문제도 있을 것이고 해설이 여러개인 문제도 있겠지만, 문제마다 아주 딱 들어맞는 알고리즘이 있는 것 같다. 워낙 문제풀이 경험이 적어서 신기했는지도 모르겠다. 2. 또 놀랐던 점은 항상 완벽한 프로그램일 필요가 없고, 확률적으로 시간을 단축할 수 있..

티스토리툴바