나 요리학원 출신임

하반기 코테를 위해 백준문제를 오랜만에 풀어봤따..!! 골고루 틀리면서 정신을 차리고 있다 이 문제는 dfs로 가장 1~n까지 간다고 생각하면 된다 대신 check[현재][이전에 고른 수]를 체크해 가며 가야한다 ans배열을 만들고 내가 수를 고르고 다음수로 넘어갈 때 현재의 수를 넣어주면 탐색이 끝나고 그대로 출력하면 된다 소스코드 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 #include #include #include using namespace std; int n; int arr[1111][11]; bool check[11..

이 문제는 트라이를 이용하면 풀 수 있다 여태까지 항상 동적 트라이만 짜봤는데 오늘 정적 트라이을 배워서 사용해봤다 먼저 문자열배열 s와 trie배열 그리고 문자열의 끝남을 알리는 fin을 잡자 trie가 [10000*10][10] 크기인 이유는 총 10000*10개의 정점이 나올 수 있고 각 정점은 0~9까지 10개의 숫자를 가질 수 있기 때문이다! 총 2가지의함수 insert, find를 구현했다! insert에서는 문자열을 trie자료구조에 넣는다 이 때 문자열의 문자 하나씩을 보며 끝난다면 fin[현재정점]을 true로 만들어준다 그럼 우리는 현재정점은 끝나는 지점이라는 것을 알 수 있다 trie배열에는 trie[현재정점][현재문자] = cnt로 인덱스를 매긴다 그럼 문자열을 하나하나 찾을때 정점..

수 정렬하기2 문제는 사실 STL 정렬로 쉽게 풀 수 있다 이번에는 삼성 B형 준비할 겸 직접 힙소트로 구현해서 풀어보았다 혹시 틀렸으면 댓글좀..!!! 부탁합니다 총 3개의 함수 swap,insert,sort 함수를 구현했다 swap은 말그대로 a,b의 수를 바꿔주는 함수다 insert는 수를 heap에 넣는 함수로 넣고나서 내가 루트가 아니라면 항상 부모와 크기를 비교해본다. 그래서 만약 내가 더 크다면 체인지! swap을 못할때까지 죽쭉 올라가보자!! sort는 pop하는걸 n번 연속으로 한다고 생각하면 쉽다 추가적인 배열을 만들필요가 없어서 메모리에 좋다..! 먼저 최대힙이므로 루트에는 가장 큰 수가 있다 이 수를 가장 마지막 last수와 바꾸준다 그럼 가장 뒤에는 가장 큰 수가 위치한다 이제 루..

그리디 알고리즘으로 그냥 그대로 앞부터 덮어가면 된다 벡터로 구현하다가 구현 오류가 많이나서 틀렸다 변수를 더 잡더라도 정확하게 구현을 하자! 마지막으로 덮은 곳을 last에 두고 last와 다음 웅덩이의 시작지점을 비교했다 만약 last가 더 크다면 웅덩이의 시작지점을 last+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 #include #include #include using namespace std; int n,l,ans; vector vt; bool cmp (const pair &a, const pair&b){ if(a.first==b.first) return a.second>b.sec..

그리디문제인제 복잡하게 생각해서 많이 틀렸다 나의 틀린 접근법은 각 날 마다 최대값을 두고 나머지 날 들은 pq 에 넣었다 그리고 각날의 최대값과 나머지날들을 비교해서 큰값을 넣었다 많은 것들을 고려했었는데 그럴 필요가 없었다 데드라인 순으로 정렬하고 내가 보고있는 데드라인까지 중 큰 값들만 남기고 버리면 된다 pq를 이용하면 쉽게 풀 수 있다 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include #include #include using namespace std; pair arr[200200]; int n; int main(){ //freopen("input.txt","r",stdin); scanf(" %d",&n); for(in..

그리디 문제이다. 우선순위 큐를 이용해 쉽게 풀 수 있다 최소값 2개를 계속 더해가면 된다 이 때 pq는 최대값을 저장하므로 -를 붙여서 저장해 최소값을 계속 찾아주자 소스코드 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 #include #include using namespace std; #define ll long long int n,m; priority_queue pq; int main(){ //freopen("input.txt","r",stdin); scanf(" %d %d",&n,&m); for(int i=0;i

다익스트라를 이용하며 최단거리로 지나가는 경로를 저장해 매번 확인했다 https://sejinik.tistory.com/131와 비슷한 방법이다! 사실 이렇게 풀면 되긴하지만 시간이 조금 오래걸린다 다른 사람들 풀이를 보니 여러가지 최적화가 있는 것 같다 내가 푼 방법은 Passed라는 배열에 지나가는 경로를 저장하고 매번 다익스트라를 돌고 확인하는 하라는대로 하는 방법이다 소스코드 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..

정말 직관적으로 문제에서 하라는대로 풀었다 먼저 최단거리를 찾아보다 그리고 이 때 내가 최단거리를 가는 모든 경우를 pre라는 벡터에 저장한다 그리고 최단거리를 구한 후 거꾸로 목적지에서부터 타고오며 check set에 넣는다 이건 간선을 제거하는 과정이라고 보면 편하다 그리고 다시 그래프를 그려서 다익스트라를 돌리면 최단거리를 제외한 2번째 최단거리가 나오게 된다 소스코드 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 6..

다익스트라를 이용하는 문제다 왼쪽 오른쪽으로 최대 L,R만큼 갈 수 있다 그럼 왼쪽으로 갈 때 가중치 100, 오른쪽으로 갈 때 10억을 주자 그리고 다익스트라를 돌려 모든정점에 최단거리를 구하자 그 후 각 정점마다 10억으로 나누고 100으로 나눠 값을 보자 그게 곧 왼쪽, 오른쪽으로 간 횟수다 결국 그 값들과 L,R을 비교하면 갈 수 있는지 없는지 확인 가능하다 소스코드 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 #include #include #includ..

DFS+비트마스크를 이용해 풀 수 있다 이미 지나간 알파벳을 지나갈 수 없으므로 비트를 이용해 확인하자 DFS를 돌리며 비트를 이용해 확인하고 지나갈 때 추가하면 쉽게 답을찾을 수 있다! 소스코드 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 #include #include using namespace std; int n,m,ans; char map[22][22]; bool check[22][22]; int dx[4]={0,0,-1,1}; int dy[4]={1,-1,0,0}; void dfs(int x,int y,int alpha,int dist){ int num..