구현

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

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

[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++] 백준 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++] 백준 21608번 상어 초등학교

21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 에 수록된 문제. 실버1 문제이고 나온지 얼마 안 돼보이는 문제였다. 문제가 과하게 친절하게 해야할 것들을 다 알려준다. 문제에 나온대로만 구현해주면 풀 수 있다. (물론 나는 학생 수를 잘못 고려해서 틀렸다. 아마 대부분 사람들이 이것때문에 런타임 에러나서 틀린 것 같았다. 학생 수가 N * N명인데, N으로만 생각해서 틀렸다. 좀 더 생각했으면 좋았을 것 같은데, 게시판에 누가 이렇게 올려놓은 걸 보고 바로 알 수 ..

[C++] 백준 20055번 컨베이어 벨트 위의 로봇

20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 에 수록되어 있는 문제중 하나. 실버1 문제이고, 정답률이 높길래 풀어봤는데, 문제가 상당히 표현이 애매모호하게 되어있다. 게시판을 참조해서 사람들이 해석해준 방법을 보고난 후에 풀 수 있었다. 문제풀이 문제의 조건을 정리하면 다음과 같다. 컨베이어 벨트는 2층구조이고, 1층은 1 ~ N, 2층은 N + 1 ~ 2N의 범위이다. (2층은 2N ~ N + 1이라고 생각해야한다.) 각 컨베이어 벨트 칸 하나마다 ..

[C++] 백준 17779번 게리맨더링 2

17779번: 게리맨더링 2 재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름 www.acmicpc.net 삼성 SW 역량 테스트 기출 문제 에 수록된 문제. 구현 / 브루트포스(완전탐색) / 시뮬레이션 문제. 처음에 조건 한줄을 잘못설정해줘서 계속 틀렸다. 반복문에서 break를 걸어주어야 하는데, continue를 써준게 틀린원인이였다. 정답률도 높은 편이고 생각한대로 구현을 잘 해주면 쉽게 맞출 수 있는 문제였다. 문제풀이 문제의 조건을 요약하면 다음과 같다. 선거구를 5개로 나눈다. 선거구를 나누는 것은 기준점 x, y와 길이 d1, d2를 정해서 나눠준다. d1은 ..

[C++] 백준 17140번 이차원 배열과 연산

구현 / 정렬 / 시뮬레이션 문제. 삼성 S/W 기출문제 중 한 문제이다. 문제에 나온 그대로 구현하면 시간복잡도 고려할 필요없이 맞출 수 있다. 조건들이 생각보다 복잡하지만 골드4 구현 문제치고는 쉬운 편에 속한다고 생각한다. 정답 비율도 높은 걸 보면 쉽게 풀 수 있는 것 같다. 문제풀이 구현 문제는 문제에 나온 내용을 잘 정리하는 것이 중요하다. 문제의 내용을 간략하게 정리하면 다음과 같다. 배열 A의 최초 크기는 3x3이다. 그리고 1초마다 다음과 같은 연산을 한다. 행의 길이 >= 열의 길이 일 경우, 배열 A의 모든 행을 정렬 행의 길이 < 열의 길이 일 경우, 배열 A의 모든 열을 정렬 배열 A를 정렬하기 위해서는 각 수가 몇번 나왔는지 알아야 하고, 정렬의 우선순위는 다음과 같다. 등장횟수..