알고리즘
-
SW Expert Academy D2 문제 풀이알고리즘 2023. 6. 28. 19:37
1959 두 개의 숫자열 두 개의 숫자열이 주어질 경우 길이가 짧은 배열을 움직여 마주보는 숫자를 곱한 값의 합이 가장 큰 경우를 구하는 문제입니다. 이 문제는 모든 값을 모두 대조해봐야된다고 생각했으므로 숫자열이 마주칠 수 있는 모든 경우의 수를 탐색할 수 있도록 했습니다. 모든 경우의 수에서 마주보는 숫자 곱의 합의 최대값을 구할 수 있도록 했습니다. 1974 수도쿠 검증 완료한 수도쿠가 주어졌을 경우 해당 수도쿠가 성공했는지 실패했는지 확인하는 문제입니다. 이중 for문을 이용하여 해결했습니다. 가로와 세로는 sudoku[i][j], sudoku[j][i]에 1~9의 숫자가 존재하는지 확인하면 됩니다. 3*3격자는 sudoku[(i//3)*3+j//3][(i%3)*3+j%3]에 1~9가 모두 존재하..
-
백준 1339 단어 수학알고리즘 2023. 6. 27. 10:22
문제 설명 이번 문제는 N개의 알파벳 단어가 주어질 경우 알파벳을 숫자 0~9 중 하나로 바꿔서 각 단어의 합을 구할 때, 이 합의 최대를 구하는 문제입니다. 모든 단어에 포함된 알파벳의 종류는 10개입니다. 각 단어의 길이는 8입니다. 문제 풀이 아이디어 최대값 각 알파벳을 숫자로 바꾼 뒤의 합을 구할 때, 높은 자리수의 알파벳이 큰 숫자가 되어야 합의 최대가 될 수 있습니다. 그러므로 가장 높은 자리에 위치한 알파벳이 큰 숫자가 되어야 합니다. 만약 여러 단어에서 같은 자리수의 알파벳 중 더 높은 숫자를 줘야 하는 알파벳을 고려해야 한다면, 이후에 또 등장하고 등장하는 자리수가 더 높은 알파벳에 더 높은 숫자를 부여해주어야 합니다. 등장하는 자리수 구하기 각 알파벳이 등장하는 자리수를 저장해두어야지만..
-
백준 7576번 토마토알고리즘 2023. 6. 26. 21:16
문제 설명 이번 문제는 토마토를 보관할 경우, 하루가 지나면 익은 토마토 주변의 토마토가 익게 될 경우 모든 토마토가 익으려면 며칠이 걸리는지 구하는 문제입니다. 주변은 상하좌우를 말합니다. 보관 창고에는 빈 공간이 존재합니다. 모든 토마토가 익을 수 없는 경우 -1 문제 풀이 아이디어 BFS 각 익은 토마토로부터 주변의 토마토가 익게 되므로 BFS를 통해 익은 토마토의 주변부터 탐색할 수 있도록 합니다. 풀이 BFS 현재 익은 토마토의 좌표를 queue에 넣어줍니다. 이 때, 첫 날 익은 토마토를 모두 한 배열안에 넣어준다음 이것을 queue에 넣어줍니다. queue= [ [ [r1,c1], [r2,c2], ... ] ] 이런 식으로 진행할 경우 진행된 날짜를 세기 편한 것 같습니다. queue의 원소..
-
백준 2252번 줄 세우기알고리즘 2023. 4. 30. 10:07
문제 설명 이번 문제는 일부 학생의 키를 비교한 정보가 주어질 때, N명의 학생들을 키 순서대로 줄 세우는 방법을 구하는 문제입니다. (답이 여러가지일 경우 한 가지만 출력해줍니다.) 문제 풀이 아이디어 줄을 서는 순서 입력으로 A B가 주어졌을 경우 B는 무조건 A 뒤에 있어야 하므로, B가 줄에 서기 위해 {A가 줄에 먼저 서야 된다}는 전제조건이 생깁니다. (줄을 앞에서부터 선다고 가정했습니다.). 만약 B보다 앞에 와야하는 사람이 A 한 명이고 현재 A가 줄을 서게 된다면, B는 이후 어느 곳이든 줄을 서도 됩니다. 만약 B보다 앞에 와야하는 사람이 A와 C일 경우, A와 C가 모두 줄을 서야지만 B가 줄에 설 수 있게 됩니다. 풀이 변수 followed[N][] = 자신의 뒤에 오는 사람을 저장..
-
백준 14499번 주사위 굴리기알고리즘 2023. 4. 29. 10:26
문제 설명 이번 문제는 주사위의 전개도가 주어지고, 주사위를 놓은 곳의 좌표와 이동시키는 명령이 주어졌을 때, 주사위가 이동했을 때마다 상단에 쓰여있는 값을 구하는 문제입니다. 지도의 각 칸에는 정수가 하나씩 쓰여 있습니다. 주사위를 굴렸을 때, 이동하는 칸에 쓰여 있는 수가 0이면 주사위의 바닥면에 쓰여 있는 수가 칸에 복사됩니다. 0이 아닌 경우에는 칸에 쓰여 있는 수가 주사위의 바닥면으로 복사되며, 칸에 쓰여 있는 수는 0이 됩니다. 주사위는 지도 바깥으로 이동시킬 수 없습니다. 만약 바깥으로 이동하려고하면 해당 명령을 무시해야하고, 출력도 하면 안 됩니다. 문제 풀이 아이디어 주사위 면 하늘을 바라보고 있는 면(0)과 동서남북(1,2,3,4)를 향하고 있는 면, 바닥에 닿는 면(5) 총 6개의 면..
-
백준 10021번 Watering the Fields알고리즘 2023. 4. 14. 15:27
문제 설명 이번 문제는 여러 좌표에 농지가 있을 경우 이 농지들을 하나로 잇는 관개 시설을 만들 때, 모든 농지들을 포함하는 관개 시설을 짓는 비용의 최소값을 구하는 문제입니다. 좌표가 (ai,aj)인 농지 a와 (bi,bj)인 농지 b 사이의 관개 시설을 짓는 비용은 (ai-bi)^2+(aj-bj)^2 입니다. 문제 풀이 아이디어 트리 모든 농지를 잇는 최소의 비용을 구하기 위해서는 농지를 잇는 간선의 개수를 최소로 해야합니다. 그러므로, 농지를 잇는 간선의 개수는 {농지 개수-1}입니다. 정렬 관개 시설의 전체 비용의 최소값을 찾아야 하므로 비용이 가장 적은 간선부터 포함 여부를 확인해야합니다. 그러므로 비용을 기준 오름차순으로 간선을 정렬해야 합니다. union-find 농지 a와 농지 b를 잇는 ..
-
백준 3190번 뱀알고리즘 2023. 4. 13. 10:16
문제 설명 이번 문제는 Dummy라는 도스게임을 제작하는 문제입니다. N * N 정사각 보드위에서 뱀이 매 초마다 아래와 같은 규칙으로 움직이고 사과의 위치와 뱀의 이동경로가 주어질 때, 게임이 몇 초에 끝나는지 계산하는 문제입니다. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킵니다. 만약 이동한 칸에 사과가 있다면 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않습니다. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워준다. 즉, 몸길이는 변하지 않습니다. 문제 풀이 0. 변수 N=int(input()) # 보드의 크기 K=int(input()) # 사과의 개수 apples=[list(map(int,input().split())) for _ in range(K)] # 사과의..
-
백준 13460 구슬 탈출 2알고리즘 2023. 4. 12. 10:32
문제 설명 이번 문제는 보드 안에 빨간색 파란색 구슬이 한 개씩 있고 기울일 수 있는 최대 횟수가 주어질 경우, 해당 횟수 내에 빨간 구슬을 먼저 구멍에 빠질 수 있다면 해당 기울인 횟수를 구하는 문제입니다. 구슬은 손으로 건드릴 수 없고, 중력을 이용해 왼쪽 오른쪽 위 아래로 기울여서 구슬을 움직여야합니다. 기울이는 동작은 구슬에 벽에 닿아 움직이지 않을 때까지만 합니다. 빨간 구슬과 파란 구슬은 한 칸안에 있을 수 없습니다. 빨간 구슬이 구멍에 빠진 뒤 해당 턴에 파란 구슬도 구멍에 빠지면 실패입니다. 문제 풀이 아이디어 브루트 포스 이번 문제는 구슬의 움직임에 따라 빨간 구슬 파란 구슬의 움직임을 모두 확인해야 하므로, 모든 경우의 수를 고려하는 브루트 포스 방법을 생각했습니다. 고려해야 하는 점 ..