알고리즘 썸네일형 리스트형 11576번 11576번 - Base Conversion 진법 변환문제. A진법을 B진법으로 바꾸기 위해서 A진법을 10진법으로 바꾼 후, 10진법을 B진법으로 바꿨다. 그동안 진법을 좀 풀어봐서 이제 감이 잡혔다. 이번 코드에서는 while 문이 아닌 재귀를 쓰면서 호출이 종료되기 직전에 결과를 출력해서 stack 이나 vector 를 reverse 하지 않고 역순으로 출력이 되도록 하였다. ( 이게 위상정렬인가?? 에서 배웠던것 같은데.. 복습이 필요하겠군) 123456789101112131415161718192021222324252627282930313233343536#include#includeusing namespace std; void trans(int x, int b){ if (x == 0) { retu.. 더보기 2089번 2089번 - -2진수 -2진수라 해서 특별한 방법이 있는것은 아니고 , 다른 진수 변환이랑 비슷하긴 한데 중간 과정에서 처리해줘야 할 조건이 조금 있었다. 나는 그냥 2진수 처럼 풀면서 필요한 부분에 - 만 하면서 진수 변환을 시켜줬다. N이 음수일 때, 또 나누어 떨어질 때, 그러지 않을 때 나눠야 했다. 처음에 틀렸다가 예시로 주어진 1,2,3,4 를 대입해보던 중에 4에서 조건을 또 처리해야 한다는 걸 느껴서 바꿨다. 그리고 N이 0일 경우를 따로 체크해줘야 했다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include#include#includeusing namespac.. 더보기 1212번 1212번 - 8진수 2진수 8진수를 2진수로 바꾸는 문제. 2진수를 8진수로 바꿀때와 비슷하게 8진수 숫자 하나 하나를 2진수로 바꾸면 되는 문제였다. 단, 맨 첫 8진수 숫자를 빼고, 나머지 8진수 숫자들은 , 무조건 2진수 3자리로 나타내야 했다. (처음에 이점을 간과했음) 그리고 내가 짠 코드는 0을 따로 추가해야했다. 그 외에는 2진수로 바꾸는 방법 등은 동일하게 사용함. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include#include#include#include using namespace std;string getNum(cha.. 더보기 28.2 문제: 고대어 사전(문제 ID: DICTIONARY) 28.2 문제: 고대어 사전(문제 ID: DICTIONARY, 난이도: 하) 위상정렬 문제... 위상정렬은 사이클이 없는 방향 그래프, 즉 DAG일 때만 가능한데.. 위상정렬이 맞는지 아닌지 체크하는 코딩 방법을 모르고 있었다... 그래서 헤메다가 책을 보고 역방향 간선이 존재하는지 여부만 체크하면 된다는 것을 알게 되었다. 위상 정렬을 할때는 bfs 를 쓰거나 dfs를 쓰는 두가지 방법이 있다. 이번 문제에서는 dfs 로 위상정렬을 하고 리턴될때마다 저장한 vector를 이용해서 역방향 간선을 체크할 수 있는 방법을 알게됐다. (bfs로 풀때 위상정렬 체크하는 방법도 알아놔야 겠다!) 원래는 그냥 스택에 넣고 출력만 했었는데, 위상정렬을 한번 더 체크하려니 조금 복잡했었다. 책에서는 이차원 배열같이 해.. 더보기 1766번 1766번 - 문제집 위상정렬과 우선순위큐를 이용한 문제였다. 나는 우선 순위 큐를 몰라서 따로 구글에서 검색해서 알아봤다. 가장 핵심은 디폴트 값이 가장 큰 값을 가장 우선 순위로 두는 max heap 이라는 점이었다. 사실 이 문제는 가장 작은 값을 우선 순위로 둬야하는데, 그 테크닉을 -1을 곱해주는 방법을 통해서 극복했다.(물론 다른 분들꺼 답습) ##문제 풀면서의 고민## 우선 순위큐를 이용하면 중간에 정점들이 뒤섞여서 순서가 바뀌지 않을까? 하는 걱정이었다. 백준 SLACK 을 통해서 질문을 하니 갓분들께서 답변을 주셨다. 큐 안에 들어있는 값들은 indegree 값이 0이기 때문에 언제 빼내도 상관없고, 그렇기 때문에 섞을 수 있다고 했다. 나는 indegree 가 0이어도 뭔가 섞이지 않을.. 더보기 11403번 11403번 - 경로 찾기 bfs를 돌려서 모든 점을 방문할 수 있을거라 생각하고 bfs로 시작했다. 간선이 양방향이 아니란 점이 중요하고, 내 풀이 방식에서 시작점을 check 하지 않았다. 이는 예를 들어 0에서 0으로 돌아오는 것을 확인할 수 있도록 남겨두었다. 나는 i = 0 일때 bfs를 돌려서 갈 수 있는 체크 된 지점을 모두 1로 맵 세팅하고 i=1 일때 또 bfs를 돌려서 갈 수 있는 체크 된 지점을 모두 1로 세팅하는 방식으로 했다. ##플로이드-워샬 알고리즘이 편하다고 다른 사람들이 그러던데.. 공부를 더 해야겠다. 플로이드 워셜 알고리즘 정답 코드 2개 추가. 첫번째꺼는 최단거리를 구한 후 바꿔주는 코드이고, 두번째 코드는 플로이드 워셜 알고리즘에서 그냥 경로가 존재하는지 확일 할 때.. 더보기 2252번 2252번 - 줄 세우기 위상 정렬에 대해서 알아보다가 예제로 풀어본 문제. 위상 정렬이 필요한 경우.. 게임에서 보면 스킬을 1번 찍고, 2번을 찍어야 3번을 찍을 수 있을 때와 같은 상황? 어떤 작업의 우선순위가 필요한 경우??에 사용된다. 주의할 점은 위상정렬은 DAG(Directed Acyclic Graph) 의 구조에서 사이클이 없을 때 사용가능. 싸이클이 발생하면 우선 순위가 흐려지기 때문 '위상 정렬'을 하는 방법은 2가지가 존재. 1. 한 정점에 들어오는 간선의 수가 0일 때, 큐에 넣음으로서 정렬을 할 수 있다. 2. DFS를 통해서 답을 구할 수 있다. 나는 1번 방법으로 문제를 풀었다. 우선 들어오는 간선의 수가 0인 값들을 큐에 넣어주었다. 그 뒤에 각 정점을 방문하면서 , 그 정점.. 더보기 11723번 11723번 - 집합 비트마스크를 공부하면서 기본적인 연습문제로 풀어보았다.. 풀면서 발생했던 문제 1. 시간초과-> cin,cout 을 모두 scanf,printf 로 바꾸면서 수정.2. 처음에 string쓰다보니까 cin, getline 썼을 때 공백으로 인한 문제점 -> char 로 바꾸고 모두 통일하면서 수정.3.원소 1이 비트마스크 0번째 수, 원소 2가 비트마스크 1번째 수... 이런거 헷갈렸음. S 집합에 p번째 원소 추가S |= (1 더보기 이전 1 ··· 35 36 37 38 39 40 41 ··· 46 다음