본문 바로가기

BOJ

백준 14889 / 스타트와 링크 순열을 이용한 브루트 포스 문제. 아이디어가 필요하다. n의 최대값이 20이기 떄문에 20명으로 구성된 순열에 대해 모든 값을 구하는 건 시간초과가 발생한다 (20!) 그렇다면 20명을 두 팀으로 나누는 아이디어가 필요. 해결법은 0(n/2개)과 1(n/2개)로 구성된 n짜리 배열을 만들고, 첫번째 팀은 0 두번쨰 팀은 1로 배정받는 방식이다. 코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788#include#include#include#include#i..
백준 1339 / 단어 수학 순열, 백트래킹을 이용한 문제. 처음에 풀땐 굉장히 헤맸다. 들어간 알파벳의 우선순위를 정하고 우선순위에 맞게 숫자를 부여하는 방식을 사용했었는데, 계속 반례에 걸리는 듯하여 순열을 사용해서 풀어보았다. 여기서 처음 알게된 유용한 함수가 있다. 바로 vector안의 중복된 것들을 모두 지워주는 함수. v.erase(unique(v.begin(), v.end()), v.end()); unique 함수는 vector 내부의 중복된 값들을 맨 뒤로 정렬하고, 자신이 바꾼 vector의 end() 부분을 반환한다. 그 부분만 erase해주면 중복제거가 된다. 또 string s 에 대해 for(char x : s)를 사용하면 x가 s의 한 글자씩 입력받는다는 사실도 처음 알았다. 두 개다 유용한 함수니 기억해두..
백준 2529 / 부등호 순열을 먼저 만들고, 그 사이사이에 입력된 부등호를 껴놓은 후 모든 조건을 만족하면 출력하는 문제. n개의 숫자로 모든 순열을 만들어보는 함수인 next_permutation과 prev_permutation이 있음을 잊고 있었다. next_permutation은 오름차순이기 때문에 최소값을 구할 때 쓰고, prev_permutation은 내림차순, 최대값을 구할 때 쓰면 된다. 코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include#include#include#include using namespace std; int n;vec..
백준 6064 / 카잉 달력 정확히 1년전에 풀어봤던 문제. 그때는 막 공약수도 구하고 복잡하게 풀었던 거 같은데. 강의를 보니 꽤 쉽게 풀리는 문제였다. 우선 year를 1씩 늘려가며 푸는 방식은 m,n의 제한이 4만이기 떄문에 시간초과가 발생한다. 카잉달력에서 앞자리와 뒷자리를 1씩 빼본 것이다. 1을 뺴보니 정확히 눈에 띄는 특징이 생긴다. 23을 예로 들면, 23을 5로 나눈 나머지가 3이고 7로 나눈 나머지가 2, 즉 가 됨을 알 수 있다. 이 패턴을 발견하면 쉽게 풀 수 있다. 코드 12345678910111213141516171819202122232425262728293031323334353637383940#include#include#include#include using namespace std; int main()..
백준 1107 / 리모컨 브루트포스 문제인데, 수학문제에 가깝다. 먼저 멀쩡한 버튼으로 숫자를 누르고 목표 채널로 한칸씩 이동할때 걸리는 카운트를 비교하는 코드이다. 굉장히 무식한 코드인데 재귀를 이용한 코드보다 보기 깔끔하고 이해하기 쉽다. 1000000번만 돌면되기 때문에 걸리는 시간도 그리 크지 않다. 코드 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include using namespace std;bool broken[10];int possible(int c) { if (c == 0) { if (broken[0]) { // 0번이 고장났을때. return 0; } else { return 1; ..
백준 5719 / 거의 최단 경로 나중에 다시 한번 풀어야할 문제. 다익스트라와 BFS를 동시에 사용해야하는 문제. 어렵다. 굉장히 헤멘 문제. 플로이드 워셜 알고리즘으로 풀면 최단경로를 '모두' 찾는데 어려움이 생긴다. 1. 다익스트라로 최단경로를 (모두) 찾는다. (최단경로를 따로 저장해두어야한다) 2. 최단경로에 걸친 간선들을 모두 삭제한다. 3. 다익스트라로 새 최단경로를 찾는다. 다익스트라 코드에서 trace를 갱신하는 부분이 핵심이다. 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858..
백준 1753 / 최단경로 다익스트라 문제. 가중치가 붙어있으면 BFS와 queue를 사용하여 풀 수 없다. (음수인 가중치가 있다면 다익스트라도 사용할 수 없다.) 다익스트라에 대한 정보는 꺼무위키에서 보자. https://namu.wiki/w/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 다익스트라를 구현하기 위해선 우선순위 큐(priority_queue)를 사용해야 한다. 일반 queue / BFS 사용법과 다익스트라/우선순위 큐의 사용법 차이는 다음과 같다. 1. 우선순위 큐에서 pair를 사용할 시 first로 비교하기 때문에 가중치를 first에 넣어주어야한다. (first가 같을 시 second를 비교한다) 2. ..
백준 9205 / 맥주 마시면서 걸어가기 굉장히 쉬운 문제인데 어렵게 해석해서 고생했던 문제다. 집 좌표와 편의점 좌표, 펜타포트 좌표를 받고. BFS를 활용하여 펜타포트에 도착할수 있는지, 아니면 각 편의점에 도착할 수 있는지 판단하여 현재 지점에서 갈 수 있는 편의점의 위치를 큐에 넣어주면 된다. 편의점을 방문했는지 확인하는 bool 배열이 필요하다. 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384#include#include#include#include#include#include using name..

티스토리툴바