생각 생각

https://acmicpc.net/problem/1089 1089번: 스타트링크 타워 스타트링크 타워는 총 10N개 층이 있는 고층 건물이고, 0층부터 10N-1층으로 번호가 매겨져 있다. 층 번호를 숫자 N개로 표현한다. 숫자 N개로 층 번호를 표시할 수 없는 경우 앞에 0을 채운다. 숫자 www.acmicpc.net 진짜 한 대 쎄게 쥐어박고 싶은 구현 문제. input을 받고 엘레베이터 램프를 저장하고, 램프의 상태가 될 수 있는 총 8개를 하나하나 정의한다. 그리고 그 램프를 이용하여 숫자가 어떻게 만들어지는지를 정의한다. 그 후에는 특정 형태의 '고장난' 램프가 어떤 램프가 될 수 있는지를 정의한다. 치환을 통해 어떤 숫자를 만들기 위해 5개의 행에 각각 어떤 램프가 있으면 가능한지의 리스트를..

https://acmicpc.net/problem/1034 1034번: 램프 첫째 줄에 N과 M이 주어진다. N은 행의 개수이고, M은 열의 개수이다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 램프의 상태가 주어진다. 1이 켜져있는 상태이고, 0이 꺼져 www.acmicpc.net 애드혹 문제. 재미있었다. 어차피 어떻게 키든 한 종류의 행밖에 모두 켤 수 없다. 따라서 dictionary에 행의 종류와 그 개수를 저장하고, 켤 수 있는 램프 중 가장 개수가 많으면 된다. 램프의 상태를 dictionary로 받는다. 일종의 counter 쓰기 귀찮아서 그냥 만들었다. 위의 for문은 예외 처리가 필요 없는, 즉 하나의 열로만 이루어지지 않은 기본 케이스이다. 램프를 켤 수 ..

https://acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net bfs 문제인데 출발점에서 도착점까지의 거리를 고려해야 하는 문제. bfs에 처음 사람과의 거리를 저장해야 하기 때문에, 애초에 deque에 넣을 때 거리를 같이 저장한다. 탐색할 때는 거리에 1을 더해준다.

https:/acmicpc.net/problem/1992 뻘짓 한 문제. 당연히 재귀인 것도 알았고 푸는 방법도 알았으나, 잘라야 할 지 말아야 할 지를 완전탐색으로 찾지 않아서 계속 오답을 써 냈다. 당연히 여타 분할 정복 문제처럼 잘라야 하면 자르고 아니면 출력하는 형태. 괄호가 당황스러웠다.

https://acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 오히려 이런 원론적인 정점, 간선을 통한 경로 찾기가 더 어렵게 느껴진다. i번째 줄은 정점 i가 어디로 연결되어 있는가를 나타낸다. 이 문제의 핵심은 check의 이용이다. bfs(i)를 한다는 것은 i번째 정점부터 연결된 모든 정점을 찾겠다는 것이니, 시작 정점에서 연결되었다는 것을 표시해줄 수단이 필요하다.

https://acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net bfs이지만, 처음부터 직접 graph를 변환시키면서 풀어나가는 문제. visited를 굳이 쓰지 않아도 되는 것이, 어차피 단지에 해당하는 지역(1)을방문하면 1을 0으로 바꾼다. 그 후 1인 곳에만 bfs를 해주면 된다. 표준 입력으로 받는 게 나은데 까먹었다. 그래프를 탐색하면서 1을 만나면 0으로 바꾸고 해당 단지의 카운트인 answer를 1로 바꿔주기. 1인 곳에 bfs를 시행하고, 정답을 sor..

dp문제. 그래프 탐색과 달리 최선의 선택을 계속 갱신해야 할 때 이용한다. 1149와 17404는 본질적으로 다르다. 끝까지 갱신을 하고 출력을 하면 되는, 즉 선형인 1149를 먼저 보자. 최솟값을 저장하는 dp에 나올 수 있는 최대 값보다 큰 inf를 설정해둔다. 이후 한번 앞부터 뒤까지 쭉 돌아서 dp를 갱신하고 최솟값을 출력한다. ​ 17404는 출발점과 끝 점을 비교해야 한다는 점이 다르다. 즉 원형이다. 출발점과 끝 점이 다르면 비록 최솟값이라고 하더라도 이용할 수 없다. 그러니 출발점-끝점을 체크하는 방법을 이용하도록 한다. 이 방법의 핵심은, 출발 점이 총 3개, 도착점이 총 3개이니 출발-도착점의 경우의 수 9개를 2중 for문으로 돌면서 시작과 도착이 같은 경우는 갱신하지 않는 것이다.

https://acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net bfs에서 횟수를 계산해야 할 경우를 공부했던 문제. 선언부는 동일하게 표준입력으로 받고 이동 방향 설정해준다. 차이점은 visited내 값을 -1로 두는 것. 이렇게 하는 이유는 최간 거리를 세기 위함이다. 함수부에서는 visited의 값이 -1이면 방문을 한 적이 없으니 방문을 해 준다. 거기에 더해, 방문함과 동시에 내가 이동할 곳의 이동 횟수가 내가 현재 있는 cur까지의 이동횟수+1보다 크다면, 그것은 최단거리가 아니니 cur..