본문 바로가기

알고리즘

 (39)
[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..
[Rust] 백준 10807번 개수 세기 오랜만에 코딩 블로그에 글 써보기 요즘 러스트를 공부해보고 있는데 언어가 하도 낯설어서 백준으로 친해지기로 했다 solved.ac에 새싹이라는 탭이 새로 생겼길래 쉬운 문제들로 시작 use std::io; fn main() { let mut s = String::new(); let mut array: [i32; 201] = [0; 201]; io::stdin().read_line(&mut s).unwrap(); s.clear(); io::stdin().read_line(&mut s).unwrap(); let values:Vec = s .as_mut_str() .split_whitespace() .map(|s| s.parse().unwrap()) .collect(); for i in values { arr..
[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..
[SWEA] 균형점 처음에는 방정식을 푸는 문제인 줄 알았지만 식을 좀 써보니 계산용이 아니라 그냥 오차범위 내의 값을 찾는 것 같았다 parametric search를 이용해 풀어야겠다는 생각이 들었다 이 때 범위를 구해주어야 하는데 뭔가 각 점들의 사이이지 않을까 하는 생각이 들어서 input을 까봤다 SW 아카데미는 인풋, 아웃풋을 많이 알려줘서 좋다ㅎㅎ.. 안좋은 습관 고쳐야하는데... 아무튼!! input, output을 까봤더니 정말 각 점들의 사이가 답이었다 이유는 조금 더 생각해봐야 할 것 같다 각 점들의 사이를 범위로 주고 parametric search를 통해 오차범위 내의 답을 구해보았다 모든 자성체에서 동일한 G와 균형점의 무게가 될 m1은 무시했다 코드에 문제가 없어 보였지만 왜인지 모르게 segme..
[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 ..

티스토리툴바