알고리즘
[Python] 백준 1932 : 정수 삼각형
문제 https://www.acmicpc.net/problem/1932 [ 문제 조건 ] 한 줄씩 내려가면서 합이 최대가 되는 경로 구하기 더해질 수 있는 값은 대각선 왼쪽 or 오른쪽 [ 해결순서 ] 누적 값이 더해질 배열을 0으로 초기화 해서 입력받은 배열의 길이와 같게 선언 및 초기화 ( 그냥 입력받은 배열에다가 계산해도 무관하다 ) 예제를 분석하다 보니 가로 줄의 첫번째 값과 끝 값은 비교 대상이 없으므로 그냥 전 줄의 같은 인덱스 값을 더하면 되고, 처음, 끝을 제외한 인덱스 값들은 이제 대각선 왼쪽 or 오른쪽을 비교해서 더 큰 값을 현재 값에 더해준다. 그렇게 값을 누적시키면 맨 마지막 줄에 이제 여태까지 누적된 경우의 수가 배열에 저장 그 중 최대 값을 구해 출력한다. [ 예제 풀이 ] ✏..
[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번참고) 같은 열인지, 대각선상에 있는지 비교한다. ..
[Python] 백준 2468번 - 안전 영역
문제 https://www.acmicpc.net/problem/2468 [ 문제 조건 ] 문제에서 예시를 들어 설명할 때 모든 경우를 다 조사해 보면 이라고 설명되어 있다. 즉, 모든 경우의 수를 조사해야 됨 (이라고 나는 이해했다.) 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력 [ 해결순서 ] 배열을 입력할 때 N 이상인 값들만 방문여부를 True 값으로 바꾸고 깊이우선탐색을 진행한다. 깊이우선탐색을 진행하고 끝날때 안전영역 값(count)을 늘린다. 또 깊이우선탐색을 반복해야하는데 현재 count 값이 1차에서 3번째 줄처럼 할려고 했으나, ..
[Python] map 함수로 2차원배열의 최대값 구하기
map ( 적용시킬 함수, 적용할 요소들 ) arr = [[0, 0, 1, 0, 0, 1], [0, 1, 0, 2, 0, 0], [0, 0, 2, 6, 12, 1], [0, 1, 0, 3, 0, 0], [0, 9, 0, 0, 4, 0]] # 각 배열의 최대값을 하나의 리스트로 print(list(map(max,arr))) # [1, 2, 12, 3, 9] # 2차원배열의 최대 값 출력 print(max(list(map(max,arr)))) #12
[Python] 백준 9020번 - 골드바흐의 추측
문제 9020번: 골드바흐의 추측 [ 문제 조건 ] 골드바흐 수 : 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다. 골드바흐 파티션이 여러개 인 경우는 두 소수의 차가 가장 작은 것이 답 [ 해결순서 ] 이 문제를 해결하기 전에 에라토스테네스의 체가 무엇인지 알아야한다. 소수인 값을 하나씩 기준으로 (이 값을 N이라 치자) N의 배수를 범위 내에 모두 지운다. 이걸 반복하고 반복문을 빠져나왔을 때 지워지지 않은 값이 소수인 것이다. 에라토스테네스의 체 코드 n = 100 a = [False,False] + [True]*(n-1) primes = [] for i in range(2, n+1): #n까지임 if a[i]: #값이 들어있으면 primes.append(i) # 2*i 인 이유는 그 값..
[Python] 백준 11052번 - 카드 구매하기
문제 11052번: 카드 구매하기 [ 문제 조건 ] 카드 개수 < 가격 i개의 카드, 가격은 Pi 즉, 가격을 최대값으로 구해야 한다. [ 예제 풀이 ] #1장 샀을때 최대가격 dp[1] =1 dp[1] = dp[1], dp[0] + list[1] #2장 샀을때 최대가격 dp[2] = 5 dp[2] = dp[2], dp[1] + list[1] #1 + 1 (1장짜리 2개) dp[2] = dp[2], dp[0] + list[2] #0 + 5 (2장짜리 1개) #3장 샀을때 최대가격 dp[3] = 6 dp[3] = dp[3], dp[2] + list[1] #5 + 1 (2장짜리 1개 + 1장짜리 1개) dp[3] = dp[3], dp[1] + list[2] #1 + 5 (1장짜리 2개 + 2장짜리 1개) d..
[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 문제의 조건 비교에서 (가로, 세로 비교했던 것) 추가로 높이만 비교하고 토마토가 익었으면 (값..