짱아의 개발 기록장

오랜만에 그리디 문제를 풀어봤다. 역시 그리디는 아이디어를 도출해내는 것이 참 어렵다...ㅎ 하지만, 그렇게 어려운 그리디 문제에 속하지는 않아서 생각보다 간단하게 해결할 수 있었다. 우선순위큐를 사용했고 맨 마지막에 있는 마감일 기준으로 우선순위큐에 값을 넣어서 각 날마다 가장 큰 값을 더해주었다. 아래는 놓치기 쉬운 반례들이다. 6 5 3 5 3 5 3 4 2 4 1 4 2 정답 : 13 4 9 9 9 9 9 9 1 10 정답 : 37 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354// 과제#include #include #include #include using name..

String을 백트래킹으로 구현하는 문제이다. 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 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 // 0만들기 #include #include #include using namespace std; int testcase, n; char oper[3] = {'+', ' ', ..

백준 9328번. 열쇠 문제와 매우 유사하다. 다만, 차이점이라면 열쇠문제는 최소 거리를 구하는 것이 아닌 찾을 수 있는 문서의 개수이고 이 문제는 거리를 구해야했다. 따라서, 단순히 문을 저장해서 해결할 수 있는 것이 아니기 때문에 visited배열에 (x, y, 키의 저장상태) 를 저장해주었다. 그래서 같은 위치를 방문하더라도 키의 저장상태가 다르다면 그 위치에 접근할 수 있도록 했다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192// ..

BFS 자체는 어렵지 않았지만, 퍼즐의 상태를 어떻게 저장할지가 굉장히 까다롭게 느껴졌다. 2차원 배열에 저장하려고 했지만,,, 어떻게 보면 BruteForce로 모든 경우를 다 돌아야하기 때문에 2차원으로 한다면,,,, 아주 복잡해지고 메모리도 많이 차지할 것으로 생각되었다. 따라서, 다른 고수분들을 어떻게 코드를 짜셨을까 보다가 대부분 String형태로 저장해놓고 0의 인덱스 값을 찾아서 그것을 2차원 배열의 (x, y) 값으로 바꾸고 인접한 곳과 자리를 바꾸는 형식으로.,,,, 구현하셨더라,,, 아주 최적화된 좋은 방법이라 생각되어 그렇게 구현해보았다. 즉, 2차원 배열의 형태로 되어있어야 bfs를 하기 쉽기 때문에 퍼즐의 상태를 한눈에 보기 쉽게 해서 0의 위치를 찾을 때에는 => String형태..

설명 추가 예정 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124// 열쇠#include #include #include #include #include #include using namespace std; int testcase, h, w;string s, tmp;char map[105..

설명 추가 예정 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100#include #include #include #include #include using namespace std; int n;int map[101][101] = { 0, };int dx[4] = { 0, 0, -1, 1 };int dy[4] = { -1, 1, 0, 0 };int check[101][101] = { 0, }; // 영역 표시하기 i..

설명 추가 예정 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153#include #include #include #include #i..

딱히 어려울 것 없는 구현 문제였다. 다만, 궁수들의 위치를 정하고 다시 배열들을 초기화해주는 작업이 필요하다는 것만 주의하면 될 것 같다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136// 캐슬 디펜스#include #..