일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
- React
- 제로베이스
- 서버
- C++
- 구조체
- map
- 자바스크립트
- 제로베이스 프론트엔드 스쿨
- 멀티스레드
- 알고리즘
- 문자열&연산자
- 프론트엔드 스쿨
- Algorithm
- leetcode
- MemoryBarrier
- 완전탐색
- 백트래킹
- Server
- socket
- 메모리 배리어
- 프로그래머스
- c#
- 코딩테스트 스터디
- JavaScript
- N과 M(2)
- BFS
- 코딩테스트
- dfs
- 구현
- 백준
- Today
- Total
목록알고리즘 문제풀이 (49)
Written
코딩테스트 스터디 2주차 기록입니다. https://leetcode.com/problems/roman-to-integer/ Roman to Integer - LeetCode Roman to Integer - Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII leetcode.com 로마 숫자를 정수로 변환하는 문제였습니다. 처음에 문제에 나온 ..
제로베이스 프론트엔드 10기 수강생들 내에서 코딩 테스트 스터디를 따로 진행하면서 공부한 것들의 내용을 정리하고있습니다. leetcode 9번 문제 Palindrome Number 풀이입니다. 기존의 x를 거꾸로해서 벡터에 넣고, 1번 인덱스의 값과 제일 뒤의 인덱스 값을 비교하면서 앞에서는 하나씩 늘리고 뒤에서는 하나씩 줄이면서 대칭이기 때문에 size를 2로 나누어 절반만 확인해서 답을 구해봤습니다. 한번이라도 다르면 규칙에 안맞기 때문에 바로 return false로 함수를 끝냈습니다. class Solution { public: bool isPalindrome(int x) { vector res; if ( x < 0) return false; while(true) { int a1 = x / 10;..
https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 시간초과로 인해 애를 많이 먹었던 문제입니다. 맨 처음에 문제를 보고 떠올린 풀이는 vector에 넣고 sort함수를 사용해서 가운데 수를 출력하는 것이었습니다. 문제의 시간제한이 0.1초이기 때문에 왠지 시간초과가 날 것 같다는 생각이 들었지만 ... 다른 풀이가 딱히 떠오르지 않아 풀이를 제출해보았는데 역시나 시간초과가 났습니다 :D 그래서 밑에 힌트를 확인해보니 , 우선순위 ..
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 2606번 유니온 파인드 사용 풀이입니다. 문제를 풀고 정답으로 채점받는 것 까지는 괜찮았는데, 헷갈리는 개념들이 있어서 백준 게시판에 질문을 올렸고 다행히도 답변을 받았습니다 ! 링크 올려드리겠습니다. (https://www.acmicpc.net/board/view/104773) 아래는 유니온 파인드로 푼 코드입니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 1..
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제를 보고나서 드는 생각은 DFS로도 풀 수 있을것 같고, Union-Find로도 풀 수 있을 것 같다고 생각했는데 DFS로 문제를 풀어본지가 좀 오래된것 같아 DFS로 구현해서 풀어보았습니다. 컴퓨터간의 방향이 따로 없어서 인접리스트 형식으로 서로 연결되어 있게끔 데이터를 저장합니다. 그리고 문제가 1번 컴퓨터를 기준으로 시작하기 때문에 DFS(1)로 구현한 DFS함수를 호출합니다. DFS에 들어오..
https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 이번 문제의 핵심은 '연결되어있기만 하다면' 다른 곳을 통하여 목적지까지 갈수 만 있으면 되는 것 입니다. 그래프의 연결관계를 확인하고 싶을 때, 사용되는 Union Find알고리즘으로 문제를 풀어보았습니다. 입력으로 주어지는 정보를 바탕으로 두 도시가 연결되어있다면 Union함수를 통해 이어주고, 마지막으로 답을 구하기 위한 최종 여행 루트의 연결관계를 파악해서 그 중 하나의 도시라도 이어져있지..
https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 출발점에서 인접한 방향(상,하,좌,우)으로 이동하면서 도착지점까지 가장 적은 루피손실을 만들어내는 문제였습니다. BFS로도 풀 수 있겠지만, 다익스트라 알고리즘으로 풀어보았습니다. 다익스트라 알고리즘 문제는 아직 경험치가 부족해서 풀다보니 BFS랑 다익스트라를 합친 것 같은 .. 혼종 알고리즘이 되어버렸지만 ... 그래도 출력은 잘되고 채점은 맞았다고 나왔습니다 ! 완벽하게 다익..
https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 큐에 좌표값을 저장해서 이동할 수 있는 곳이면 거리값들을 1씩 증가시키면서 마지막에 거리 정보를 저장한 배열의 [N][M]값을 출력하는 BFS탐색으로 문제를 해결해보았습니다. 그런데 첫번째 코드에서 메모리초과가 발생했습니다. 메모리제한이 192MB인데 , 배열의 크기도 크지않은데 어째서 메모리초과가 나는 것인지 ..궁금해 하다가 구글링 해본 결과 BFS를 사용할 때, 종종 발생하는 일이더라구요. 예를 들면 아직 (3,3)의 좌표..