Algorithm

프로그래머스 숫자카드나누기 // 복잡하면 함수로.. , 배열을 정렬하라.

코딩테스트 연습 - 숫자 카드 나누기 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 : 탐색이많다 해결 : 정렬, 배열중 최소값의 약수 비교만으로 충분함. ex) 14,35, 70 의 최대공약수 후보 : 1,7,14 중에 있다. / 35,70약수는 필요없음. #include #include #include using namespace std; //안나눠 지는게 잇다.(true) bool is_rest (int num, vector array) { for(auto c : array) if (c%..

프로그래머스 여행경로 // 키가 string인 dfs는 for(i)로 해결, 예외처리 백트래킹

https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr * 문제1 : 알파벳순서대로 방문 해결 : dfs전 정렬 *문제2 : 키가 string인데? visit[string]가능? ㄴㄴ 해결 : 원소가 2개밖에없으므로 for(i)로 돌면서 2차원벡터 방문 여부만 체크. 접근은 ticket[i][0], [i][1]로 접근 *문제 3: a->b c->d 인거는 못가고, a->b, b->c 인거만 가야함 해결 : 이전값(b)과 현재값(c)이 다르면 pass ..

백준 2529 부등호 // 재귀로 완탐구현 , string 정렬시주의

2529번: 부등호 (acmicpc.net) * 재귀로 완탐구현 기본꼴 : go(index, 임시저장결과값) 1. 종료조건 2. 직접해보면서 일반화하라. 마지막숫자 == num[idx-1] 비교할숫자 == i 비교할op == a[idx-1] 임을 알 수 있다. * string 정렬시주의 "23" "123" 비교시 앞부터 하나씩 비교 하므로, 23이 더 크게됨에 주의. #include using namespace std; int n, temp, check[14]; vector ret; char a[14]; bool good(char a, char b, char op) { if (op == '' && a > b) return true; return false; } void go(int idx, string ..

백준 1987 알파벳 // 노드가 각자의visit을 가져야한다면 원복! , dfs visit[now] [next]둘중 하나만 해라

1987번: 알파벳 (acmicpc.net) 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net * 노드가 각자의visit을 가져야한다면 원복! visited[a[ny][nx] - 'A'] = 1; dfs(ny, nx, cnt + 1); visited[a[ny][nx] - 'A'] = 0; * dfs visit[now] [next]둘중 하나만 해라 void dfs(int y, int x, int cnt) { v[y][x]=1;//항상 참이됨 ~~~~ v[ny][nx]=1; dfs[ny][nx]; } 문제 ..

백준 3197 백조의 호수 // bfs멈춰는 tempQ, 1차원에서 논리짜라, next경우의수를 나눠서 처리하라, pair Q 클리어하는법

3197번: 백조의 호수 (acmicpc.net) 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net * 논리짜기 물) . . 다음(next)경우의수 : '.' X L '.'-> 계속, 입력시 이미큐에넣어놓음, 방문처리도함 -> 처리필요X 'L'->계속, L도 물로간주. 입력시 처리완료. -> 처리필요X X -> 멈춰 1.tempQ push 2. 방문처리 3. there을 '.'으로 수정. 백조) . . 다음(next)경우의수 : '.' X L '.'-> 계속, Q.push 'L'->..

백준 14497 주난의 난// bfs멈춰는 큐2개로 해결, 어려우면 1차원에서 논리를 짜라

14497번: 주난의 난(難) (acmicpc.net) 14497번: 주난의 난(難) 주난이는 크게 화가 났다. 책상 서랍 안에 몰래 먹으려고 숨겨둔 초코바가 사라졌기 때문이다. 주난이는 미쳐 날뛰기 시작했다. 사실, 진짜로 뛰기 시작했다. ‘쿵... 쿵...’ 주난이는 점프의 파 www.acmicpc.net * 어려우면 1차원에서 해보면서 논리를 짜라 # 1 0 0 1 0 0 계속 //q.push 1->멈춰, cnt++ //temp.push, q=temp, cnt++ ex) next가 1일때, temp.push만 되므로 q.size==0이 됨 => q=temp, cnt++ 실행됨. //새로운시작 * bfs는 도중에 탈출X, 방문배열에 정답을 모두담고, 출력만해라. * 탈출조건 문제 while (true..

백준 12851 // bfs암기, 정답 경우의수 구하기는 cnt[next]+=cnt[here]

12851번: 숨바꼭질 2 (acmicpc.net) 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net * 정답 경우의수 구하기 핵심코드 for (int next : {now - 1, now + 1, now * 2}) { //1. 범위체크 if (next >= 0 && next >k ; /* * bfs algorithm * 1.초기화 cnt[n] = 1; * 2.종료조건 * 3.next 범위체크 * 4.next 방문체크 * 5.visit[next] 갱신 * 5.1 q.push!..

백준 13913 // bfs 경로추적은 prev[next]=here

13913번: 숨바꼭질 4 (acmicpc.net) 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net * bfs 경로추적 핵심코드 prev[10]=5 // prev[5]=3 .. 이런식으로 연결함. ex) 노드 : 5-10-11(목표k) 벡터 : 11(k)-10(prev[11]). 문제 : 첫노드는 안들어감 ,역순으로 넣어짐 해결 : push(start), 리버스 for (int next : {now - 1, now + 1, now * 2}) { //1. 범위체크 if (next..