https://www.acmicpc.net/problem/1283 1283번: 단축키 지정 첫째 줄에 옵션의 개수 N(1 ≤ N ≤ 30)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄에 옵션을 나타내는 문자열이 입력되는데 하나의 옵션은 5개 이하의 단어로 표현되며, 각 단어 역시 10개 이하 www.acmicpc.net 쉬워보여서 덤볐는데, 생각보다 구현과 문자열 처리가 힘들어서 애먹은 문제이다. 1. dic이라는 int형의 defaultdic을 만든다. 2. 입력받는 문자열을 공백 단위로 끊어서 s에 저장한다. 3. s에 저장된 문자열을 돌며 단축키를 지정한다. 3-1. 만약 tf가 True이면 앞의 단어에서 단축키가 설정되었으므로 단어를 tmp에 넣는다. 3-2. 만약 단어의 첫글자가 dic에 ..
https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 요즘 구현, 시뮬레이션 문제들을 미는 중인데 삼성기출을 풀다 백준문제를 푸니 확실히 쉽게(?) 느껴진다. 시뮬레이션 문제는 말 그대로 주어진 조건을 따라 시뮬레이션을 돌리면 된다. 골드 이상부터는 엄청난 집중력과 끈기, 인내가 필요하다.. (빡구현, 하드코딩) 1. 사과위치를 입력받고 정사각보드m에 사과위치를 -1로 표시해준다. 2. 방향변환정보를 turn이라는 dictionary에 저장한다. 예제 1같..
www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 1. 보물 -> 육지 사이의 최장거리이므로 지도(m)을 입력받고 지도에 있는 모든 육지좌표를 land배열에 저장한다. 2. bfs함수: visited배열초기화, dist배열 0으로 초기화, (i, j) 시작지점에 대해 deque에 넣고 bfs를 돌린다. 만약 상하좌우 칸에 방문하지 않았고, 그 칸이 육지라면 거리를 1증가시킨다. 최종적으로 거리의 최댓값을 return (27번째 줄 코드는 2차원 배열에서 최댓값을 ..
www.acmicpc.net/problem/18110 18110번: solved.ac 5명의 15%는 0.75명으로, 이를 반올림하면 1명이다. 따라서 solved.ac는 가장 높은 난이도 의견과 가장 낮은 난이도 의견을 하나씩 제외하고, {5, 5, 7}에 대한 평균으로 문제 난이도를 결정한다. www.acmicpc.net 쉬운 문제이지만, 파이썬의 허점(?)을 알 수 있는 문제였다.. 파이썬은 다른 언어와 다르게 반올림을 할 때 사사오입이 아닌 오사오입이다. www.omnibuscode.com/board/board_devcommon/43652 OMNIBUSCODE [개발상식] - 반올림하는 두 가지 방법 (Round-off(사사오입), Round-to-nearest-even(오사 오입)) 1. 근사값..
www.acmicpc.net/problem/14676 14676번: 영우는 사기꾼? 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐 www.acmicpc.net 앞서 올렸던 위상정렬 알고리즘을 응용해서 푸는 문제이다. 1. M만큼 X, Y를 입력받고 graph[X]에 Y를 append해주고, indegree[Y]에 1을 더해준다. 2. K만큼 반복문을 돌며 건물을 짓거나 파괴합니다. 3. 만약 command가 1이라면 building번 건물을 짓고자 하는 것이므로 indegree[building]을 확인한다. 3-1. indegree[b..
www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 전형적인 위상정렬 문제이다. 위상정렬 알고리즘은 추후에 한 번 포스팅 할 예정이다. 1. N, M을 입력받고 M번 만큼 A와 B를 입력받는다. 2. A가 B 앞에 줄 서야 하므로 graph[A]에 B를 append해주고 indegree[B]에 1을 더해준다. (indegree 배열: 진입차수) 3. indegree[1]부터 indegree[N]까지 돌며 진입차수가 0인 노드를 큐..
www.acmicpc.net/problem/11946 11946번: ACM-ICPC 대회가 끝난 후 팀 별 성적을 순위에 따라 출력한다. 만약 순위가 같으면 팀 번호가 빠른 것을 먼저 출력한다. 각 팀마다 팀 번호, 푼 문제 수, 총 시간을 출력한다. www.acmicpc.net 단순 구현문제이지만, 생각보다 빡세서 포스팅해본다. 일단 입력값이 많고, 그에 대한 순서 처리가 생각보다 힘들다. 1. dic이라는 딕셔너리를 만들고 미리 1번팀의 1번문제 결과부터 n번팀의 m번 문제결과 까지 [0, -1]을 만들어 놓는다. (주석에 설명했듯이 '틀린횟수'와 '총 시간'이다) 2. q개의 로그를 입력받는다. 만약 log[3]이 'AC'가 아니라면 틀린 것이므로 해당하는 팀의 문제결과인 dic[dic[(int(l..
www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net N이 100이하이므로 O(N^3)인 플로이드-와샬 알고리즘을 사용해도 통과가 될 것 같아서 풀어보았다. 1. M개 만큼 a와 b를 입력받고 a와 b사이의 거리를 1로 cost배열에 넣어준다. 2. 플로이드-와샬 알고리즘을 통해 각 건물 사이의 거리를 구해준다. 3. 브루트포스 방식으로 치킨집이 1번,2번일 때 부터 1번,3번 ... N-1번,N번까지일 때 모든 도시에서의 왕복 시간..
모르는 사이에 조금씩 조금씩..
