오늘 공부한 내용 : 그리디가능한 선에서 최대 혹은 최소의 극단적인 경우를 계속 적용함일단 문제를 보고 그리디가 안될 케이스를 바로 떠올려보고, 쉽게 그런 케이스가 떠오른다면 DP등 다른 방식으로 선회하자도저히 그리디를 안하고 못버티겠단 생각이 들면 적용어디 코테에서든
구현의 두 가지 종류완전탐색 : 모든 경우의 수를 전부 시도(계산)해 봄시뮬레이션 : 문제에 제시된 알고리즘을 차례대로 수행
최소직사각형 - 문제링크간단한 문제다.복잡하게 생각하기 쉽지 않다.나 정도 되는 바보여야지 복잡하게 생각한다.스포주의여튼간에 답에서 원하는거는 면적이다.가로, 세로 중 하나를 기준으로 잡고각 명함의 가로, 세로 중 큰 값을 그 기준에 넣어준다그리고 마지막에 그래서 전체
행렬 테두리 회전하기LV2 문제이지만 딱히 할 말 없다.처음엔 문제를 보고 뜨악했지만(쿼리인가? 맙소사 구간에서 최대 최소? 뭐지? 뭐지?) 자세히 보니 요구조건에 시간이나 효율성 등 언급이 없다.그냥 구현 문제라는 뜻이다.그냥 배열을 돌리면 된다.사실 이렇게 배열을
숫자 문자열과 영단어문자열을 다루는 문제이다.사실 문자열 문제를 볼 때마다 살짝 마음이 무거워진다.옆집 python은 그렇게 문자열을 다루기 쉽다던데..문자열 문제들은 웬만하면 LV 1이라지만 체감이 높고다양하게 풀 수 있는 것 같다.물론 나는 멍청이라 이번에도 멍청하
오픈채팅방문자열을 다루는 문제이다.LV2 !! 문제 !! 지만 사실 문자열이라는 주제에 한정해서는LV이라는게 그렇게 중요한가..? 싶기도 하다.아무래도 역시나 문제를 풀면서 느끼는 것은아 진짜 python 갈아타야 하나..하는 것이다.'python 이면은 split()
소수 만들기일단 소수(prime number)에 관한 문제면아마 어느정도 알고리즘 공부를 해 보신 분들은에라토스테네스의 체가 떠오를 것이라고 생각한다.그걸로 범위 내의 소수를 걸러낸 후에결국 nums 안에 존재하는 3개짜리 조합을 다 찾으면 된다.dfs를 하면 되겠지
LCS 2이번 문제는 DP에 있어서유명한 문제 중 하나인LCS(Longest Common Subsequence)의 연장선이다.(백준에 실제로 기본적인 LCS문제가 존재한다.)대부분의 수학문제도, 알고리즘 문제도 그렇듯이기본 개념을 어떻게 활용시키느냐, 가 초점 아니겠
보물섬이 문제는 그래프 문제이고 인접 행렬의 BFS와 관련된 문제이다.1\. 인접 행렬에서의 BFS를 어떻게 처리하는가?2\. 인접 행렬에 BFS를 적용할 때 시간복잡도를 알고 있다면 무리없이 풀 수 있다.사실 원래 몰랐더래도 간단히 생각해보면이차원 행렬에 대해 BFS
더 맵게이 문제는 heap 관련 문제이다heap은 heap property를 만족시키는 완전이진트리이다.여기서의 heap property는부모 노드의 키 값과 자식 노드의 키 값 간의 대소관계를 의미한다.부모 노드의 key값이 자식 노드의 key값 보다 항상 크다면 최
모의고사이 문제는 완전탐색 문제이다.완전탐색이라는건 한마디로 전부 다 뒤져본다는 뜻이다.사실 크게 어려운 게 없는 문제이다그냥 전체 돌리면 된다규칙을 어떻게 적용하냐는 사람마다 다르겠지만사실 규칙도 그리 어렵지는 않아서..그냥 하시면 됩니다.너무 간단한 문제라 소스코드
체육복그리디 알고리즘(Greedy algorithm) 문제이다한국어로는 욕심쟁이 알고리즘 이랬나번역이 아주 마음에 든다항상 그 상황에서 조건에 따라 할 수 있는최선의 작업을 수행하면 된다.물론 이렇게 직관적이고 쉽고 빠르기에안 통하는 경우가 있다. 사실 매우 많다.대표
오르막 수동적계획법을 사용하는 문제로써 백준에서는 대표적인 문제이다.동적계획법을 풀 때는 보통반복문으로 밑에서부터 쌓아올리는 bottom-up 방식과일단 재귀를 통해 부채를 쌓아두고 천천히 갚아나가는? 것 같은 top-down 형식 중 하나를 고르게 되는데이 둘 중에서
가장 먼 노드이 문제는 그래프 문제이다.사실 그래프에 대한 문제는 어느정도 정형화된 유형이 있기는 하다.보통 문제의 조건들과 더불어 그래프의 유형 (인접행렬 혹은 인접리스트)가 주어진다. 그 후 적절한 알고리즘을 찾아서 적용하면 된다. (말이 쉽지)내가 생각하기에 대충
타겟넘버그래프 관련 문제이다.그래프와 관련된 문제는 나의 많지 않은 코테 경험에서도(참고로 좋은 경험은 거의 없다 ㅎ)그래프 관련은 굉장히 자주 출제되었다.물론 저번에 그래프 문제를 처음 벨로그에서 다룰 때한 번 유형과 관련해서는 정리를 했다고 생각하기에여기서는 넘어가
성격 유형 검사하기이거는 그니까.. 문자열의 탈을 쓴 문제이지실제로 문자열로 다룰 건 없다.뭐라고 설명해야 하는거지..그냥 key로 Value를 찾는자료구조들 (C++, Java의 map, python의 dictionary 등등)사용법을 잘 알고 있다면어려움 없이 풀
키 패드 누르기이 문제도 간단한 구현 문제이다.케이스를 잘 나누면 된다.주의해야 할 점은 맨 처음 왼손과 오른손의 시작점인 \*와 어떻게 처리하냐 일 것이다.이것도 각자의 스타일이 있겠지만나는 맨 마지막 행의 \*,0,10, 11, 12라고 생각하고 풀기로 했다.그게
주차 요금 계산뭔가 문자열이지만 문자열이 아닌 것 같은 문제를 많이 만나다가다시 한번 강력한 친구를 만났다.사실 이 문제도 문자열을 다룬다고 할 만한 문제는 아닌가..싶기도 하다.C++ 기준으로 str.find()와 str.substr()을 이용한 문자열 나누기, 문자
N과 M(5)N과 M은 백준에 시리즈물로 쭈루루룩 있다.백트래킹의 연습을 하기 위한 문제이다.번호가 올라갈 때 마다 조건이 하나씩 추가되고 하는데이번문제는 숫자가 작은 순서대로 나오라는 것이다.그런데 사실 생각을 차분히 해보면순회하면서 백트래킹을 한다고 했을 때출력값이
요즈음은 그냥 solved.ac에서 클래스별로 문제를 풀고 있는데현재 티어까지 지나온 길을 확인하던 중내가 틀렸던 문제가 있길래 확인을 해봤다.신기하게도 ps에 C++을 사용하는 내가python으로 문제를 한 번 제출해서 틀렸었다. 무슨일일까..?문제는 여튼주어진 숫자