거창한 시작

www.acmicpc.net/problem/2422 2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 첫째 줄에 정수 N과 M이 주어진다. N은 아이스크림 종류의 수이고, M은 섞어먹으면 안 되는 조합의 개수이다. 아래 M개의 줄에는 섞어먹으면 안 되는 조합의 번호가 주어진다. 같은 조합은 두 번 www.acmicpc.net 알고리즘 종류 구현 완전탐색 사고 과정 순서가 있고 중복없이 아이스크림을 선택합니다. 그리고 안 좋은 조합을 고르지 말아야 합니다. 저는 DFS와 백트레킹을 이용해서 아이스크림을 선택하기로 했습니다. 그리고 안 좋은 조합을 제외하는 경우를 배열을 이용해서 처리했습니다. 이 방법 말고도 2차원 배열을 이용해서 3중 for문으로 완전탐색하는 방법도 있습니다. 2차원 배열에는 좋..

www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 알고리즘 종류 구현 사고 과정 주사위 면의 상태(state)와 값(val)을 나타낼 배열을 각각 생성합니다. 1. 명령어에 따라 주사위의 위치를 바꿔줍니다. 만약에 범위 밖으로 나가면 continue로 무시합니다. 2. 명령어에 따라 각 주사위 면의 상태를 바꿔줍니다. 3. 바닥과 맞닿은 지도의 값이 0인지 아닌지에 따라 처리합니다. 4. 주사위..

www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 알고리즘 종류 구현 사고 과정 뱀의 몸을 저장하기 위해서 deque으로 배열을 만들어 줍니다. 뱀의 움직임을 저장할 배열 rotate를 만들어 줍니다. 1. 뱀이 움직일 시간이면 방향을 바꿔줍니다. 2. 머리를 움직여 봅니다. 그리고 아래 조건으로 확인합니다. 2-1. 끝? 범위 밖 또는 자신의 몸과 부딪혔는지 확인합니다. 2-2. 사과? 사과가 있으면, 몸을 늘려줍니다. 사과가 없으면 꼬리 부분을 비웁니다. 구현(C..

www.acmicpc.net/problem/1414 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net 알고리즘 종류 MST 크루스칼 사고 과정 입력된 모든 랜선의 길이를 저장합니다. 그리고 크루스칼 알고리즘으로 MST를 만들면 연결된 길이를 빼줍니다. 그리고 모든 컴퓨터가 연결되었는지 확인해야 합니다. 모든 컴퓨터가 연결되어 있는지 확인할 수 있는 방법은 무엇일까요? A노드와 B노드가 연결되어 있는지는 parents 배열에 저장해두었습니다. 그렇다면, 이 배열을 for문으로 순환하면서 부모가 모두 동일하다..

www.acmicpc.net/problem/1368 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 알고리즘 종류 MST 크루스칼 사고 과정 '논 사이 연결 VS 논에 우물파기'를 비교해야 하는 문제입니다. 생각해보면, 트리가 여러 개 나올 수 있다는 것을 알 수 있습니다. 이럴 경우, 가상의 노드를 생성하여 해결할 수 있습니다. 즉, 가상의 노드 0을 만들고 0과 연결된 간선을 우물을 파는 비용으로 하면 됩니다. 아래 그림으로 설명해드리겠습니다. 우선 초기 상태입니다. 붉은색은..

www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 알고리즘 종류 구현 완전탐색 사고 과정 최대 5번 이동이라고 하니 5번 이동해서 최대값을 찾습니다. 1. 이동방향은 순열조합으로 찾습니다. 2. 네 방향에 따라 이중 for문을 다르게 하여 블록을 이동시킵니다. 이동시키는 방법은 아래와 같습니다. 2-1) 범위 끝 또는 숫자가 있는 블록을 마주하면 한 칸 전으로 이동합니다. 2-2) 현재 한 칸 이전에 있는 상태입니다. 한 칸 앞에 ..

www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 알고리즘 종류 구현 BFS 사고 과정 BFS를 이용해서 각 구슬의 위치를 저장하여 해결했습니다. 동일한 위치로 갈 수 있기 때문에 4차원 배열 isVisited를 생성하여 재방문을 체크했습니다. 1. 파란 구슬과 빨간 구슬을 움직입니다. 움직이는 도중에 구멍을 지나면 체크해 줍니다. 2. 파란 구슬이 빠졌으면 continue 합니다. 빨간 구슬만 빠졌으면 종료합..

www.acmicpc.net/problem/1445 1445번: 일요일 아침의 데이트 첫째 줄에 숲의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 3보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 숲의 지도가 주어진다. 숲의 지도는 S, F, g, . 만으로 이루어져 있 www.acmicpc.net 알고리즘 종류 다익스트라 우선순위 큐 사고 과정 다익스트라를 2차원 배열에 사용하여 해결했습니다. 값을 저장할 dp 2차원 배열을 만들어 줍니다. 시작점에서 출발하여, 아래 2가지 조건으로 비교합니다. 1. 쓰레기를 지나는 경우 비교 2. 쓰레기를 지나는 경우가 같으면, 쓰레기 주변을 지나는 경우 비교 목표 지점에 도착하면, 종료합니다. 구현(C++) 1 2 3 4 5 6 7 8 9..

www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 알고리즘 종류 구현 사고 과정 1. 말의 상태를 담을 수 있는 배열이 필요할 것 같았습니다. 그래서 Piece라는 구조체를 만들고, 이 구조체로 ps라는 배열을 만들었습니다. 구조체에는 말의 위치(y, x)와 방향(d) 그리고 맨 밑인지(isButtom)를 확인하는 변수들이 있습니다. 2. 말을 쌓을 수 있어야 합니다. 그래서 3차원 벡터를 만들기로 했습니다. state라는 명을 붙였습니다. 3. 이제 턴 1회..

제 마음대로 리뷰를 시작하겠습니다. 오랜만에 알라딘 중고서점을 다녀왔습니다. 많은 세계문학전집이 반값 이하로 팔고 있길래 여러 권 구매했습니다. 읽고 싶은 책을 싼 값이 구매할 수 있어서 참으로 좋았습니다. 문학 카테고리에서는 세계문학전집을 선호합니다. 주관적인 이유지만, 무엇을 깨달고 배우는데 실패할 확률이 적다고 생각해서 입니다. 삶에 필요한 내용을 배우는데에 엇비슷한 내용이 없는 것 같습니다. 이번 작품은 크눌프입니다. 많지 않은 페이지 수와 헤르만 헤세의 작품이라서 먼저 읽기로 했습니다. 전원적인 분위기라고 들어서 마음 놓고 읽었지만, 카페 테라스에서 책을 마무리하며 멍하니 자신을 되돌아 보는 시간을 가질 수 있었던 책이되었습니다. 줄거리 시작... 1. 초봄 크눌프는 몇 주 동안 병원에 누워있다..