티스토리

개발개발

검색하기

블로그 홈

개발개발

deonggideok.tistory.com/m

waterground 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

[JAVA/DP] 백준 2133 타일 채우기 1. 문제 https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 2. 풀이 DP를 사용해서 풀이한다. 2X1, 1X2 타일을 이용해 채우므로, 3XN에서 N이 홀수일 경우 타일로 채워질 수 없다. 자바 배열에서는 배열 선언시 0으로 초기화 되므로 별도로 값을 초기화해주지 않아도 된다. 경우를 2가지로 나누어서 생각한다. 3X2를 채울 수 있는 경우는 3개이다. N-2개의 타일을 채운 경우 뒤에 2X1을 채워넣는다고 생각하면, DP[N] += DP[N-2] * 3이다. 4X2, 6X2, 8X2.... 4 이후 2의 배수마다 2가지 방법으로 칸을 채울 수 있는 방.. 공감수 0 댓글수 0 2021. 12. 28.
[JAVA/BFS] 백준 14503 로봇청소기 1. 문제 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 2. 풀이 BFS를 이용해 풀이한다. 별도로 방문 배열을 사용하지 않고 방문한 부분을 2로 값을 변경했다. 이 문제에서 중요한 것은 방향을 정하는 것이다. d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽 인데, 표에 해당하는 방향을 미리 배열로 지정해 놓고 왼쪽으로 이동할 때 (기존 방향 + 3) % 4로 다음 방향을 설정해준다. 청소를 .. 공감수 0 댓글수 0 2021. 12. 27.
[JAVA/DP] 백준 12865 평범한 배낭 1. 문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 2. 풀이 DP를 이용해 풀이한다. 2차원 배열로 DP를 진행한다. 첫번째 인덱스는 무게를 의미한다. dp[k][n]일 경우, k 무게 만큼 버티고 있을 때다. 두번째 인덱스는 물품의 인덱스를 의미한다. dp[k][n]일 경우, n번째 물건까지를 고려했을 때다. 즉, DP 배열에 저장되는 값은 인덱스에 해당하는 물건들의 .. 공감수 0 댓글수 0 2021. 11. 24.
[JAVA/우선순위큐] 백준 1715 카드 정렬하기 1. 문제 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 2. 풀이 카드 묶음의 합이 가장 작기 위해선, 가장 적은 카드 합(또는 카드)를 2개를 계속해서 합하는 것이다. 즉, 오름차순 정렬된 우선순위 큐를 사용해 가장 작은 카드 합을 2개 빼내고 이 두 카드의 합을 구한 후 구한 합을 다시 우선순위 큐에 넣으면 가장 적은 카드 합을 구할 수 있다. 3. 코드 import java.util.*; import java.io.*; .. 공감수 0 댓글수 0 2021. 10. 29.
[JAVA/DFS] 백준 19236 청소년 상어 1. 문제 https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 2. 풀이 상어의 위치를 DFS를 이용해 움직인다. 상어와 물고기를 각각 객체를 만들어 사용한다. 물고기(Fish)는 좌표, 물고기 번호, 방향, 살아있는지 여부를 멤버 변수로 갖는다. 상어(Shark)는 좌표, 방향, 먹은 물고기 번호의 합을 멤버 변수로 갖는다. 물고기 번호를 입력 받고, 탐색을 시작하기전, 물고기를 번호 순서대로 먹기 위해 물고기가 담긴 list를.. 공감수 0 댓글수 0 2021. 10. 29.
[JAVA/구현] 백준 14500 테트로미노 1. 문제 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 2. 풀이 총 5개의 블록이 있는데, 이 중 ㅜ 블록(분홍색 블록)을 제외하고는 DFS 4번을 통해 대칭, 회전을 한 모든 블록의 모습을 구할 수 있다. 따라서, ㅜ를 제외한 4개의 블록은 DFS를 통해 4개 칸의 합을 구하고, ㅜ는 별도의 함수를 통해 4개 칸의 합을 구한다. 모든 칸에서 4개 블록타입을 모두 확인해야 하므로, 처음 DFS를 호출 할 때 백트래킹을 사용한다.(81~83.. 공감수 0 댓글수 0 2021. 10. 23.
[JAVA/BFS,구현] 백준 13460 구슬 탈출 2 1. 문제 https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 2. 풀이 가장 빠른 횟수를 구하기 위해 BFS를 사용한다. 구슬이 굴러가면 파란 구슬과 빨간 구슬이 같이 굴러가게 되므로, 두 구슬의 위치를 모두 담은 클래스를 선언해 사용한다. 맨 처음 구슬의 위치를 저장해 BFS를 시작한다. 구슬들의 위치 방문여부를 확인하기 위해 4차원 배열을 사용한다.(visited[n][m][n][m]) 4 방.. 공감수 0 댓글수 0 2021. 10. 22.
[JAVA/백트래킹] 백준 14889 스타트와 링크 1. 문제 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 2. 풀이 백트래킹을 이용해 풀이한다. DFS를 이용해 한 사람씩 팀에 추가시키고 이를 boolean 배열에 저장한다(boolean[] visited) 선택한 사람의 수가 n/2인 경우, 즉 두 팀이 결성된 경우 두 팀의 점수차를 구한다. 두 팀의 점수차가 0인 경우 이미 최솟값이므로 프로그램을 종료한다. 3. 코드 import java.util.*; import java.io.*; class Main{ s.. 공감수 0 댓글수 0 2021. 10. 22.
[JAVA/DFS,BFS] 백준 14502 연구소 1. 문제 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 2. 풀이 벽을 세울 위치를 선택할 때 DFS, 바이러스가 퍼지는 과정은 BFS를 이용해 풀이한다. 입력을 받을 때, 바이러스가 있는 좌표(값이 2인 부분)은 따로 저장해둔다. DFS를 이용해 벽을 세운다. 재귀함수를 이용해 DFS를 구현한다. map 중 벽을 세울 수 있는 부분(map[i][j] == 0)에 벽을 세운다.(map[i][j] = 1) 3개의 벽을 모두 세울때까지 재귀함수를 호출해 이.. 공감수 0 댓글수 0 2021. 10. 22.
[JAVA/백트래킹] 백준 14888 연산자 끼워넣기 1. 문제 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 2. 풀이 백트래킹을 이용해 풀이한다. 기호별 사용할 수 있는 남은 갯수를 담은 배열(markCnt)에서 0이 아닌 경우, 즉 기호를 사용할 수 있는 경우 기호를 사용한 계산을 한다. 모든 경우를 구하기 위해 재귀함수 실행 후, 기호별 사용할 수 있는 갯수를 다시 늘려준다.(markCnt[i]++) 계산식을 끝까지 구한 경우, 이전.. 공감수 0 댓글수 0 2021. 10. 21.
[JAVA/BFS] 백준 16236 아기 상어 1. 문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 2. 풀이 BFS를 통해 상어의 위치를 이동해가며, 먹을 수 있는 물고기 중 가장 작은 거리를 선택하고 더이상 먹을 수 없는 물고기가 없을 때까지 이 과정을 반복해 답을 구한다. 전체적인 풀이 과정은 아래와 같다. 상어의 위치를 저장하고, 상어의 위치에서부터 탐색을 시작한다. 상어의 위치에서 BFS를 해 상어의 위치를 이동시킨다. 상어가 갈 수 있는 경우는 (1) 상어의 크기보다.. 공감수 0 댓글수 0 2021. 10. 21.
[JAVA/백트래킹] 백준 15686 치킨 배달 1. 문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 2. 풀이 백트래킹을 이용해 풀이한다. 백트래킹을 통해 치킨집을 하나씩 선택하며 총 m개의 치킨집을 선택한다.(backTracking()) 백트래킹을 하기 위해, 방문여부를 나타내는 boolean[] visited을 사용한다. m개의 치킨집을 고른 경우, 도시의 치킨 거리를 구한다(getChickenDist()). 최소 도시의 치킨 거리를 구한다.(Math.min(.. 공감수 0 댓글수 0 2021. 10. 18.
[JAVA/DP] 백준 14501 퇴사 1. 문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 2. 풀이 n일에 받을 수 있는 최대 수익을 기억하기 위해 DP 배열을 사용한다. 날짜 범위 내에 일 종료가 가능한 경우(i + time[i] 공감수 0 댓글수 0 2021. 10. 18.
[JAVA/스택] 백준 2493 탑 1. 문제 https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 2. 풀이 오른쪽에서 레이저를 쏘기 때문에 오른쪽으로 시작 할 수 있지만, 그렇게 하면 최악의 경우 N!의 복잡도가 발생할 수 있다. 따라서, stack을 활용해 오른쪽부터 계산한다. 풀이 과정은 아래와 같다. 탑의 위치와 높이를 스택에 모두 저장하기 위해 별도의 클래스를 만든다. 탑의 왼쪽부터 시작한다. while문을 이용해 stack에 있는 탑들을 돌아보며, 현재의 탑 높이가 스택.. 공감수 0 댓글수 0 2021. 10. 11.
[JAVA/BFS] 백준 5014 스타트링크 1. 문제 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 2. 풀이 BFS로 풀이했다 (1) n층을 최소한의 버튼을 눌러 도착했을 때의 버튼 누른 횟수를 저장하는 배열(minBtn)을 사용해 정답을 구하고, 중복을 체크하는데 사용한다. (2) 위의 최소 버튼 누른 횟수를 저장하는 배열(minBtn)에서 시작점의 버튼 누른 횟수를 0이 아닌 1로 처리해, 시작점과 처음 도착한 층의 차이점을 만들어 처리한다. (3) 맨 마지막 정답을 처리할때, +1 한 값을.. 공감수 0 댓글수 0 2021. 10. 11.
[JAVA/BFS] 백준 2644 촌수계산 1. 문제 https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 2. 풀이 BFS를 써서 풀이한다. 처음에는 큐에서 poll 했을때 촌수를 높이는 걸로 처리를 했는데, 그렇게 하면 연결되지 않는(?), 결과에 상관없는 촌수를 계산할 때까지 더하기 처리가 나서 실패했다. 그래서 기준점을 잡아서, 기준점과의 촌수를 계산하는 배열을 따로 만들어 처리했다. 3. 코드 import java.util.Arrays; import java.ut.. 공감수 0 댓글수 0 2021. 10. 11.
[JAVA/다익스트라] 백준 5719 거의 최단 경로 1. 문제 https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 2. 풀이 시작점에서 부터 다익스트라로 최단 경로를 구한다. 도착점에서 부터 거슬러가며 최단 경로를 따로 표시한다. k[i][j] = 1; // i~j까지가 최단 경로면 1 원래의 리스트에 간선 중 최단 경로가 아닌 간선만 추가해 리스트 갱신 최단 경로를 뺀 간선으로만 다익스트라를 돌림 3. 코드 import java.io.*; import java.uti.. 공감수 0 댓글수 0 2021. 7. 15.
[JAVA/LCA] 백준 3176 도로 네트워크 1. 문제 https://www.acmicpc.net/problem/3176 3176번: 도로 네트워크 첫째 줄에 N이 주어진다. (2 ≤ N ≤ 100,000) 다음 N-1개 줄에는 도로를 나타내는 세 정수 A, B, C가 주어진다. A와 B사이에 길이가 C인 도로가 있다는 뜻이다. 도로의 길이는 1,000,000보다 작거나 같은 양 www.acmicpc.net 2. 풀이 처음엔 플로이드 와샬을 써야하는가....? 싶었지만 LCA를 써서 푸는 문제였다. LCA에서는 조상 노드들을 따로 저장하는 배열(parent)가 있는데, 이 때 노드에서부터 2^i번째 노드까지의 최솟값, 최댓값을 저장하는 따로 저장하는 것이 포인트다. 3. 코드 import java.io.*; import java.util.Array.. 공감수 0 댓글수 0 2021. 7. 15.
[JAVA/LCA] 백준 11438 LCA 2 1. 문제 https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 2. 풀이 LCA를 구현하는 문제다. LCA는 최소 공통 조상을 구하는 문제다. LCA를 구현하기 위해 현재 노드의 부모를 2차원 배열에 저장하는 방법과 1차원 배열에 저장하는 방법이 있다. 1) 부모를 2차원 배열에 저장 부모를 2차원 배열에 저장할 경우 첫번째 차원에는 노드의 인덱스가 담기고 두번째 차원에는 노드의 2^i번째 조상 노드가 저장된다. 2) 부모를 1차원 배열에.. 공감수 0 댓글수 0 2021. 7. 15.
[JAVA/플로이드 와샬] 백준 2458 키순서 1. 문제 https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 2. 풀이 플로이드 와샬을 활용한 문제다. 문제의 예제에서 나온 그래프를 잘 보자. 여기서 순서를 정할 수 있는 노드는 뿐이다. 4보다 큰사람이 , 로 2명이고, 4보다 작은 사람이 , , 로 3명이므로 총 6명 중 나보다 큰 사람 2명, 나보다 작은 사람 3명 => 나는 3등 이라는 결론을 얻을 수 있는 것이다. 즉, 현재 노드가 다른 노드들과 모두 연결되어 있는 경우 순서를 따질 수 .. 공감수 0 댓글수 0 2021. 7. 12.
[JAVA/투포인터] 백준 2143 두 배열의 합 1. 문제 https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 2. 풀이 투포인터를 사용해 풀이한다. A의 부분합과 B의 부분합의 합을 구해야하는 상황이므로 A의 부분합과 B의 부분합을 미리 구해놓고 A의 부분합과 B의 부분합을 각각 정렬해 투포인터를 이용해 합이 T일 경우, answer에 추가한다 +) A의 부분합과 B의 부분합이 중복될 경우 한번에 처리해주기 위해,.. 공감수 0 댓글수 0 2021. 7. 11.
[JAVA/백트래킹] 백준 9663 N-Queen 1. 문제 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 코드 import java.util.Scanner; // 백트래킹 public class Main { static int answer = 0; public static void nQueen(int[] arr, int n, int depth) { if(n == depth) { answer++; return; } for(int i = 0; i < n; i++) { // 한 row에서 퀸을 놓을 수 있.. 공감수 0 댓글수 0 2021. 7. 11.
[JAVA/Binary Search] 백준 1072 게임 1. 문제 https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 2. 풀이 이진탐색을 사용한다. 새롭게 해야 하는 게임의 수를 이진탐색을 사용해서 찾는다. 소숫점을 버리기 위해 새로한 게임을 포함한 승률을 구하는 가정에서 100을 곱하게 되는데, 이 때 int 범위의 수가 넘을 수 있으므로 long 처리를 해줘야 된다는 것을 주의 해야 한다. 3. 코드 import java.util.Scanner; //이진탐색 public class Main.. 공감수 0 댓글수 0 2021. 7. 8.
[JAVA/투포인터] 백준 2842 집배원 한상덕 1. 문제 https://www.acmicpc.net/problem/2842 2842번: 집배원 한상덕 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 www.acmicpc.net 2. 풀이 투포인터와 BFS를 모두 활용한다. 구해야 되는 것은 가장 작은 고도의 차이므로, 가장 높은 고도(high)와 가장 낮은 고도(low)를 설정해 그 고도 내에서 집배원이 모든 집을 방문할 수 있는지 본다. 투포인터를 이용해 low 값 과 high 값을 변경해가며 가장 작은 고도차를 찾는다. 고도 내에서 모든 집을 방문할수 있는지 확인 할 때 BFS를 사용한다.. 공감수 0 댓글수 0 2021. 7. 8.
[JAVA/투포인터] 백준 7453 합이 0인 네 정수 1. 문제 https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 2. 풀이 숫자가 A, B, C, D 총 네종류가 있고 합이 0이 되는 A, B, C, D 쌍을 구해야 한다. 이를 A와 B의 가능한 모든 합과 C와 D의 가능한 모든 합으로 나누어 구하고 A와 B의 합과 C와 D의 합 중 0이 되는 쌍을 찾는다. 즉, (A+B) + (C+D) 이런식으로 나누어 생각하는 것이다. A와 B의 합과 C와 D의 합은 가능한 모든 경우의 수를.. 공감수 0 댓글수 0 2021. 7. 8.
[JAVA/Deque] 백준 11003 최솟값 찾기 1. 문제 https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 2. 풀이 방법 1) 우선 순위 큐 사용 자바로 우선 순위 큐를 사용해 정렬 된 값을 바로 사용해서 하려고 했더니 시간 초과가 난다. 자바로 풀기 위해 다른 방법을 찾아 봤다. 방법 2) Deque 사용 숫자가 있는 위치와 숫자의 값을 모두 Deque에 넣어 풀이하는 방법이다. (1) 현재 숫자를 입력 받는다. (2) 현재 덱 내에 있는 수 중 뒤에서 부.. 공감수 0 댓글수 0 2021. 7. 7.
[C++/구현] 백준 9093 단어 뒤집기 1. 문제 https://www.acmicpc.net/problem/9093 9093번: 단어 뒤집기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다. 단어의 길이는 최대 20, 문장의 길이는 최대 1000이다. 단어와 단어 사이에는 www.acmicpc.net 2. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include #include #include using namespace std; int main() { int t; cin >> t; // 이때, 정수 값 뒤 누른 엔터가 그대로 남아있어 getline에 들어감 string s, temp.. 공감수 0 댓글수 0 2020. 1. 29.
[C++/Map] 백준 9375 패션왕 신혜빈 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include #include #include #include using namespace std; int main() { int t; cin >> t; string cloth, kind; while (t--) { int n; cin >> n; map m; // 옷 종류와 종류별 수를 담는 map while (n--) { cin >> cloth >> kind; m[kind]++; // 옷 종류별 수 갱신 } long long res = 1; for(auto it = m.begin(); it != m.end(); it++){ res *= it->second + 1; .. 공감수 0 댓글수 0 2020. 1. 29.
[C++/LIS] 백준 11053 가장 긴 증가하는 부분수열 1.문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 2. 풀이 가장 긴 증가하는 부분수열은 LIS(Longest Increasing Sequence)로 매우 유명한 알고리즘이다. DP를 이용하는 문제는 매번 어렵다. 문제에는 두가지 배열이 있다. 숫자들의 나열이 담긴 배열 현재 인덱스에 해당하는 숫자까지의 LIS를 저장하는 배열 문제에서 2)의 배열에서 이전까지.. 공감수 0 댓글수 0 2019. 12. 27.
[C++/GCD] 백준 2981 검문 1. 문제 https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 2. 풀이 숫자들이 여러개 입력 될 때 각 숫자는 n = a * x + r(x는 나누는 수, a는 몫, r은 나머지)로 표현 할 수 있다. A, B, C,.... 이렇게 숫자가 오름차순을 나열 되어있다고 할 때, 각 숫자들은 a * x + r, b * x + r, c * x + r....로 표현 될 수 있고 r = A - a * x = B - b * x A - B = x * (a - b) 로 근접한 두.. 공감수 0 댓글수 0 2019. 12. 27.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.