백준
[백준] 1002번 - 터렛
오늘은 살짝 수학공식이 필요한 문제를 풀어보았습니다 개념만 알고 그대로 알고리즘에 적용하면 어렵진 않은 문제인 것 같네요! https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 문제에 사용된 변수명과 공식을 설명하자면, 입력받은 r1, r2는 두 원의 반지름이고 R은 두 원의 중심 사이의 거리 입니다. 반지름과 두 점 사이의 거리를 비교하면서 교점을 구하면, 있을 수 있는 위치의 개수가 나옵니다. 경우의 수는 다음과 같은데요. 이 경우를 그대로 코드로 작성하면 문제를 해결할 수 있습니다.
[백준] 2583번 - 영역 구하기 (DFS / BFS)
오늘은 문제를 보자마자알 수 있는 DFS, BFS 분류의 문제를 풀어보았습니다. 오랜만에 풀어서 조금 감을 잃었는지 조금 헤매면서 풀었던 것 같네요 😅 바로 풀이 보시죠!!! 1. 문제 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 2. 풀이 문제 입력부터 확인하면, 첫번째 줄에 세로, 가로, K 를 입력하고 (K는 모눈종이의 직사각형의 개수) 두번째 줄부터 직사각형의 꼭짓점 좌표를 하나씩 입력받습니다. 문제에서 해당 직..
[Python] 백준 1074번 : Z
문제 1074번: Z [ 문제 조건 ] Z 모양 순서대로 방문 입력한 r행 c열이 몇번 째로 방문하는지 출력 [ 해결순서 ] 1번째 풀이 -> 실패 재귀적으로 모든 분면의 모든 값을 확인해서 2X2 배열일 때 ( 더이상 등분하지 않아도 되면 ) 조건에 맞을 때까지 값을 하나씩 늘려가면서 몇번째 방문인지 계산하다가 r행 c열의 조건이면 여태껏 더한 방문값을 출력하고 종료한다. 이렇게 하면 시간 초과가 날 뿐만 아니라, 입력한 값에 포함하는 분면이 아닌 값들도 모두 확인해 비효율적인다. 2번째 풀이 (참고) 이 풀이는 아이디어를 참고한 후 코드를 짜면서 해석했는데, 이 문제를 풀 때 내가 처음에 생각해낸 아이디어와 비슷했다. (코드를 못 짜겠어서 1번째 풀이로 풀었지만..) 입력한 값이 몇 사분면인지 계산한..
[Python] 백준 11051 : 이항 계수 2
문제 11051번: 이항 계수 2 [ 문제 조건 ] nCk 를 구하면 된다. [ 해결순서 ] 먼저 분류가 DP라서 DP로 해결하려 했다. 팩토리얼 값들을 저장하기 위해 dp배열을 선언해서 반복해서 곱한 값들을 배열에 저장하였고 계산 된 값을 그냥 공식에 맞게 출력했다. nCn이나 nC0인 경우는 값이 그냥 1이기 때문에 조건문을 추가하였다. ( 넣지않아서 에러가 발생했다 ) 파이썬에 내장되어 있는 factorial 모듈도 있길래 그것도 사용해서 풀어봤다. 3줄만에 풀 수 있었다 ! ✏️한줄평 : 재귀적으로 팩토리얼을 구하지 않고 dp로 풀어볼 수 있는 문제였다. 코드
[Python] 백준 1309번 : 동물원
1309번: 동물원 [ 문제 조건 ] 2 * N 배열의 동물원 우리 사자를 배치할 때 가로 세로로 붙어있으면 안됨 사자가 한마리도 없는 경우도 1가지 경우로 침 [ 해결순서 ] 처음엔 기존의 dp 같은 방식으로 풀려고 시도해 배열의 각 칸에 숫자를 부여해서 조건에 맞는 조합으로 값을 계산해서 구하려고했다. 뭔가 규칙이 보이는 것 같다가도 막상 식을 못세우겠어서 조금 헤매다 결국 구글의 도움을 좀 받았다. ( 삽질을 하고있단 느낌이 .. ) 첫번째 줄에 경우를 3가지로 나눠서 계산을 해야한다. *4번 줄 참고 경우의 수를 나눈 후 제일 작은 예시인 2 X 2 배열일 때를 직접 적어가며 규칙을 찾아보려했다. 사진을 참고하면 이해가 빠르겠지만, 한마리도 두지 않는 경우는 ( 두지 않는 경우, 왼쪽, 오른쪽 )..
[Python] 백준 1946 : 신입사원
문제 https://www.acmicpc.net/problem/1946 [ 문제 조건 ] 각 지원자마다 서류, 면점 순위를 입력 (* 주의 성적이 아니므로 순위가 낮은게 좋은거임) 서류, 면접 성적 중 적어도 다른 지원자보다 둘 중 하나 높아야 함 → 즉, 다른 지원자보다 둘 다 낮으면 탈락 [ 해결순서 ] 문제를 해결하는 포인트 중 하나가 입력 받은 후 먼저 1차적으로 서류순으로 등수를 정렬 하는 것이다. ( 면접 순으로 해도 상관 X ) 이미 서류 순으로 정렬 했다면, 이제는 면접 등수만 갖고 비교하면 되므로 훨씬 수월하다. 먼저 기준 값으로 서류 1등의 면접 등수를 두고 값을 계산하는데, 이미 뒤에 지원자들은 서류 등수는 다 낮은데 면접 등수까지 낮으면 둘 다 낮은 것이므로 탈락 기준 값보다 면접 ..
[Python] 백준 9663 : N-Queen
문제 https://www.acmicpc.net/problem/9663 [ 문제 조건 ] 1 ≤ N < 15 출력 : 서로 공격할 수 없게 놓는 경우의 수 백트래킹 문제 → 개념을 알고 있어야 함 [ 해결순서 ] 체스판에 퀸을 놓기위한 조건은 퀸의 가로, 세로, 대각선에 위치한 곳에 두면 안된다. 백 트래킹 문제에선 퀸을 놓을 때 직전의 열에 두지 않는다고 한다. ( 중복제거를 위해 ) 하나의 행에 하나의 퀸만 놓을 수 있다. 그렇다면 N * N개의 경우의 수가 존재 할 텐데 이 중에서 서로 공격하지 않게 놓는 경우의 수를 구해야한다. nqeen()은 퀸을 오른쪽 행으로 하나씩 옮기면서 경우의 수를 확인하고 check()로 행은 비교할 필요가 없고 (3번참고) 같은 열인지, 대각선상에 있는지 비교한다. ..
[JAVA] 백준 1245 - 농장 관리
문제 1245번: 농장 관리 [ 문제 조건 ] 인접한 격자 8개를 모두 비교할 dx, dy 배열 산봉우리 높이 > 산봉우리 인접한 격자의 높이 산봉우리 총 갯수 = count 해당 값이 산봉우리 인지 아닌지 여부 = top [ 해결순서 ] 문제에서의 '인접하다' 정의를 먼저 이해해야한다. X, Y 좌표 차이가 1이하인 값인 인접한 값. 대각선 4군데 상하좌우 총 8개의 값을 비교하여 깊이우선탐색을 진행해야한다. 모든 farm 배열을 확인하여 방문하지 않은 값 중 0이 아닌 산봉우리가 될 수 있는 값들을 기준으로 dfs() 를 실행하는데 그 전에, 해당 값이 산봉우리라고 임의로 지정해두고 깊이우선탐색 실행 후에도 해당 값이 제일 높으면 그 때 총 값을 증가시킨다. 기존의 깊이우선탐색을 진행하..
[JAVA] 백준 11057 - 오르막 수
문제 11057번: 오르막 수 [ 문제 조건 ] N의 범위는 1~10000 오르막 수의 개수를 % 10007 [ 해결순서 ] 직접 노트에 적어보면서 규칙을 찾으려고 했다.이를 보면 점화식을 구할 수 있다. 이를 보면 점화식을 구할 수 있다. 각 자릿수별로 끝자리 0~9에 따라 들어갈 수 있는 경우의 수를 구해 해당 n의 경우의 수를 모두 더하면 총 오르막 수 의 개수를 구할 수 있다. 점화식 : dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) ✏️한줄평 쉽다고 생각했지만, 조금 생각을 해봐야하는 신박한 문제였다. 코드
[JAVA] 백준 7569번 - 토마토
문제 7569번: 토마토 [ 문제 조건 ] 입력 1 = 익은 토마토 0 = 익지않은 토마토 -1 = 토마토 없음 출력 0 = 저장될 때 모든 토마토 익음 1 = 모든 토마토 익지 못함 n = 모두 익을 때 까지 최소 며칠이 걸리는지 보관 후 하루가 지나면 익은 토마토와 인접한 건 익음 [ 해결순서 ] 여태까지 풀던 문제는 상하좌우만 비교해서 해결하면 됐으나, 위 아래도 비교해서 6가지 경우를 비교해야한다. 3차원 배열로 가로,세로,높이의 값을 입력받고 너비우선탐색의 대상은 익은 값만 이므로 입력받을 때, 토마토가 익은 것들만 큐에 넣는다. 큐에 넣은 것들을 하나씩 꺼내며 너비우선탐색 한다. 기존 유사한 BFS 문제의 조건 비교에서 (가로, 세로 비교했던 것) 추가로 높이만 비교하고 토마토가 익었으면 (값..