ProgramSoliving (197) 썸네일형 리스트형 백준 : 1039 JAVA https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 처음 문제를 접했을 때는 완전탐색으로 2개를 짝지어 교환하는 경우의수 7! 카운트가 최대 10개 완탐을 했더니 메모리초과가 발생하였다 아마 (7!) ^ 10 의 경우의를 탐색해거 그런것 같다. 따라서 BFS문제로 접근하였다. 자리를 바꾼다는것은 visit[num][cnt] 로 지정해서 cnt 인 카운터로 num을 방문 했는가 안했는가를 boolean형으로 관리하고 넢이우선순위 연산을 진행한다. 이대 중간에 '0'이 맨앞에 오는 경우도 갈수가 없는걸 처리하면 정답이나온.. 백준 : 9376 https://www.acmicpc.net/problem/9376 9376번: 탈옥 문제 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타나 있다. 감옥은 무인 감옥으로 죄수 두 명이 감옥에 있는 유일한 사람이다. 문은 중앙 제어실에서만 열 수 있다. 상근이는 특별한 기술을 이용해 제어실을 통하지 않고 문을 열려고 한다. 하지만, 문을 열려면 시간이 매우 많이 걸린다. 두 죄수를 탈옥시키기 위해서 열어 www.acmicpc.net 처음 접근햇던 방식은 죄수 두명을 각각 큐에 넣어서 탈출할수 있는 경로를 구하고 그경로를 가지고 각각 대조햇을때 겹치는 부분을 제거하는식으로.. 백준 : 2933 JAVA https://www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄이 저장되어 있으며, 던진 막대기가 미네랄을 파괴할 수도 있다. 동굴은 R행 C열로 나타낼 수 있으며, R×C칸으로 이루어져 있다. 각 칸은 비어있거나 미네랄을 포함하고 있으며, 네 방향 중 하나로 인접한 미네랄이 포함된 두 칸은 같은 클러스터이다. 창영은 동굴의 왼쪽에 서있 www.acmicpc.net BFS DFS 카테고리에 잇엇지만 사실상 시뮬레이션 문제. 명령의 순서쌍을 0 1 2 3 4 5 총 6개라고할때 k%2 == 0 이면 왼쪽.. 백준 : 10830 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 행렬을 2^n 제곱꼴로 미리 저장해둿다가 B 제곱을 구해야하면 B = 2^1 + 2^4 + 2^8 꼴로 분해해서 사용한다. package day0301; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class B1083.. 백준 : 11401 https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 페르마의 소정리와 확장 유클리드 알고리즘으로 값구하기. 확장 유클리드알고리즘은 Ax + By = GCD(A,B) 라고할때 맞는 정수 x y를 구하는 방법이다. 재귀 적인 방법이 있고 반복문을 통한 반복이 있는 반복문을 통한방법이 이해하기 쉬우므로 사용하였다. 아래는 재귀적으로 푸신분의 소스참조.. 이해할려고해도 이해잘안됨 https://onsil-thegreenhouse.github.io/programming/probl.. 백준 : 3197 https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 문제 두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다. 호수는 가로로 R, 세로로 C만큼의 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다. 호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다. 아래에는 세 가지 예가 있다. ...XXXXXX..XX.XXX ....XXXX.......XX www.acmicpc.net 단순 BFS탐색으로는 많은 시간이 걸린다. 줄일수 있는건 2가지가 있다. 얼음이 녹는 시간을 사전에 미리구한다. 현재위치가 X일때 상.. Sqrt Decomposition 평방분할 알고리즘 구간합을 구할때 쓰는 알고리즘이다. 구간을 √N 으로 나눠주고 그 구간의 합을 구하는 알고리즘이다. 만약 0~15 라면 크기가 4인 배열을 만든다음 0~3 , 4~7 , 8~11 ,12~15 합들을 배열에 넣어준다. 그리고 배열 4~7의 값을 구해라고하면 바로출력하면된다. 하지만 3~9처럼 걸쳐잇는 합을 출력해야할경우에는 left right를 만들어서 크기가 4식 나눳으므로 인덱스값이 4로나누엇을때 0이 되는애들이 될때가지 left를 더하거나 right를 빼면서 0이나오는 값으로 만들어준다. 안되는값들은 그냥 arr에서 직접 result에 더해준다. 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.. 백준 : 1655 https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다. www.acmicpc.net 문제는 MaxHeap Minheap을 만들어서 중앙값 왼쪽 오른쪽을 관리하는 것이다. Maxheap mid Minheap 이런식으로 정렬은한다고 친다면 처음 받은 중앙값을 mid로 하고 관리하면된다. 이때 처음받은 값을 기준으로 그다음값이 mid 보다 크다면 Minheap에 넣어주고 작다면 Maxheap에 넣어준다. 이때 중.. 이전 1 ··· 13 14 15 16 17 18 19 ··· 25 다음