c++ 알고리즘

기록노트

15. 소수의 개수, 16. 아나그램

선생님 퀴즈, 층간소음, 분노유발자, 가위바위보

카드게임, 온도의 최대값

33,35,37,38

병합정렬

40. 교집합, 41. 연속된 자연수의 합

42. 이분검색

43. 뮤직 비디오

프로그래머스: 징검다리 건너기, 45. 공주 구하기, 46. 멀티태스킹, 47. 봉우리, 48 각 행의 평균과 가장 가까운 값, 49. 블록의 최댓값

50,51. 영지(territory) 선택 : (small),(large), 52. uglyNumbers

54. 올바른 괄호(stack), 55. 기차 운행 57. 재귀함수를 이용한 이진수 출력

60. 합이 같은 부분집합(DFS : 아마존 인터뷰)

60. 합이 같은 부분집합(DFS : 아마존 인터뷰)

61. 특정 수 만들기(DFS : MS 인터뷰) 62. 병합정렬

64. 경로탐색, 65. 미로탐색, 66. 경로탐색(인접리스트) 68. 최소비용(인접리스트)

70. 그래프 최단거리(BFS)

71. 송아지 찾기(BFS : 상태트리탐색), 72. 공주 구하기(큐 자료구조로 해결) 73,74. 최대힙, 최소힙 (priority_queue : 우선순위 큐)

75. 최대 수입 스케쥴(priority_queue 응용문제)

76. 이항계수(메모이제이션) 77. 친구인가? (Union&Find 자료구조)

78. 원더랜드(Kruskal MST 알고리즘 : Union&Find 활용)

79. 원더랜드(Prim MST 알고리즘 : priority_queue 활용)

다익스트라 알고리즘1-1. 개요다익스트라(dijkstra) 알고리즘은 그래프에서 한 정점(노드)에서 다른 정점까지의 최단 경로를 구하는 알고리즘 중 하나이다. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하며 각 정점까지의 최단 경로를 모두

오랜만에 알고리즘 문제를 다시 꾸준히 풀어보겠다는 다짐에 백준에 들어가봤다. Dynamic프로그래밍 문제중에 고르다가 처음에는 계단 오르기라는 문제를 풀어보려 했는데, 생각할수록 풀이가 너무 복잡해져서 포기하고 더 만만해 보이는 문제를 찾다가 풀게 됐다. Dynamic Programing의 가장 기본 예시중 하나인 피보나치수를 이용하는 문제였다. 그...

count 배열에 해당 수까지 연산 횟수의 최솟값을 저장한다. 주어진 n부터 1까지 count배열을 탐색하면서 값을 업데이트한다. 다이나믹 프로그래밍은 결국에 다 해보되, 같은 연산을 반복하지 않도록 하는 것 같다. 다이나믹 프로그래밍에 해당하는 문제인 걸 알고 있었는데도 방법을 생각하는데 시간이 좀 걸렸다.

Silver 3

Silver 4

학교에서 그리디 알고리즘을 배울 때 접한 적이 있는 문제였기 때문에 생각하는데 오래 걸리지 않았다. 결국 최대한 많이 회의실을 이용하도록 하기 위해서는 가능하다면 끝나는 시간이 빠른 순서대로 배정하는 것이 가장 최적의 방법이다. 조금 디테일이 추가된 것이 끝나는 시간과 시작 시간이 동일한 경우가 주어지는 것인데, 처음에는 종료시간이 같은 경우 시작...

어찌어찌 테스트케이스는 정확하게 답이 나오는 걸 확인했는데, 시간초과가 계속 나왔다. 아무리 생각해도 반복문 한 번에 해결할 방법은 없는 것 같아서 최대한 효율적으로 탐색하기 위해 check 배열을 이용해 이미 탈락한 경우에는 비교하지 않고 비교의 주체가 되지도 않도록 하였다. 두번째로 질문을 뒤져보니 자료구조의 선언도 뭔가 영향을 주는 것 같아서 배...

Gold 4

Gold 4

이번학기 듣는 알고리즘 연습 수업 과제로 나온 문제인데, 이틀째 골머리를 앓다가 푼 게 너무 기뻐서 기록하기로 했다. 교수님도 그렇게 말하셨고, 나도 푸는 아이디어 자체는 어렵지 않다고 생각한다.(다른 문제들에 비해) 근데 코드 작성하는 게 좀 빡친다. 문제 문자열을 뒤집을지 말지를 결정하는데, 뒤집게 되면 cost가 발생한다. 주어진 문자열들을 최...

문제 풀이 처음엔 단순하게 지나온 수중 가장 큰 수를 기록하고 해당 수보다 큰 수가 나오면 업데이트 하는 방식을 생각했는데, 어림도 없다. dynamic Programming인 걸 알기에 많이 나왔던 방식중 하나인 해당 인덱스에서 끝나는 경우 최댓값을 이용하기로 했다. 증가하는 배열(정답이 될 배열)을 따로 생성해서 유지한다. 이 배열의 마지막값보다...

실버1

골드 4