전체 글
-
Programmers 순위 검색알고리즘 풀이/Search 2021. 8. 27. 23:19
링크 : https://programmers.co.kr/learn/courses/30/lessons/72412 if (checked[j]) { str.append("-") } else { str.append(strs[j]) } } val key = str.toString() val score = strs[4].toInt() if(map.containsKey(key)) { map[key]!!.add(score) }else { map[key] = mutableListOf(score) } } for(i in index until 4) { checked[i] = true recursive(map, strs, checked, i+1,depth+1, max_depth) checked[i] = false } } fu..
-
BOJ 11657 [타임머신]알고리즘 풀이/수학 2021. 3. 19. 22:50
BOJ 11657 : www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 처음에 queue에 넣어서 bfs처럼 풀어보려고 시도했으나, cycle을 알아낼 마땅한 방법이 떠오르지 않아 재귀 형식으로 바꿨다. key point는 재귀함수 내의 if문이다. 현재 재귀호출하면서 방문한 적 없는가? 현재 재귀 내에서 방문한 적이 없더라도, 이전에 방문했을 때 저장된 값(arr)보다 적은 시간이 걸리는가? 이 두..
-
BOJ 1005 [ACM Craft]알고리즘 풀이/DP(동적계획법) 2021. 3. 10. 22:19
BOJ ACM Craft : www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 우선 주어진대로 그림을 그려보니, 그래프가 나왔다. 어떻게 이어볼까,, 고민하다가 역으로 이어보니 답이 나왔다. 페이지에 있는 테스트케이스를 토대로 그려본다. 입력 : 5 10 100000 99999 99997 99994 99990 4 5 3 5 3 4 2 5 2 4 2 3 1 5 1 4 1 3 1 2 4 대략 이런그림이 나온다. 내가 필요한 것은 4에 도달하기까지의 시간이다...
-
BOJ 9184 [신나는 함수 실행]알고리즘 풀이/BFS(너비 우선 탐색) 2021. 3. 7. 23:03
BOJ 신나는 함수 실행 : www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 신나지 않은 함수 실행이다. 메모이제이션을 사용해 풀었다. 배열 인덱스에 50을 더한 이유는 마이너스도 있으니깐,, 밑에 코드는 +50때문에 눈이 좀 피곤할 수도 있다. 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..
-
BOJ 17836 [공주님을 구해라!]알고리즘 풀이/BFS(너비 우선 탐색) 2021. 3. 7. 23:00
BOJ 공주님을 구해라! : www.acmicpc.net/problem/17836 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 간단한 BFS 문제이다. 키포인트는 방문배열(visit)를 3차원으로 설정했다. visited[3][3][0] => 그람 없이 (3, 3)을 방문한 경우 visited[3][3][1] => 그람을 가지고 (3, 3)을 방문한 경우 그람을 획득하면, 해당 node가 그람을 가지도록 체크해준다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ..
-
BOJ 17141 [연구소 2]알고리즘 풀이/BFS(너비 우선 탐색) 2021. 3. 4. 23:08
BOJ 연구소 2 : www.acmicpc.net/problem/17141 17141번: 연구소 2 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 승원이는 연구소의 특정 위치에 바이러스 M개를 놓을 것이고, 승원이의 신호와 동시에 바이 www.acmicpc.net 옛날에 연구소는 풀어봤는데, 2탄도 있는줄 몰랐다. 나의 풀이 방법은 다음과 같다. 바이러스를 놓을 수 있는 구역을 먼저 체크해 vector에 담아놓는다. 브루트 포스를 이용해 바이러스를 놓는 모든 경우의 수를 체크한다. BFS로 바이러스를 확산시켜본다. 제출하니 420ms나 걸린다... 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24..
-
BOJ 6588 [골드바흐의 추측]알고리즘 풀이/수학 2021. 3. 2. 22:50
BOJ 골드바흐의 추측 : www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 오랜만에 푸는 앨거리즘,,, 골드바흐 추측에 관련한 소설을 중학교때 읽었는데, 하나도 기억이 안난다. 어쨌든 진짜 뻘짓을 많이했던 문제다. 처음에 계속 시간초과가 떠서 대체 뭐시 문제인가...하고 봤더니 cin.tie(NULL) ios::sync_with_stdio(0)를 추가해야 한다고 한다... 그래서 추가하고 다시 제출하니 또 시간초과가 뜬다. 더 알아보니..
-
싱글톤(Singleton) 패턴잡기술 2021. 2. 20. 02:21
내가 회사에서 개발할 때 가장 많이 쓰는 패턴 중 하나다. 자꾸 이런 잡기술만 늘어가는 것 같다... 하여튼 너무나도 유용하게 잘 쓰고 있는 패턴인데, 인스턴스를 하나만 가져서 공유할 데이터가 필요할 때 자주쓴다. 여러가지 방법이 있다는데, 내가 쓰는 코드만 적으려 한다. 간단한 예로, 카카오톡의 구조를 내마음대로 짜봤다. MyAccount : 내 계정의 정보를 가지고있는 객체. 내 이름, 이메일과 같은 정보들을 가지고 있다. Profile : 카톡 친구 화면에서 맨 위에 보이는 내 프로필 Chatting : 채팅 화면 표시해주는 객체 Setting : 환경설정 관련 객체 이렇게 있다고 가정해본다. Profile, Chatting, Setting에서 모두 내 계정의 정보를 필요로 한다. Profile엔 ..