알고리즘 (39) 썸네일형 리스트형 [C++] 최소비용 구하기2 백준 11779번 다익스트라로 풀어본 최소비용 구하기 문제 가장 기본적인 다익스트라는 거리(비용)만 구하는데 경로까지 구해야 하는 문제였다 경로를 우선순위큐에 vector로 다 넣어주었는데 간단하게 풀고싶어서 그렇게 풀긴 했지만 좋은 풀이는 아닌 것 같다 메모리를 줄이기 위해 다른 풀이가 있는지 찾아보았더니 특정점 a를 가기 위한 최적 경로가 b를 통해서라면 route[a] = b와 같이 저장해서 쓰는 방법이 있었다 이렇게하면 모든 경로를 벡터로 갖지 않아도 역추적이 가능하다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 .. [C++] 벽 부수고 이동하기 백준 2206번 solved ac 클래스 3이 끝나서 클래스 4 문제들을 풀기 시작했다 한참 많이 풀었던 bfs 유형이라 금방 풀 수 있었다 먼저 문제에서 요구하는 최단경로라는 키워드를 통해 bfs를 쓰면 되겠다고 판단했다 그 다음 벽을 단 한번만 부술 수 있으니 벽을 이미 부순 상태인지, 앞으로 부술 수 있는지만 나누어주었다 visit 배열 또한 벽을 부순 상태로 방문한 것인지, 부수지 않고 방문했는지 따로 저장했다 반복문 안에서의 조건은 아래와 같이 세가지로 나누었다 1. 벽도 없고 방문한 적도 없으며 앞으로 벽을 부술 수 있다 2. 벽이 없고 이미 벽을 부수었고 벽을 부순 상태로는 처음 방문한다 3. 벽이 있고 아직 벽을 부수지 않았다 이때 벽을 부순 칸을 다시 방문하는 것은 최단 경로가 아닌것이 .. [C++] 리모컨 백준 1107번 dfs로 문자열을 열심히 만들다가 뭔가 이상하다는 느낌이 들어서 방법을 고쳤다 처음 생각한 방법은 문제에 있는 예시처럼 5457이면 먼저 5를 쓸수 있는지 확인해서 5, 그다음 54, 545, 5455 이런식으로 문자열을 늘려갔다 하지만 999와 같은 경우는 1000 - 1이 유리한데 내 방식은 찾지 못할 것 같았다 예외 처리를 해주기에는 이런 상황이 너무 많을 수 있다는 생각이 들어 제한 조건을 다시 살펴보았다 채널은 총 500000개이고 한 문자열을 만들 수 있는지 없는지 확인하는데에는 최대 6밖에 들지 않았다 따라서 만들 수 있는 전체 문자열을 확인하는것이 예외처리도 없고 간편하겠다는 생각이 들었다 다만 입력으로 들어오는 채널은 500000이하이지만 500001 - 1 이런식으로 만.. [C] Z 백준 1074번 solved ac 클래스 문제를 전부 풀어보기를 시작했다 재귀를 이용하여 풀었던 Z 문제 풀면서 예전에 Icpc 기출인 philosopher's walk 문제의 쉬운버전이라고 느껴졌다 문제는 오랜만에 알고리즘을 다시 해서 그런가 long long 신경안써서 overflow 일어난 것과 부등호 부주의 했던 점ㅠㅠ 바빠도 일주일에 몇문제씩은 꼭 풀어야지 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include #include long long int dfs(long long int N, int r, int c){ if(N==2){ if(r==0 && c==0) return 0; else if(r==0 && c==1).. [프로그래머스] 2021 Dev-matching : 웹 백엔드 개발자 풀이 데브매칭 문제가 공개되었길래 풀어보았다 이 날 라인 코테였나...? 날짜가 겹쳐서 하나만 나가느라 데브매칭은 신청 못했는데 문제가 공개되다니!! 1. 로또의 최고 순위와 최저 순위 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include #include using namespace std; int get_rank(int i){ if(i>=6) return 1; else if(i==5) return 2; else if(i==4) return 3; else if(i==3) return 4; else if(i==2) return 5; else return 6; } vector solution.. [C++] 프로그래머스 순위 그래프 탭에 있는 순위라는 문제 보자마자 예전에 백준에서 풀었던 역사라는 문제가 생각났다 역사 문제에서는 사건의 전후관계를 플루이드 워셜 알고리즘을 파악했었는데 여기서는 같은 원리로 승패를 파악했다 역사 문제 풀때도 이 알고리즘을 전후관계 파악에 쓰는게 되게 생각해내기 어렵다고 느꼈는데 이 문제에서 또 만나서 반가웠다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include #include using namespace std; int player[105][105]; // player[i][j]==1 if player i beats player j int solution(int n, vector r.. [C++] 연산자 끼워넣기 백준 14888번 문제 읽으면서 쉽게 풀수있도록 많이 신경써준 문제라는 느낌이 들었다 먼저 연산자 우선순위 고려도 안해도 되었고 중간에 계산되는 식도 int범위를 초과하지 않는다고 친절히 알려주었다 아마 그래서 solved ac 실버로 측정된 것 같다ㅎㅎ 삼성 SW 기출 문제집에 있는 몇안되는 실버 문제 dfs 순열 코드를 응용해서 작성해봤다 숫자 배열은 그대로 두고 그 사이사이에 어떤 연산자가 들어갈지를 전부 찾아주었다 이때 연산자 순서는 직관적으로 확인할 수 있게 string으로 그냥 넣어주었다 전체 숫자 사이에 연산자들이 정해지면 결과를 차례로 계산하여 최소,최대값과 비교해주었다 마지막에 최소값과 최대값만 출력해주면 끝! 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1.. [C] 주사위 굴리기 백준 14499번 오랜만에 머리속에서 공간 돌려봤던 문제 중고등학교 시절에 수학문제 풀던 기분이었다ㅋㅋㅋ 주사위 굴리는 로직만 파악하면 까다롭지는 않았던 문제다 동서남북 각각 손으로 그려보며 각 방향별로 주사위 어느 위치에 있던 숫자가 어디로 가는지를 파악했다 나머지는 문제에서 하라는 그대로 숫자를 복사하고 출력만했다 디버깅 안하면서 풀었는데 바로 맞춰서 뿌듯 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 .. 이전 1 2 3 4 5 다음
