분류 전체보기
-
[프로그래머스] 자물쇠와 열쇠 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++CS기초/알고리즘 2022. 2. 7. 17:57
https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=803 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 간단한 구현 문제였다. 처음에는 최소 시간과 최대시간 + 4 만큼 for문을 돌면서 해당 시간에 차가 지나갈 수 있다면 정답배열에 시간을 담아주는 식으로 하려고 했는데, 시간이 최대 10^9 (십억) 이라서 제한시간 2초에 걸려 시간초과가 났었다. 그래서 흠 이렇게 해서는 안되겠군 이라는 생각과 함께, 차가 안들어오는 시간대는 패쓰해야겠다는 생각이 들어 해당 코드를 추가시켜 주었더니 통과했다. 전반적인 로직은 아래와 같다. 1. A, B, C, D 교차로에 들어오는 차들을 큐에 담아주었다. 나중에 정답배열을 입..
-
[프로그래머스] - 퍼즐 조각 채우기 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도 늘려주도록 하였지만, 이렇게 하면 못 지나가는 곳의 물고기까지 먹을 수 있고/거리도 틀리다 (자기보다 큰 물고기는 못 지나가기 때문) 아 멀리를..