본문 바로가기

전체 글89

백준 2178번 C++ 미로 탐색 미로탐색N×M크기의 배열로 표현되는 미로가 있다.101111101010101011111011미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. 코드1234567891011121314151617181920212223242526272829303132333435363738394041#include #include using namespace s.. 2019. 6. 26.
백준 9466번 C++ 텀 프로젝트 텀 프로젝트https://www.acmicpc.net/problem/9466이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.예를 들.. 2019. 6. 15.
백준 7576번 C++ 토마토 토마토https://www.acmicpc.net/problem/7576철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일.. 2019. 6. 14.
백준 1012번 C++ 유기농 배추 유기농 배추https://www.acmicpc.net/problem/1012차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다.(한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있다고 간주한다)한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어놓았다. 배추들이 모여있는 곳에는 .. 2019. 6. 12.
백준 4963번 C++ 섬의 개수 섬의 개수https://www.acmicpc.net/problem/4963정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오.한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러쌓여 있으며, 지도 밖으로 나갈 수 없다. 푸는 법DFS 혹은 완전 탐색으로 풀면 된다고 한다.(i, j)의 위치에서 인접해있는 8개의 위치를 조사해서 탐색해나가면 되는 문제다.map[i][j]이 0이 아니라면 map[i][j]에 0을 대입하고 주변을 탐색한다.map[i][j]=0은 이미 방문한 섬이므로 중복을 방지하기.. 2019. 6. 12.
백준 1707번 C++ 이분 그래프 이분 그래프https://www.acmicpc.net/problem/1707그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다.그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 푸는 법이분 그래프인지 확인하는 법알고리즘 검색하다 보면 꼭 나오는 이 분의 블로그를 보고 그냥 이대로만 하면 맞을 수 있다.주의할 점은 테스트 케이스를 실행할 때마다 그래프와 체크를 초기화해주는 것이다.나는 DFS로 풀었고, 만약 start의 색깔과 next의 색깔이 이미 존재하고(둘다 방문했고) 색깔이 같으면 재귀문을 빠져나와 answer이 N.. 2019. 6. 12.
포스팅이 밀리고 있다 일기 써야 하는데 포스팅이 밀린다...알고리즘 와! 너무! 꿀잼!이기도 하고 시험 두 개 보느라 시간이 없다...어제오늘은 합숙이었어서 되게 재밌었는데 그것도 월요일에 몰아서 포스팅 해야지일본 이제 한달 반밖에 남지 않았다...열심히 놀러 다녀야지 2019. 6. 10.
지식공학 패턴인식 부분 번역 패턴인식 (1)학습목표패턴인식의 흐름특징벡터프로토타입인식선형식별함수를 쓰는 수법구분적선형식별함수를 쓰는 수법인식: re-cognitioncognition: 인식, 인지recognition: 보고 그것을 알 수 있는 것.패턴 인식이란소년의 사진(데이터 취득)전처리특징추출식별사전(프로토타입)입력-데이터, 패턴공간출력-클래스,카테고리공간패턴인식의 분류판별문제: 구하는 출력이 이산적인 라벨인 경우2클래스문제: 동일인물? 얼굴? 얼굴아님?다클래스문제: 누구? 무슨 스포츠?회귀문제: 구하는 출력이 연속적인 라벨인 경우몇살? 당도는 얼마? 능력은?(점수아니고)-> 수치, 측정라벨비계량데이터: 덧셈, 뺄셈에 의미가 없음계량데이터: 덧셈, 뺄셈에 의미가 있음패턴인식 응용예문자인식, 숫자인식, 물체인식얼굴검출, 문자검출행.. 2019. 6. 10.
백준 11004번 C++ K번째 수 K번째 수https://www.acmicpc.net/problem/11004수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. 문제는 간단해보였는데...아마 이걸 푸는 사람들을 기다리는 건 시간초과일 것이다.그냥 알고리즘 헤더에 있는 소트함수로 하면 될 것 같았는데 안 돼서 오늘 Min Heap으로 풀었다.그랬더니 아슬아슬하게 통과.radix sort를 이용하면 시간복잡도는 O(dn) (d: 데이터의 가장 큰 자리수, n: 데이터수)이라고 한다. 더 빠르게 풀 수 있을 듯우선순위 큐 최고...시간초과 참고는 여기 코드123456789101112131415161718#include #include using namespa.. 2019. 6. 10.

티스토리툴바