ProgramSoliving (197) 썸네일형 리스트형 백준 : 10775 https://www.acmicpc.net/problem/10775 10775번: 공항 문제 오늘은 신승원의 생일이다. 박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다. 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다. 공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 도킹된 게이트에는 다른 비행기가 도착할 수 없다. 이러한 사고가 일어나면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 www.acmicpc.net 문제해결 방법 : Union-Find 이문제에서 생각할것은 도킹을 할수 없는 상태가 잇다면 그다음 쿼리는 처리안해주고 끝난다는 것이다. 두.. 백준 : 1637 https://www.acmicpc.net/problem/1637 1637번: 날카로운 눈 문제 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그 원숭이는 좀 특이한 원숭이였다. 어떤 것도 꿰뚫어볼 수 있는 날카로운 눈을 가진 기이한 원숭이였다. 부드러운 눈을 가진 멍멍이는 언제나 날카로운 눈을 가진 원숭이를 부러워했지만 한편으로는 매우 질투했다. 어느 날 멍멍이는 원숭이의 날카로운 눈이 너무 샘나서 원숭이를 직접 패고 싶었지만 날카로운 눈으로 찌를까봐 무서워서 때리지는 못하고 대신, 원숭이에게 문제 하나를 던져주었다. 그 문제 www.acmicpc.net 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.. 백준 : 5213 JAVA https://www.acmicpc.net/problem/5213 5213번: 과외맨 문제 과외맨은 평소에 서강대학교 학생 이민혁으로 위장하고 있는 한국의 대표적인 영웅이다. 그는 슈퍼 히어로가 너무 미국에 집중되어 있는 현실을 안타까워했고, 그의 절친한 친구인 스파이더맨과 아이언맨에게 한국으로 와서 같이 영웅 활동을 하자는 제안을 했으나 거절당했다. 얼마 전, 오랜 잠에서 깨어난 고대 마야인들이 과외맨이 수업을 듣는 동안 과외 노트를 훔쳐갔다. 과외맨은 빼앗긴 노트를 찾아오기 위해 인천 공항으로 가서 과테말라로 가는 비행기를 탔다. 일단 www.acmicpc.net 문제를 푸는데 작은 부분에서 많이 해매었던 문제다. 도미노 판을 표시하는 Map과 각각의 도미노의 번호를 표시하는 맵을 만들면된다. 물론 .. 백준 : 12886 https://www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌 세개는 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려고 한다. 강호는 돌을 단계별로 움직이며, 각 단계는 다음과 같이 이루어져 있다. 크기가 같지 않은 두 그룹을 고른다. 그 다음, 돌의 개수가 작은 쪽을 X, 큰 쪽을 Y라고 정한다. 그 다음, X에 있는 돌의 개수를 X+X개로, Y에 있는 돌의 개수를 Y-X개로 www.acmicpc.net boolean 형을 잘못생각하면 1000 1000 1000 구조로 해야하나 생각 할수 있다. 이렇게 제출하면 메모리초과 오류를 발생시킨.. 백준 : 1086 JAVA https://www.acmicpc.net/problem/1086 1086번: 박성원 첫째 줄에 정답을 기약분수 형태로 출력한다. p/q꼴로 출력하며, p는 분자, q는 분모이다. 정답이 0인 경우는 0/1로, 1인 경우는 1/1로 출력한다. www.acmicpc.net 비트마스크, 메모이제이션, GCD 가 사용된다. TSP처럼 현재의 상태가 A 일때 방문한노드가 falg(000000000) 일때 값은 얼마인가 하고 물어볼수가 있다. 주의 할점은 숫자의 길이가 50이기때문에 char 형으로 문자를 받고 앞에서부터 나머지 연산을하면서 나머지를 구해야한다. ex) 5221 에 나머지 17을 구하기 위해선 5221%17 이 아니라 앞에서부터 5%17 = 5 -> 두번째 문자열로 이월 52%17 = 1 -> 세.. 백준 : 16946 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다. 각각의 벽에 대해서 다음을 구해보려고 한다. 벽을 부수고 이동할 수 있는 곳으로 변경한다. 그 위치에서 이동할 수 있는 칸의 개수를 세어본다. www.acmicpc.net 하나의 정점에서 BFS를 탐색을 한다면 시간초과걸린다 일단 모든 정점을 0으로 이어저있는칸의 구간별로 개수를 센다. 이렇게 모든 값을 매긴다음 1을 기준으로 구역이 인접해있는지센다. 잇때 set을 쓰.. 백준 : 10217 https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세에 힘입어 구글 역시 대기업답게 비용 감축에 열을 내고 있었던 것이다. 초대장 내용에 의하면 구글은 찬민에게 최대 M원까지의 비용만을 여행비로써 부담해주겠다고 한다. 인천에서 LA행 직항 한 번 끊어주는게 그렇게 힘드냐고 따지고도 싶었지만, www.acmicpc.net 문제 접근 방법 제약시간 10초에 많은 TestCase를 테스트하는 문제였다. 처음에는 단방향 노드인데 아무생각없이 양방향.. 벨만포드 알고리즘 : 백준 11657 ( 타임머신) https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net NlogN 인 다잌스트라 알고리즘보다 N^3 인 시간복잡도를 가지지만 음수의 가중치를 가지는 그래프에 대해서도 최단경로를 구할 수 있는 벨만포드 알고리즘이다. 구하는 방법은 모든 간선들을 순환하면서 현재의 간선이 INF 값이 아니라면 연결된 간선들을 최신화를 해주는 방법이다. 이러한 최신화를 N-1번 반복하면 그게 벨만 포드 알고리즘이다.. 이전 1 ··· 12 13 14 15 16 17 18 ··· 25 다음