알고리즘

[C++] 백준 20056번 마법사 상어와 파이어볼

20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 에 수록된 문제. 구현 / 시뮬레이션 문제로, 문제에서 요구하는 대로 풀면 된다. 오랜만에 풀어보는 알고리즘 문제라서 특수한 알고리즘이 필요없는 구현 문제일 줄 알았는데 시간 복잡도를 생각 안하고 풀어서 시간 초과를 냈었다. 문제풀이 다음과 같은 순서대로 구현했다 모든 파이어볼을 이동시킨다. 2개 이상의 파이어볼이 있는 곳에서 합친 후 4개로 나눠준다. 1번 로직과 2번 로직을 반복만 시켜주..

[C++] 백준 2589번 보물섬

그래프 탐색 문제. 오랜만에 풀어보는 알고리즘 문제라 그런지 머리가 잘 안 돌아갔지만 그래프 탐색이란 것을 알고 쉽게 풀 수 있었다. 문제풀이 땅 - 땅으로 이동하는 거리중 가장 긴 거리를 찾으면 된다. 돌아가면 안되고 최단거리 기준이므로 DFS는 안되고 BFS로 탐색해야한다. 이 기준대로만 구현하면 쉽게 풀 수 있다. /* * 백준 2589번 보물섬 * https://www.acmicpc.net/problem/2589 * 그래프 탐색 이론 - 너비 우선 탐색, 브루트 포스 */ #include #include #include #include using namespace std; int height, width; char board[51][51]; bool visit[51][51]; vector visi..

[C++] 백준 20057번 마법사 상어와 토네이도

20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 에 수록된 문제. 구현 / 시뮬레이션 문제로, 문제에서 요구하는 대로 풀면 된다. 문제풀이 나는 다음과 같은 로직, 순서를 구현해서 풀었다. 0 = 좌, 1 = 하, 2 = 우, 3 = 상 이라는 방향을 잡았다. 이동하는 횟수는 (좌, 하) 1번씩, (우, 상) 2번씩, (좌, 하) 3번씩 ...의 규칙으로 반복된다. 각 방향이 이동할 때, (r, c)에 얼마를 계산해야 하는지, 그리고 계산한 좌표..

[C++] 프로그래머스 2020 KAKAO BLIND RECRUITMENT Level 1 키패드 누르기

코딩테스트 연습 - 키패드 누르기 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL" programmers.co.kr 구현 문제. Level 1 문제는 보고 바로 이해하고 풀 수 있는 게 중요한 것 같다. 실제 코딩테스트에서는 시간 압박이 더 심하므로 빠르게 이해하고 빠르게 푸는 게 중요한 것 같다. 물론 무조건 빠르게 푸는 것 보단 한 번에 확실하게 푸는 게 중요하다. 문제풀이 문제에 나온 그대로 구현해주기만 하면 된다. 나같은 경우는 키 패드들을 좌표로 만들어놓고 ..

[C++] 프로그래머스 2021 KAKAO BLIND RECRUITMENT Level 1 신규 아이디 추천

코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 programmers.co.kr 문자열 / 구현 문제. Level 1은 크게 어려운 문제는 아니라고 생각했다. 막상 코딩 테스트에서 만나면 시간을 많이 잡아먹을 것 같다. 문제풀이 문제에 나온 그대로, 다음과 같은 순서로 구현해주면 된다. 아이디의 길이 : 3 ~ 15 소문자, 숫자, -, _, . 사용 가능. 마침표(.)는 처음과 끝에 사용 불가 마침표는 연속 사용 불가 단계를 통해서 규칙에 맞는 새로운 아이디 추천 1. 모든 대문자를 소문자로 치환. 2. 소문자, 숫자, -, _, ..

[C++] 백준 2096번 내려가기

다이나믹 프로그래밍 문제. 메모리 제한이 상당히 제약적인데, 이 부분을 잘 이해했으면 쉽게 풀 수 있는 문제다. 처음에 배열을 10만 x 3개씩 만들어서 풀어보려 했는데, 메모리 초과가 났다. 결국 게시판을 참고해서 풀 수 있었다. 문제풀이 문제에 표현된 그대로, N번째 줄마다 1, 2, 3번째에 도달했을 때 최대, 최소값을 기록해두면 된다. 첫번째 칸에 도달한 경우에는 이전에 1, 2번째 칸인 경우이다. 두번째 칸에 도달한 경우에는 이전에 1, 2, 3번째 칸인 경우이다. 세번째 칸에 도달한 경우에는 이전에 2, 3번째 칸인 경우이다. 이 문제의 핵심은 이전에 지나온 칸, 앞으로 지나올 칸의 수는 저장할 필요가 없다는 것이다. 따라서 입력을 받을 때마다 i번째 칸에서의 최대, 최소값을 기록해두면 된다...

[C++] 백준 2638번 치즈

2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net 구현 / 시뮬레이션 / 그래프 탐색 문제. 문제에서 구현하라는 대로 구현해서 풀면된다. 제출하고 시간이 44ms가 나왔는데, 다른 사람들은 보통 12 ~ 20ms가 나온 것 같았다. 유의미한 차이는 아니라서 일단은 그냥 넘어갔다. 문제풀이 문제의 조건들은 다음과 같다. 격자의 가장자리들에는 치즈가 존재하지 않는다. 한 시간마다 외부공기와 동, 서, 남, 북 중 두 방향 이상 외부공기와 접한 치즈는 녹는다. 치즈로 둘러쌓인 공간은 외부 공간으로 치지 ..

[C++] 백준 23288번 주사위 굴리기 2

23288번: 주사위 굴리기 2 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 가장 왼 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 수록 문제. 구현 / 시뮬레이션 문제이다. 이해하기 어려웠고, 시간을 잡아먹었던(자꾸 8번째 테스트 케이스가 이상하게 나와서 고쳤다.) 것들이 있었다. 조건들을 정리해가면서 문제 풀이를 정리해 보겠다. 문제풀이 문제의 조건들을 정리해보면, 다음과 같은 순서로 구현하면 된다. 높이, 너비, 주사위 이동횟수를 입력받는다. 격자의 각 칸의 숫자를 입력받는다. 여기까지가 기본 입력이다. 그 후에 이동횟수만큼 아래를 반복..

[C++] 백준 2573번 빙산

2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 구현 / 그래프 탐색 문제. 삼성 기출 문제와 유사한 문제였다. 문제에서 제시하는대로 구현하면 맞출 수 있는 문제다. 문제풀이 다음과 같은 순서로 만들면 된다. 0이 아닌 칸들에서 인접한 칸들 중 0인 칸들의 개수를 큐에 저장해둔다. 큐에 있는 정보를 토대로 각 칸마다 0인 칸들의 개수만큼 높이에서 빼준다. DFS / BFS를 통해 연결 요소의 개수를 구해서 2 이상인 경우에는 몇 년 걸렸는지 출력한다. 2 미만일 경우에는 1로 돌아간다. 이 때 DFS /..

[C++] 백준 13549번 숨바꼭질3

다익스트라 문제. 이 문제는 처음에 BFS로 접근했는데 자꾸 틀렸습니다. 가 나왔다. 게시판을 참고하고 나서 다익스트라로 풀었다. 그런데 사람들을 보니 우선순위 큐 + BFS이면 풀 수 있다고 했다. 나도 우선순위 큐 + BFS로 시도했었는데 왜 못풀었을까..흠.. 문제풀이 이 문제는 다익스트라로 풀어야 한다. 왜냐하면 이전의 숨바꼭질 문제들은 +1, -1, *2의 시간초과가 모두 같았지만, 이번 문제의 경우 *2가 걸리는 시간이 0초이다. 따라서 *2들 먼저 모두 탐색한 후에 또 거기서 +1, -1 *2들 먼저.. 이런식으로 탐사해야한다. /* * 백준 13549번 숨바꼭질3 * https://www.acmicpc.net/problem/13549 * 그래프 탐색 이론 - 다익스트라 * 다익스트라에서는 ..