알고리즘
-
[프로그래머스] 자물쇠와 열쇠 C++알고리즘/프로그래머스 2022. 2. 10. 17:28
https://programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 카카오 2020 공채 1차 기출문제이다. M, N 이 최대 20이어서, 완전 탐색으로 풀어보았다. 완전 탐색을 할 시에는, 4 (열쇠 회전) * (2 * (M - 1) + N)^2 (열쇠 이동) 번 반복하게 된다. 열쇠를 90도로 회전시키고, 이동시키며 자물쇠에 들어가는지 검사한다. 2차원 배열 board를 사용해 자물쇠와, 열쇠가 모두 들어갈 수 있는 사이즈를 만들어준다. 그리고 해당 board 에 열쇠와 자..
-
[프로그래머스] - 퍼즐 조각 채우기 c++알고리즘/프로그래머스 2022. 2. 4. 10:34
https://programmers.co.kr/learn/courses/30/lessons/84021 코딩테스트 연습 - 퍼즐 조각 채우기 [[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]] [[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]] 14 [[0,0,0],[1,1,0],[1,1,1]] [[1,1,1],[1,0,0],[0,0,0]] 0 programmers.co.kr 해당 문제를 푸는 데 많은 시간이 들었다. 푸는 방식은 감이 왔지만, 알고리즘을 조금 오랜만에 풀어서 그런가..? 막상 구현을 하는..
-
[백준 16235번 - 나무 재테크] C++ 풀이알고리즘/삼성SW역량테스트기출 2021. 10. 19. 02:22
16235번. 자료구조는 2차원 배열 안에 deque 를 넣는 것으로 n * n 땅을 표현했다. 구현은 빠르게 했지만 계속 43% 정도에서 시간초과가 떠서 잡느라 매우 오랜 시간을 소요했다ㅜ....... 시간을 줄이는데 도움이 되었던 것은 1. 구조체 없애기 처음에는 tree 구조체를 써서 했지만 2차원 배열에 저장하므로서 위치를 따로 갖고있을 필요가 없어져서 그냥 나무 나이만 deque 에 저장하는 것으로 했더니 47%에서 시간초과가 났다. 2. deque 자료구조로 sort 함수를 없애기 가을에 새로 생기는 나무들을 deque 의 front 에 push 해줌으로서 정렬할 필요가 없어졌다. 새로 생기는 나무는 나이가 1로 기존의 나무보다는 작을 것이기 때문이다. 그래서 봄에 나이 적은 순서대로 나이 추..
-
[백준 20056번 - 마법사 상어와 파이어볼] C++ 풀이알고리즘/삼성SW역량테스트기출 2021. 10. 18. 12:44
20056번. '1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다' 이 말인 즉슨, 1행에서 범위 초과하여 0행으로 갔을때, N행에 놓아주고, 1열에서 범위를 초과하여 0열로 갔을 때 N열에 놓아라는 의미이다. 반대로, N행에 있다가 범위를 초과하여 N + 1행으로 가면, 다시 1행에 놓아준다. 로직은 문제에 쓰인 그대로 풀이해주면 된다. 나는 2차원 벡터에 파이어볼을 담고있는 큐를 담았다. 그리고 이동한 파이어볼을 new_map 에 담아주고, 검사하면서 2개 이상 파이어볼이 있으면 합친 다음 4개로 만들어 주었다. 이 때, 만약 질량이 0이라면 파이어볼을 없애준다. k 번 이동 후에 남아있는 파이어볼 질량 총 합을 구해주면 된다. #include #include #include #d..
-
[백준 21611번 - 마법사 상어와 블리자드] C++ 풀이알고리즘/삼성SW역량테스트기출 2021. 10. 15. 00:35
https://www.acmicpc.net/problem/21611 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, ( www.acmicpc.net 이 문제 덕분에 구현력이 한층 상승한 기분.. 전체적인 나의 전략은 아래의 그림과 같다. 2차원의 map을 입력받아 저장하고, 구슬이 파괴되는 부분의 map 값을 -1로 만들어 주어 파괴되었음을 표시했다. 그 다음에는 달팽이 모양을 따라서 1차원의 배열로 펼친다. 그래야 같은 구슬이 4개 이상 연속하는지 검사하여 구슬을 폭파시킬 수 있다. 이때 주의할 점은, 4개 이상 모여있는 ..
-
[백준 17142번 - 연구소3] C++ 풀이알고리즘/삼성SW역량테스트기출 2021. 10. 13. 00:16
17142번. 처음에는 조금 어렵게 접근했는데, 천천히 생각해보니 간단히 해결할 수 있었던 문제이다. 우선 총 바이러스 개수에서 M개를 뽑도록 하고, 뽑은 바이러스를 큐에 넣고 bfs를 돌리면 된다. "활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 비활성 바이러스가 활성으로 변한다" 라는 문구가 조금 헷갈렸다. 근데 해당 바이러스가 있는 곳도 지나갈 수 있다는 의미 정도로 해석하면 될 듯 하고, 별다른 처리를 안해주어도 되었다. 어짜피 "시간"기준이기때문에 origin 에서 시간이 +1 되는건 마찬가지기 때문. 처음 0의 갯수와 방문한 0의 갯수가 같다면, 모두 바이러스가 퍼졌다는 의미이다. 완성된 코드. #include #include #include #include using namespace ..
-
[백준 16236번 - 아기상어] C++ 풀이알고리즘/삼성SW역량테스트기출 2021. 10. 7. 02:45
16236번. 나에게 생각보다 매우 많이 걸렸던 문제이다. 처음부터 다시짜고 다시짜고..를 한 5번 정도 했던 것 같았다. 우선, 처음에는 bfs 함수를 한번만 호출하여 한번에, 아기 상어가 잡아먹는 물고기들을 순서대로 queue에 담음과 동시에 distance 를 계산하여 answer를 구하려고 했다. 이건 매우 잘못된 접근이었다... 왜냐면 queue에 담을 아기상어를 찾는 것을 거리가 1, 2, 3, ... 이렇게 늘려가면서 위에서 아래로/왼쪽에서 오른쪽으로 훑어가면서 스캔하는 방식으로 for문을 돌리고, 잡아먹은 물고기 갯수를 ++하여 fish size도 늘려주도록 하였지만, 이렇게 하면 못 지나가는 곳의 물고기까지 먹을 수 있고/거리도 틀리다 (자기보다 큰 물고기는 못 지나가기 때문) 아 멀리를..
-
[백준 16234번 - 인구 이동] C++ 풀이알고리즘/삼성SW역량테스트기출 2021. 10. 2. 20:29
백준 16234번. 사용한 알고리즘 - bfs 구현은 빠르게 했는데 80%에서 계속 시간초과가 나서 좀 애먹었다ㅜ bfs 호출 수를 줄이고, map 값 변경을 bfs 내부에 해줘서 시간초과 문제를 해결했다.. flag를 사용해서 주변에 인구차가 l 이상 r이하 나는 나라가 있으면 해당 (i,j) 에 대하여 bfs 한번 호출하고 바로 for 문을 빠져나오게 했다. 그리고 처음에는 bfs 다 끝나고 바깥에서 sum, cnt 값을 가지고 map 을 수정해줬는데 해당 작업을 bfs 안에서 하니 시간초과문제가 해결되었다. #include #include #include #include using namespace std; vector map; vector visited; int n, l, r; int dx[] =..