WIZI Blog

www.acmicpc.net/problem/21611 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, ( www.acmicpc.net 2021 삼성 인턴 기출문제였다고 합니다. 어렵다는 말이 많아서 한번 풀어봤더니 64%에서 런타임 에러가 났습니다;; 원인을 분석해본 결과 3 1 1 1 1 1 0 1 1 1 1 3 1 과 같은 테케를 넣었을 경우 모든 구슬이 사라지는 경우가 발생하는데 큐를 사용하여 구현했던 저는 여기서 터졌습니다. 아무것도 없는 큐에서 값을 pop하려 하니 런타임 에러가 발생한 것이었고 이를 고쳐주니 문제를..

문제 www.acmicpc.net/problem/8111 8111번: 0과 1 각각의 테스트 케이스마다 N의 배수이면서, 구사과가 좋아하는 수를 아무거나 출력한다. 만약, 그러한 수가 없다면 BRAK을 출력한다. www.acmicpc.net 풀이방법: 모듈러 연산을 활용하여 나머지를 체크하면서 bfs를 진행하였다. 첫 숫자가 0이되면 안되므로 1부터 시작하는데 현재숫자를 x라고 했으면 다음 숫자는 각각 x*10 + 0, x*10 + 1 이 된다. 이를 통해 다시 모듈러연산으로 계산을 진행한다. 또한 방문을 했으면 trace라는 배열을 이용하여 여태까지 왔었던 경로를 기억해놨다가 print(0)으로 (모듈러 0, 즉 나누어 떨어질 때 종료하므로) 경로를 역추적하였다. (-1일때 종료) 다만,, 한가지 의문..

www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net 그리디, 브루트포스, 비트마스킹을 이용한다. 처음에 문제를 잘못읽었는데 동전을 선택하는 것이 아니라 행이나 열을 선택하는 것이었다. 문제를 제대로 읽고나니 풀이방법이 바로 떠올랐다. 풀이 방법: 비트마스킹을 활용하여 20개의 조합(100만 정도임)을 전부 해볼 것인데, 만약 행과 열 모두 브루트포스로 돌리게되면 (100만*100만)으로 시간초과가 난다. 그래서, 열만 조합을 돌려 뒤집어주고, 행은 뒷면인 동..

programmers.co.kr/learn/courses/30/lessons/72415 코딩테스트 연습 - 카드 짝 맞추기 [[1,0,0,3],[2,0,0,0],[0,0,0,2],[3,0,1,0]] 1 0 14 [[3,0,0,2],[0,0,1,0],[0,1,0,0],[2,0,0,3]] 0 1 16 programmers.co.kr 2021 kakao blind recruitment 문제였다. 부르트포스와 bfs를 사용하여 문제를 해결하였다. 문제풀이: 1. 카드의 짝 만큼 permutation을 돌린다. (next_permutation 사용) 2. 카드의 조합을 순서대로 찾아가며 bfs로 짝을 찾아 카드를 지운다. 3. 최소가 나오는 경우를 찾아야하므로 모든 경우를 다 본다. 만약 (1카드, 2카드, 3카..

www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 기본적인 bfs문제다. 내가 이미 방문했던 곳을 표시하는 배열이 필요한데 3차원 배열로 벽을 몇번 뚫었나를 체크한다. 풀이과정 {x,y, 벽뚫은 횟수} 세가지 정보를 담아서 큐에 넣는다. 여기서 큐에 넣는 방법은 두가지로 갈린다. 1. 다음칸이 벽인경우 2. 다음칸이 뚫려있는경우 다음 칸이 벽인경우 현재 내가 (벽을 뚫은 횟수+1) 가 있는 check배열에 이전까지 왔었던 거..

www.acmicpc.net/problem/14939 14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net 비트마스킹과 브루트포스를 이용한 문제이다. 가로의 길이가 10밖에 안되므로 조합을 구성하면 2^10 이고 전부 도는거 10*10 으로 해서 시간복잡도 계산을 하였다. 또한 비트마스크를 이용한 조합구현 코드를 이용해서 구현하였다. for (int subset = set;; subset = ((subset - 1) & set)) subset이 0인것도 확인을 해야하므로 for문 안쪽에서 subset = ..

www.acmicpc.net/problem/17831 17831번: 대기업 승범이네 첫 번째 줄에 판매원들의 수 N(2 ≤ N ≤ 200,000)이 주어진다. 판매원들은 1번, 2번, …, N번으로 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 2번 판매원부터 N번 판매원의 사수가 순서대 www.acmicpc.net 문제 제목을 봤는데 친구가 사업에 성공했나보다. 속초사는 친구였는데 잘되어서 서울에서 왕부자가 되었다. 이 문제는 2019 홍익대학교 프로그래밍 경진대회 문제였다. 알고리즘 분류 : 트리에서의 다이나믹 프로그래밍. 풀이과정: dp[MAX][2]를 사용하여 dp[i][0]에는 현 멘토노드를 선택하지 않은경우, dp[i][1]에는 현 멘토노드를 선택한 경우로 최댓값을 저장하였다. 필자..

programmers.co.kr/learn/courses/30/lessons/72416 코딩테스트 연습 - 매출 하락 최소화 CEO를 포함하여 모든 직원은 팀장 또는 팀원이라는 직위를 가지고 있으며 그림에서는 팀장과 팀원의 관계를 화살표로 표시하고 있습니다. 화살표가 시작되는 쪽의 직원은 팀장, 화살표를 받는 programmers.co.kr 2021 KAKAO BLIND RECRUITMENT의 마지막 문제이다. 알고리즘 분류는 트리에서의 DP 이다. tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/ 2021 카카오 신입공채 1차 온라인 코딩 테스트 for Tech developers 문제해설 지난 2020년 9월 12일 토요일 오후 2시부터 7시까지 ..

programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 작년에 봤었던 카카오 블라인드 2021문제였다. 작년에 3-7번 문제중 가장 만만한 문제였던 것으..

programmers.co.kr/learn/courses/30/lessons/72412