본문 바로가기

알고리즘

 (14)
[ 백준 9207 ] 페그 솔리테어 (C++) # 문제링크 www.acmicpc.net/problem/9207 9207번: 페그 솔리테어 각 테스트 케이스에 대해서, 핀을 움직여서 남길 수 있는 핀의 최소 개수와 그 개수를 만들기 위해 필요한 최소 이동 횟수를 출력한다. www.acmicpc.net 이 문제를 처음 봤을 때는 왜이렇게 어렵게 생각했는지 모르겠다. ㅎㅎㅎ 처음 봤을 때는 저 말들을 어떻게 움직여줘야하지? 그냥 무작위로 다 움직이면 되나? 저 말들의 위치값을 받아두어야 하나? 한 번 움직이면 그 다음은 어떡하지? ... 뭔가 정리가 안되었다. 그냥 for 문 돌면서 말의 위치를 찾아서, 말이 이동 가능한 모든 경우의 수로 돌려보면 되는 문제였다. 근데 맵이 또 계속 달라지는데 어떻게 하지? 원본을 복사해뒀다가 한번 시뮬레이션을 하고 다시..
[정올 2514] 문자열 찾기 # 문제링크 jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1775&sca=2050 JUNGOL www.jungol.co.kr 주어진 문자열에서 연속 3개의 문자가 IOI 이거나 KOI인 문자열이 각각 몇 개 있는지 찾는 프로그램을 작성하라. 문자열은 알파벳의 대문자로만 이루어진다. 예를 들어 "KOIOIOI"라는 문자열은 KOI 1개 , IOI 2개가 포함되어있다. -> string 으로 받아서, 0번째 글자부터 s.length() - 2 까지 돌면서 KOI 와 IOI를 찾았습니다. # 제출 코드 #include using namespace std; int main() { string s; cin >> s; int K = 0, I = 0; for (int i = ..
[백준 2659] 십자카드 문제 C++ 풀이 # 문제링크 www.acmicpc.net/problem/2659 2659번: 십자카드 문제 입력은 한 줄로 이루어지며, 이 한 줄은 카드의 네 모서리에 씌여있는 1 이상 9 이하의 숫자 4개가 시계 방향으로 입력된다. 각 숫자 사이에는 빈칸이 하나 있다. www.acmicpc.net 모든 시계수를 만들어 visited 에 체크하고, 주어진 수 까지 앞에 몇개가 있었는지 확인했습니다. 시계수를 만들 때 4중 for 문을 사용했는데 이렇게 하는 게 맞는지 모르겠네... 하면서 했습니다. 더 좋은 방법이 있을지도.. # 제출 코드 #include #include using namespace std; bool visited[10000]; int get_num(int a, int b, int c, int d) {..
[백준 11004] K번째 수 # 문제링크 www.acmicpc.net/problem/11004 11004번: K번째 수 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 정렬해서 K 번째 있는 수를 구해야 한다. C++의 STL에 sort 를 활용해서 배열을 완전히 정렬한 후 K번째 값을 출력하면 된다. 정렬해서 몇 번째에 있는 수를 알려주는 STL인 nth_element 함수가 있다. nth_element(시작, 찾고자하는 인덱스, 끝) 이렇게 넣어주면 된다. # 제출 코드 // sort 를 이용한 풀이 #include #include using namespace std; long long int a[5000001]..
[백준 10825] 국영수 정렬문제 # 문제링크 www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net STL의 sort 에 compare 함수로 구현했습니다. # 제출 코드 #include #include #include #include using namespace std; struct Student { string name; int kor; int eng; int math; }; bool compare(const Student&a, const Student&b) { if (a..
[백준 1012] 유기농 배추 # 문제링크 www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 섬 개수 세는 문제랑 비슷한 문제다. DFS로 같은 섬의 방문한 map을 다시 0으로 변경시켜주어 다시 세지 않도록 한다. 모든 1을 0으로 바꿔주었기 때문에 여러 번 반복하더라도 초기화 할 필요가 없어서 좋다. # 제출 코드 # include char map[50+2][50+2]; int T, M, N, K; int yd[] = { 1, -1, 0,0 }; int xd[] = { 0, 0, 1, -1 }; v..
[백준 2146] 다리 만들기 # 문제링크 www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net DFS를 사용하여 섬을 구분하고, BFS를 사용해서 가장 짧은 거리를 찾는 문제. DFS, BFS 둘 다 써야하는 문제였어요. 문제 예시로 준 섬입니다. 이를 아래처럼 0과 1로 표시할 수 있습니다. 1 1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 1 1 1 0 1 1 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0..
[백준 1010] 다리 놓기 #조합 # 문제 링크 www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 > T; while (T--) { int N, M; cin >> N >>..

티스토리툴바