본문 바로가기

백준

 (43)
[Rust] 백준 2630번 색종이 만들기 use std::io; fn recursive (vec: &Vec, white: &mut i32, blue: &mut i32, r :i32, c :i32, length: i32) { let start = vec.get(r as usize).unwrap().get(c as usize).unwrap(); for i in r..r+length { for j in c..c+length { if vec.get(i as usize).unwrap().get(j as usize).unwrap() != start { recursive (vec,white,blue,r,c,length/2); recursive (vec,white,blue,r,c + length/2,length/2); recursive (vec,white,b..
[C++] 별자리 만들기 solved ac 클래스 5를 따기 위해 클래스 풀던 중 풀어보게 된 문제 4386 별자리 만들기 이다 스패닝 트리 활용 문제로 좋은 것 같다 사실 처음에는 어떻게 풀어야 할 지 감이 잘 안와서 알고리즘 분류를 먼저 보았다 알고리즘 분류에 MST라고 나와있었고 그제서야 별의 개수가 매우 작아 모든 경우를 edge로 하여 MST를 만들면 되겠구나 하는 생각이 들었다 역시 input 크기 보기는 매우 중요하다 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 #include #include #include using n..
[C++] 백준 23288 삼성기출 주사위 굴리기 2 2021 하반기 삼성 기출이 올라왔다해서 후다닥 풀어봤다 이 문제는 총 55분 가량 걸렸는데 문제를 잘못 읽어서 한 20분 넘게 날려서 아쉬웠다 삼성 기출을 쉽게 푸는 법을 설명하기 위해 어떤식으로 접근하였는지 서술해보고자 한다 먼저 주사위 모양을 살펴보았다 나는 주석처리된 부분처럼 배열의 인덱스를 정하였다 그 후 주사위가 구를 때 어떤 위치에 어떤 인덱스가 가게 되는지를 살펴보았다 다행히 문제에서 힌트를 주었다 먼저 문제에서 준 주사위 초기값 주사위 배열을 초기값인 2,4,1,3,5,6으로 채워주었다 그다음 초기값이 동쪽으로 변할 때 어떻게 변화하는지 살펴보았다 살펴보면 1,5번 인덱스는 그대로 2번은 3번으로, 3번은 4번으로, 4번은 6번으로, 6번은 2번으로 바뀐 것을 알 수 있다 이런 규칙에 따..
[C++] 가장 가까운 두 점 백준 2261번이다 직무 교육 들으면서 추가로 풀어보았던 문제 solved ac 플레 3이라는 꽤나 높은 난이도의 문제였다 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 #include #include #include #include #include #define ll long long using namespace std; typedef struct pair pii; pii points..
[C++] 개미굴 백준 14725번 삼성 프로를 따기 위해 다시 알고리즘을 열심히 해야겠다 아직 수업을 안들어서 뭘 할까 하다가 백준 알고리즘 분류에서 내가 좋아하는 트라이를 골라서 풀어봤다 이 문제는 개미들이 타고 내려간 정보를 보고 개미굴의 전체 모습을 파악하는 문제 전형적인 트라이라기 보다는 트라이를 알면 쉽게 풀 수 있는 문제였던 것 같다 map과 vector를 사용하면서 프로 시험에 이제 stl 허용인것이 행복했다 노드별로 string을 키로 갖고 노드 포인터를 value로 갖는 map을 만들어주었다 로봇개미가 찾은 경로는 insert 함수를 재귀적으로 불러 차례차례 넣어주었다 이때 이미 한 번 이상 찾은 경로는 map에서 찾아서, 처음 가는 경로는 새로운 노드를 만들어 재귀함수를 불렀다 출력 또한 재귀적으로 함..
[C++] 특정한 최단 경로 백준 1504번 다익스트라를 응용한 문제였다 최단 경로는 경로인데 특정한 두 지점을 꼭 지나간 최단 경로 찾기 따라서 최단 경로를 저장하는 배열을 한 지점만 들른 경우, 두 지점 모두 들른 경우 나누어서 만들어주었다 예전에 비슷한 문제를 푼 적 있어서 dist 배열을 다차원 배열로 status 별로 나누는 것은 금방했지만 조건 체크에서 실수를 해서 몇번 틀렸다 꼭 들러야하는 점이 1인 경우 시작점이 1이라 자동적으로 들르게되지만 처음의 코드에서는 해당 케이스를 잡지 못했다 start status를 만들어 시작점이 1인 경우를 따로 체크해주었더니 정답처리되었다 최단 경로를 상황별로 나누어 저장하는 것과 시작점이 특정 지점인 경우만 체크해주면 될 듯한 문제! 1 2 3 4 5 6 7 8 9 10 11 12 ..
[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. 벽이 있고 아직 벽을 부수지 않았다 이때 벽을 부순 칸을 다시 방문하는 것은 최단 경로가 아닌것이 ..

티스토리툴바